ABC182 Valid Payments
- 問題
- 解法
「同じ硬貨を使わない」というのを「同じ桁が同時に非零にならない」と読み替える。つまりY - X = Z (Y : 支払い、Z : お釣り) だと考えた時に、a0 < a1 < ... < a(n-1) かつ a(i+1) % ai = 0が成り立ってるので、各硬貨の使用枚数の上限が決まっていて、これをその桁で取れる最大の値と考える。
引き算は考えにくいので、Y = X + Z で考える。
条件「同じ桁が同時に非零にならない」を満たすような Y, Zの定め方を求めればいいが、これは桁dpで解ける形。
自分の実装では Zi = 0 の場合と Zi != 0 の場合に分けて考えたが、Yi = 0 と Zi = 0 の場合に分けてる人も多そう。(ZiはZのi桁目)
どちらにせよ、下の桁からの繰り上がりと合わせて考えることで、この桁からの繰り上がりが発生するかどうかが決まるので、注意深く場合分けすれば良い。
例えば、Zi != 0 の場合に Xi = 0 で下から繰り上げがないなら、どう頑張ってもZi = Yi になるので遷移できないので気をつける必要がある。
- 提出
