CODE FESTIVAL 2016 Final E - Cookies

この記事は、CODE FESTIVAL 2016 Final E - Cookies の解説です。

クッキーを食べない場合、クッキーを焼く速度は常に \(1\) 枚/秒であるので、\(N\) 枚以上のクッキーを作るには \(N\) 秒かかる。

クッキーをちょうど \(1\) 回食べる場合、\(x\) 秒間で \(x\) 枚焼いて食べたとすると、\(N\) 枚以上のクッキーを作るには、\(x+A+\left\lceil\dfrac Nx\right\rceil\) 秒かかる。
かかる時間を最小化するような \(x\) はおよそ \(\sqrt N\) である。

クッキーをちょうど \(2\) 回食べる場合、\(x\) 秒間で \(x\) 枚焼いて食べ、その後 \(y\) 秒間で \(x\cdot y\) 枚焼いて食べたとすると、\(N\) 枚以上のクッキーを作るには、\(x+A+y+A+\left\lceil\dfrac N{x\cdot y}\right\rceil\) 秒かかる。
かかる時間を最小化するような \(x,y\) はともにおよそ \(\sqrt[3]N\) である。

クッキーをちょうど \(k\) 回食べる場合、\(N\) 枚以上のクッキーを作るのにかかる時間を最小化するには、およそ \(\sqrt[k+1]N\) 秒経過する毎にクッキーを食べるとよい。
そのとき全体でかかる時間はおよそ \(k\cdot A+(k+1)\sqrt[k+1]N\) となる。

上記の概算に \(N=10^{12},A=0,k=0,1,2,\cdots\) を代入すると、クッキーを食べる回数として考える必要があるのは \(0\) ～ \(30\) 回程度であることが分かる。
さらに、\(k\ge3\) のとき、クッキーを焼くのにかかる時間は \(4000\) 秒以下であることも分かる。

そういうわけで、\(k=0,1,2\) のときについては「およそ \(\sqrt[k+1]N\)」であるような値を全部調べることにして、\(k\ge3\) のときについては次のような DP を考える。

\(dp_{i,j}\) を「クッキーを食べた回数が \(i\) 回で、クッキーを焼くのにかかった時間が \(j\) 秒であるときの、存在しているクッキーの枚数の最大値」とする。
（「焼くのにかかった時間」には食べるのにかかった時間は含まれていないし、「存在しているクッキー」には既に食べたクッキーは含まれていない。）
これは \(dp_{0,j}=j\) という初期化ができて、\(dp_{i+1,j+k}=\mathrm{max}(dp_{i+1,j+k},k\cdot dp_{i,j})\) という遷移ができる（\(dp_{i,j}\) 枚のクッキーを食べた後、速度 \(dp_{i,j}\) 枚/秒で \(k\) 秒焼く）。
\(dp_{i,j}\) の値が全て得られたら、\(dp_{i,j}\ge N\) を満たす \(i,j\) に対して、\(A\cdot i+j\) の最小値を求めればよい。
（\(A\cdot i+j\) はクッキーを食べるのにかかった時間とクッキーを焼くのにかかった時間の和である。）