ABS Coins(ABC087B)をループ1回で解く

前々から興味はあったんですが、今年に入ってからAtCoderをはじめました。
とりあえず出てみて慣れつつ、過去問をちょこちょこ解いたりAOJちょっとずつやったりとかで地味に頑張ってます。
競プロはガチ勢は実行速度の早いC++とかC#とかでやってるイメージが非常に強いんですが、自分は個人的に慣れようと思ってたGoでやっています。
この記事を書いた次点ではまだ灰色ですが、継続的に頑張っていきます。

さて、ABS（※）の中にCoinsという問題があります。
https://atcoder.jp/contests/abs/tasks/abc087_b

※参考
AtCoder Beginners Selection
けんちょん(@drken)さんの下記の記事を参考にして作られた（で、いいんですよね？）、最初のチュートリアル的な10問です
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

問題文はAtCoderのページやけんちょんさんの記事をご参照ください。
ざっくりいうと、500円、100円、50円をそれぞれ1枚以上持っていて、その中で合計金額をX円にするためには何通りの方法があるか、というのを求めるというものです。

この記事の趣旨

なぜ既に散々ネット上に解説が上がっているものに対して今更書こうかと思ったかと言うと、　別解に対する解説をしているものがあまりちゃんと見つからなかったからです。
下で書きますが、この問題にはいくつか解き方があります。
ただ、言及されているのは愚直な全探索と、工夫して1回ループを減らすパターンまでばかりで、ループ1回で行う方法については（探した限り）見つかりませんでした。
なので、今後学習する方の参考になればと思って書こうと思った次第です。
なお、筆者は一応理系でしたがそこまで数学が得意だったわけではないのでいい加減な説明があるかもしれません。
変なところがあったら補足をいただけるととても嬉しいです。

解き方

調べればいっぱい出てきますが、一番単純な方法は全探索です。
Goで実装するとこんな感じです。大体どの言語でも似たような感じかと。

全探索

package main

import "fmt"

func main() {
    // 愚直な全探索パターン
    var A, B, C, X, ans int
    fmt.Scan(&A, &B, &C, &X)
    for i := 0; i <= A; i++ {
        for j := 0; j <= B; j++ {
            for k := 0; k <= C; k++ {
                if 500*i+100*j+50*k == X {
                    ans++
                }
            }
        }
    }
    fmt.Println(ans)
}

この問題を解くだけであれば
$ 0 \le A,B,C \le 50$
であるので、仮にすべて50枚だったとしても高々50^3=125000通りを調べればいいだけで、十分時間内に計算ができます。
上記はそれをfor文の3重ループで実装しています。
実際にコンテスト中であれば、実装の早さを考慮してこれでいいと思います。（自分はいきなりパターンを減らしに行って少し詰まりました）

ただ、あくまで勉強として行うなら計算量を減らす方法も考えたいですね。
この問題ならいいですが、数字によってはループを何重にもにも回すと計算量が多すぎて間に合わなくなるケースが多々あります。
これもよく言及されていますが、500円の枚数と100円の枚数が決まった時点で50円の枚数も確定するので、そのことを利用してループを一つ減らせます。

ループ2回の例

package main

import "fmt"

func main() {
    var A, B, C, X, ans int
    fmt.Scan(&A, &B, &C, &X)
    for i := 0; i <= A; i++ {
        for j := 0; j <= B; j++ {
            rest := X - 500*i - 100*j
            if rest >= 0 && rest/50 <= C {
                ans++
            }
        }
    }
    fmt.Println(ans)
}

問題のサンプルを例に取ると、
例えば合計額が6000円のとき、
500円玉が10枚、100円玉が5枚というところまで確定すると、残額は500円です。
この時点で、50円玉の枚数は10枚ということが確定します。
ということは、2番めのループの時点で残額が0円以上、かつ使える50円玉の枚数で作れる金額が残額よりも大きければ条件を満たせます。
（↑の例では残額を50で割ってその数がC以下かどうかを条件としていますが、除算は割り切れなかったときの扱いに気をつける必要があります。この問題の場合、Xは50の倍数ということが条件に入っているので50で割り切れない場合を考慮する必要はありません）

さて、ここまではよく言及されていますが、調べても中々もう1回ループを減らしたパターンが見つかりません。
他の方の回答例を参考にしようにも、回答数が多すぎて該当のパターンの回答を探すのは容易ではありません、
だからこそこの記事を残しておこうと思いました。

ループ1回のパターン

さて、ざっくりと何をするかを説明します。

まずは500円玉を使う枚数を決めます。
そうすると、500円を使った枚数の残りの金額を100円と50円で作る必要があります。

ここで残額に対して100円をもっとも多く使った払い方と、100円をもっとも少なく使った払い方を考えます。
問題のサンプルだと500円を10枚使った場合、残額が1000円になります。（サンプルではB=40、C=50）
最も多く100円を使った場合10枚（50円玉が0枚）、最も少なく100円玉を使った場合は0枚（50円玉が20枚）になります。
100円玉が9枚になった場合、50円玉が2枚
100円玉が8枚になった場合、50円玉が4枚
…
という風に、100円玉が0〜10の間のパターンは100円玉を50円玉に変換していくことで満たせます。
つまりこの場合0〜10の11通り（0が含まれるので、10通りでないことに注意）が該当するパターンです。
500円玉の枚数を1枚ずつ増やしていって、それぞれについてパターン数を求め、その総和を出力すれば回答できます。
この場合は500円玉の枚数分しかループを行わないのでループ1回で行えます。

また、500円玉を使った時点で作りたい金額をオーバーしてしまったら、どうやっても目標金額を作ることはできないので、それ以降ループを続ける必要はありません。

100円玉の最大数

100円玉を最大にしたいので、なるべく多く100円玉を使うパターンを考えます。
500円を使った残額が100円の残り枚数分(100*B）以上の場合、100円玉の最大数はB枚
100*B円よりも残額が小さければ、残額を100で割った商が100円玉の最大数になります。
100円玉が10枚あって、500円を除いた残額が500円だとすると、当然最大の枚数は5枚になりますね。
ループ2回のときにも言及したとおり、ここで100円玉の枚数が決まると残った50円玉の枚数も決まります。

100円玉の最小数

100円玉を最小にしたいので、500円を使ったあとの残額をできるだけ50円玉を多く使って実現することを考えます。
残額が、50円玉を最大のC枚使ったときの金額（50*C円）より小さければ、残りすべて50円玉にすることができるので、残額を50で割った商が50円玉の枚数。このとき、当然100円玉は0枚です。
（合計額は50の倍数という条件があるので、50で割りきれないケースは考慮の必要なし）
一方、50*C円が残額以上だった場合、50円玉はC枚使うことになる…のですが、50円玉をC枚使ったときに余りが100の倍数になってないと当然100円玉で残りの金額を作ることができません。
なので、残額から50*C円を引いたときに、残額が100の倍数でない場合は50円玉をC-1枚にすれば100の倍数になります。（例えば、50円玉を5枚使ったときの余りが250円だったら、50円玉を4枚にすれば余りが300円になって100円玉3枚で実現できる）

実装例

以下、実装例です。
あまりきれいな実装ではないかもしれないのでもっとうまく書ける、というご指摘はコメントください。
(A,B,C,Xがここだけ小文字なのは最初に実装しようとしたときの名残なのでご容赦ください…）
100円玉の最大数と最小数を求めるところは似たような感じになったのと、長くなったので関数にして分離しました。
100円玉の枚数が決まったときの50円玉の枚数も一緒に出して、ちゃんと合計がX円になるチェックしています。

ループ1回

package main

import (
    "fmt"
)

func main() {
    var a, b, c, x, rest, ans int
    fmt.Scan(&a, &b, &c, &x)
    for i := 0; i <= a; i++ {
        if x < 500*i {
            break
        } else {
            rest = x - 500*i
        }
        // 100円玉を最も多く使った払い方と、最も少なく使った払い方を求める
        var maxh, minf int
        maxh, minf = max100ycoins(rest, b, c)
        var minh, maxf int
        minh, maxf = min100ycoins(rest, b, c)

        if 500*i+100*maxh+50*minf == x && 500*i+100*minh+50*maxf == x {
            ans += maxh - minh + 1
        }
    }
    fmt.Println(ans)
}

func max100ycoins(rest int, b int, c int) (int, int) {
    var maxh, minf int
    if rest >= 100*b {
        maxh = b
        rest -= 100 * b
    } else {
        maxh = rest / 100
        rest %= 100
    }
    if rest <= c*50 {
        minf = rest / 50
    }
    return maxh, minf
}

func min100ycoins(rest int, b int, c int) (int, int) {
    var minh, maxf int
    if rest >= 50*c {
        if (rest-50*c)%100 != 0 {
            maxf = c - 1
        } else {
            maxf = c
        }
        rest -= 50 * maxf
        minh = rest / 100
    } else {
        maxf = rest / 50
    }
    return minh, maxf
}

これでループ1回で実装できました。

おまけ

下記を満たす問題

• 合計値が決まっている
• 2つ以上の異なるものがある

これを見て何を思い出すかというと、なんとなくつるかめ算ですね。
https://chugaku-juken.com/turukame/
ループ1回のときの、最大値と最小値から数を求めるところの考え方はとてもそれっぽい気がしました。

こちらに記載のある、3段を2段にする、みたいなところが近い考え方なのかもしれません（適当）
https://chugaku-juken.com/sandan-turukame/

この辺はもっと詳しい人がきっと解説してくれるはず（他力本願）

この記事が誰か他の方の参考になれば幸いです。