ABC99C - Strange Bank
Published on 2023-06-13Last Modified 2023-12-01
Table Of Contents
はじめに
個人的に比較的難しく、教育的な動的計画法の問題に出会ったので、メモを残しておく。 防備録的な色合いが強いので、私にとって明らかなことは書かない。
問題
思考
もし仮に、6冪の金額のみを用いることができるという制約なら単純な6進数変換の問題である。 しかし、本問では9冪の金額も用いることができるため、最適解が自明な貪欲法でない可能性が高い。
例えば、 「6冪と9冪のなかで今の金額に一番近い値を採用し、それを続ける」 という貪欲法を考える。 実はこの貪欲ではテストケースすら突破できない。(確認済み)
貪欲で解ける可能性が低そうなので、次に全探索を考えてみる。 自明な全探索は、log_6(N)ビット6進数とlog_9(N)ビット9進数によるビット全探索だと思われる。 計算量はO(6^{log(N)}9^{log(N)}) これは明らかに間に合わない。(実は少し工夫した全探索による解法が存在するので後述する)
解法
一回引き出したら口座に戻せないという制約上、部分問題に分割することができる。 すなわち、x円を引き出す最小手順がわかっていれば、もう少し大きな金額yに対して、y円を引き出す最小手順がわかる。
このことに気づくのは比較的用意だと思う。 さて、部分問題を精査していく。
私は次に述べる点に気づかなかったため、動的計画法を構築できなかったのだが、具体的な遷移は「1手前」を考えるだけで良い。 私はずっと、6冪と9冪が使えるということは、「6冪と9冪に引っかからないけど6や9の倍数である数」への遷移を毎回考える必要があると思いこんでいた。
つまりは、
dp[x]を計算するときに、min(dp[x-6]+1, dp[x-12]+2, dp[x-24]+4, ...)というようなことをしなければだめだと思っていたということだ。
しかし実際は、dp[x-12]やdp[x-24]の値はdp[x]に到着する前に計算されており、更にそれを織り込み済みでdp[x-6]が計算されている。
つまり、遷移のときに気にする必要があるのは1回で引き出せる金額の更新だけなのである。
結論として、
dp[x] = min(dp[x-diff]) (diff := {x | a <- N, 6^a, 9^a}, k < 0 (dp[k] = infinity), dp[0] = 0)
という遷移で計算可能である。 ある金額xに対して、高々logN通りの更新候補が存在するため、計算量はO(NlogN)で抑えられる。
また、全探索でも解くことができる。 「任意の引き出し方は、6進数成分と9進数成分に分解できる」 という事実を用いると、引き出す金額を2つに分割して、6進数/9進数表現に直したときのビットの総和が候補値になる。
分割の全探索がO(N)、各ケースO(logN)でx進数に変換できるから結局O(NlogN)で解くことができる。 上で述べた自明な全探索よりも少し工夫が入っている。
どちらが難しい解法かと言われると微妙だが、個人的には部分問題に分けるほうが自然かなと感じる。
追記
上の遷移式におけるNは、自然数全体の集合です。また、<-は集合の元であることを示す記号です。
参考文献