全国統一プログラミング王決定戦 エキシビジョン：F - コラッツ問題

問題

https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e

考え方

サンプル2から f(1789997546303)=1000 であることが分かっているので、これを利用する。

f(N)=P を満たす N を memo_P とすると f(memo_{1000}) = 1000 である。この結果の両辺に -1 すると

f(memo_{1000}) - 1 = 1000 - 1 = 999

となる。左辺は X の偶奇によって仮定の式を適応することができて memo_{1000} は奇数であるから

f(memo_{1000}) - 1 = f(3 * memo_{1000} + 1) + 1 - 1 = f(3 * memo_{1000} + 1)

となる。まとめると

f(3 * memo_{1000} + 1) = 999

となるから、これによって memo_{999} = 3 * memo_{1000} + 1

となることが分かる。偶数の場合も同様だが、memo_{998} の結果を求めてみよう。

f(memo_{999}) = f(5369992638910) = 999 であり X = memo_{999} は偶数である。この両辺に -1 すると

\displaystyle f(memo_{999}) - 1 = f(\frac{memo_{999}}{2}) + 1 - 1 = f(\frac{memo_{999}}{2}) = 998

であることから \displaystyle memo_{998} = \frac{memo_{999}}{2} であることが分かる。

このようにして memo_P から memo_{P-1} の結果を得ることができるので memo_{1000} から順番に memo_{1} まで求めることができる。

Submission #4347375 - 全国統一プログラミング王決定戦 エキシビジョン

どこに着目して考察するべきだったか

何が求められているか整理するとサンプル2の両辺から-1をすることで求めたい値を得ることができることが分かる。

何がバグっていたか

得た知見(典型ポイント)

類題

雑記

ちょっと冗長になってしまった...