CODE FESTIVAL 2016 FINAL E - Cookies (1000(500))

満点解法は全く思いつかなかったので解説を読んで書いた。クッキーを焼いている区間の積が最終的なクッキーの枚数になるのに気付かなかったので駄目。

解説を読んだ上でもlong longのオーバーフローなどの実装上難しい点があった。

部分点実装(多分嘘)

$ memo[i][j] で時間iまでにj枚のクッキーを持っていられるかどうかをメモする

$ memo[i][j] からは$ memo[i-a-k][\lceil n / i \rceil] (2 \le k \le i - a) を参照し、一個でもtrueならtrue

気持ち高速化するため、$ memo[i] の中で最大のjが今調べてるクッキーの枚数以上かつ結果がtrueなら、今調べてる以上の枚数を作れるので今の結果もtrueとして返す

最悪$ 10^6 \times 10^6 = 10^{12}でMLE/TLEかもと思ったが通った

逆方向でやると、部分点解法みたいに計算量削減できたはず

計算量は不明

解説の満点解法

クッキーを食べる回数cは$ 0 \le c \le 40と決めつけて良い

40は$ 2^{40} \ge 10^{12}から

$ a = 0とした時、$ n = b^cの場合に$ b * cがn枚焼き上がるのにかかる時間であり、$ b = c = \log nの時に最小となる

$ a \ne 0の場合、更に$ (c-1) * aの時間がかかるので、cをそれ以上大きくしても全体の時間が増えてしまう

もしかしたら小さいn(4以下位?)では違うかも?

作れる枚数は各区間の積なので、区間の差は高々1になる

区間の長さとして、c＋1乗した時にnを超える最小の数sを二分探索で求める

$ (10^{12})^2 \gt 2^{64}なので単純にpow(s, c+1) >= n比較しようとするとオーバーフローする

対数を使って(c+1) * log(s) >= log(n)で比較するとオーバーフローしない

doubleの精度は53bitで$ 2^{53} \gt 10^{12}なので対数で比較しても精度は落ちていないはず

可能な限り多くの区間で長さを1削る

区間の長さの合計に待ち時間のaをc回足し、すべてのcの中で最小の物が答え

クッキーを食べる回数のループは$ O(\log N)

区間の長さの二分探索がそれぞれ$ O(\log N)

区間の内、いくつについて1短くできるか調べるのが$ O(\log N)

二分探索で求めれば$ O(\log \log N)になりそう

以上だけだと$ O(\log^2 N)なので、解説が$ O(\log^3 N)ということはおそらくlogをもとめる計算量が$ O(\log N)なのだろう