ABC155 – E「Payment」

▲「お兄ちゃん、この前の ABC155 難しくなかった？」

■「ああ、難しかったね。色々がんばって、なんとか解法は理解できたけど、時間内に解ききるのは相当ハードル高かったね」

▲「うんうん。それで、E 問題の『Payment』の解き方が知りたいんだけど」

■「E 問題？　D 問題は大丈夫なの？」

▲「D 問題も大丈夫じゃないけど、解説 PDF に DP って書いてたから解けるかもと思って」

■「なるほど。じゃあ、解いてみようか」

ABC155 – E「Payment」

■「1 円、10 円、100 円、1000 円、……の紙幣を使って N 円以上支払って差額を受け取るんだね。そして、支払う紙幣と受け取るお釣りの紙幣の合計枚数の最小値が知りたい、と」

▲「サンプル 1 の 36 円だと、ぴったり 36 円払うと支払いが 9 枚でお釣りが 0 枚で合計 9 枚になるね」

■「そうだね。ちょっと多めに 40 円払って 4 円のお釣りをもらうと、支払いが 4 枚でお釣りが 4 枚の合計 8 枚になるから、こっちの方が良い。合計 8 枚以下にする方法は無いみたいだから、8 が答えだね」

▲「これ、どうやって考えるの？」

 

 

■「上の桁から考える方針と、下の桁から考える方針があるけど、とりあえず上から見てみようか」

▲「上からってことは、サンプル 1 の 36 円だと、10 円札からってこと？」

■「うーん、どうかな？」

▲「どうかな？って……　あ、一応 100 円札を使う可能性も考慮するってこと？」

■「うん。36 円ならさすがに大丈夫だけど、99 円だと 100 円払うのが最適だからね」

▲「じゃあ、 036 円支払うとするね。まず 100 円札について、払わないパターンと 1 枚払うパターンがあり得るね」

■「そうだね。もちろん、2 枚使うパターンはあり得ないよね。そのままお釣りで帰ってくるから」

▲「たまに余分に百円玉を出しちゃって『この百円玉はいらないです』って返されちゃうことあるよね」

■「僕もやったことあるけど、それは置いといて。まず、100 円札を使わないパターンを考えよう」

▲「はーい」

■「10 円札は支払いで何枚使う可能性がある？」

▲「えっと、36 円だから、 3 枚使うパターンと、4 枚使ってお釣りをもらうパターンがあるね」

■「そうだね。つまり、『 3 枚払う』か『 4 枚払う』かの 2 通りだね」

▲「じゃあ 3 枚払う方が少ないから良いね！ってなったらダメなんだよね」

■「うん。3 枚払うと『その桁までぴったり払った状態』で、4 枚払うと『その桁まで 1 多く払った状態』になって、この違いが下の桁に影響するから、ちゃんと区別しておかないといけない」

▲「繰り下がりがあるか無いかってことだね。次は 1 の位？」

 

 

■「いや、その前に 100 円札を 1 枚払った場合を考えよう」

▲「100 円札を 1 枚払った場合、10 の位はお釣りで帰ってくるよね？」

■「そうだね。何枚帰ってくる？」

▲「36 円に 100 円払ったら、10 円札が 6 枚と 1 円札が 4 枚返ってくるよね。だから、6 枚？」

■「今は『 100 円札を 1 枚払った』という状態を考えているけど、まだ下の桁を見ていないから、もしかしたら 1 円札も何枚か払っているかもしれない。もし 1 円札を 6 枚払って合計 106 円払ってたら、お釣りの 10 円札は何枚？」

▲「70 円だから 7 枚になるね」

■「そう。だから、100 円札を 1 枚払った状態だと、返ってくる 10 円札は 7 枚か 6 枚」

▲「これも、下の桁への影響が違うから別々の状態になるの？」

■「うん。100 円札を 1 枚払った状態で、10 円札を 7 枚受け取れば、その時点では 30 円払ったことになる。つまり『その桁までぴったり払った状態』だ。一方、10 円札を 6 枚受け取れば、40 円払ったことになるから、『その桁まで 1 多く払った状態』になる」

 

 

▲「てことは、036 円払う場合、まず 100 の位について、0 枚払って『ぴったり状態』に行くか、1 枚払って『 1 多い状態』に行くかっていう選択肢があるってことだよね」

■「うん」

▲「それで、100 の位で『ぴったり状態』になってる場合は、10 の位で 3 枚ちょうど払って『ぴったり状態』に行くか、4 枚払って『 1 多い状態』に行くかっていう選択肢があるんだね」

■「うんうん」

▲「100 の位で『 1 多い状態』になってる場合は、7 枚ちょうど貰って『ぴったり状態』に行くか、6 枚だけ貰って『 1 多い状態』に行くかっていう選択肢がある！」

■「そのとおり。じゃあ、10 の位で『ぴったり状態』になるためには最低何枚やり取りする？」

▲「10 の位でぴったり状態ってことは、『 0 枚払う＋ 3 枚払う』か『 1 枚払う＋ 7 枚貰う』だから、枚数が少ないのは 3 枚！　これはどっちも 30 円払うのと同じだね」

■「正解。じゃあ、10 の位で『 1 多い状態』に行くには？」

▲「『 0 枚払う＋ 4 枚払う』か『 1 枚払う＋ 6 枚貰う』だから、4 枚が最小！」

■「正解。じゃあ、この調子で 1 の位も考えよう」

 

 

▲「 1 の位は “6” だから、こういう表になるかな？」

上の桁の状態＼今の桁の状態	ぴったり状態	1 多い状態
ぴったり状態（すでに 3 枚やり取りしてる）	6 枚払う	7 枚払う
1 多い状態（すでに 4 枚やり取りしてる）	4 枚貰う	3 枚貰う

■「そうだね。この表によると、1 の位で『ぴったり状態』に行くためには、3+6=9 枚か、 4+4=8 枚が必要だね」

▲「じゃあ、最小は 8 枚だ！」

■「これがサンプル 1 の考え方だね。もちろん、1 の位では必ず『ぴったり状態』じゃないとダメだね」

▲「こんな感じで DP していけばいいんだね」

■「じゃあ、DP について考えていこう」

 

 

▲「DP 配列の状態はこんな感じ？」

$dp[i][0]=$ 上から i 桁目まで処理して『ぴったり状態』になるためにやり取りする最小枚数

$dp[i][1]=$ 上から i 桁目まで処理して『 1 多い状態』になるためにやり取りする最小枚数

■「そうだね」

▲「新しい桁を処理するときに、やり取りする紙幣の枚数はこうだよね？」

$i-1$ 桁目の状態＼$i$ 桁目の状態	ぴったり状態	1 多い状態
ぴったり状態（$dp[i-1][0]$ 枚やり取りしてる）	$N[i]$	$N[i]+1$
1 多い状態（$dp[i-1][1]$ 枚やり取りしてる）	$10-N[i]$	$9-N[i]$

■「この表の、N[i] っていうのは、N の上から i 桁目ってことだよね」

▲「うん。最初に付け足した最上位の “0” が 0 桁目かな」

■「じゃあ、遷移の漸化式を書いてみよう」

▲「$i$ 桁目の各状態について、枚数が少ない方を採用するから……　こう！」

$dp[i][0]=\min (dp[i-1][0]+N[i], dp[i-1][1]+10-N[i])$

$dp[i][1]=\min (dp[i-1][0]+N[i]+1, dp[i-1][1]+9-N[i])$

■「そして、出力は？」

▲「出力は最後の桁まで処理して『ぴったり状態』になるための最小枚数だから、$L$ 桁あるとしたら $dp[L][0]$ だね。」

■「良さそうだね。じゃあ、コーディングしてみようか」

 

 

▲「実際に $N$ の頭に “0” をつけなくても、$dp[0][0]=0, dp[0][1]=1$ っていうのが分かってたら大丈夫だよね」

■「そうだね。その場合、最上位を 0 桁目とするなら、さっきの遷移式の $N[i]$ が $N[i-1]$ に変わるね」

▲「じゃあそれでいこう！　……これで大丈夫かな？」

 

■「うん。AC したね」

▲「やったー！」

 

 

▲「ところで、これっていわゆる桁 DP なの？」

■「うーん、どうだろう。桁をなぞっていく DP といえばそうだけど、よくある桁 DP は『 N 以下の数のうち……を満たすものを数えよ』っていうタイプで、桁をなぞるときに『その桁まで N と一致しているかどこかで緩められたか』という状態を持つから、ちょっと違うような気もする」

▲「何言ってるのか分かんない」

■「EDPC の S 問題とかで典型的な桁 DP の練習をするといいかもね」

▲「 S 問題！　遠いよ〜」

■「DP 練習用の記事もあるから、焦らず少しずつ慣れていこう」