皆様どうも、ばるとーくです！
今回はこちらの問題「Collatz conjecture」を解説していこうと思います！
問題
問題文
関数 $f(n)$ を以下のように定義する。
$$f(n) = \begin{cases} n/2 & (n \equiv 0 \pmod{2}) \\ 3n+1 & (n \not\equiv 0 \pmod{2}) \end{cases}$$
与えられた正の整数 $N$ を $n$ の初期値として、「$n$ を $f(n)$ で置き換える」操作を繰り返す。
これを $1$ 回以上行ったとき、初めて値が $1$ となるまでには何回の操作を必要とするか求めよ。
ただし、$10^{100}$回以内の操作で $1$ に到達しない場合はinfinityと出力せよ。制約
- $1 \le N \le 3000$
- $N$ は整数
解いてみたい方はこちら↓
解説
この問題は有名な「コラッツ予想」をモティーフにして作りました。
コラッツ予想とは
このようなことを予想する問題です。
適当な自然数を1つ思い浮かべる。
「偶数なら2で割り、奇数なら3を掛けて1を足す」という操作を繰り返す。
最初の数がどんな数でも、計算を繰り返すうちに必ず1になる。
この問題は、コンピュータを用いた証明により $2^{68}$ 以下の数で正しいことが立証されているものの、未だ未解決な問題です。1
今回は、この「偶数なら2で割り、奇数なら3を掛けて1を足す」という部分の表現を関数として表していたわけです。
「操作結果が1になるまでに何回かかるか？」というところがこの問題独自の点です。
この問題で考えるべきポイントは3つです。
- 実装方法
infinityの場合はどんなときか- "$1$" の処理
始めに実装方法ですが、シンプルにwhileループを組むだけで問題ありません。
（yukicoder解説ページの想定解を参考にしてください）
関数 $f$ の根幹はif文で作ることができるでしょう。
また、後述しますが、この関数 $f$ はコード内で2回使用するため、関数化しておくと実装が少し楽になるでしょう。
次に、infinity の場合、すなわち、「$10^{100}$ 回以内の操作で $1$ にならないとき」はどんな時なのかについてです。
結論から言うと、それに該当する場合は今回の制約上ありません。ただのフェイク情報というわけです（この辺が共テ仕草です）。
実際、今回の制約内での最大の答えが $N=2919$ のときで、その計算結果は $216$ となります。
※参考:測定に使用したコードとその結果(Github)
最後に1の処理です。問題文の制約として、「操作を $1$ 回以上適用したとき」というものがあるため、1を入力すると0が出力されるようなコードはWAとなります。
具体的には、（想定誤解法として用意していますが）このようなコードはWAとなります。
※疑似言語を使用しています
整数型 n
while(n != 1){
●関数fの処理を行う
}
●答えを出力
これを回避する方法として、想定解では、「whileループを回す前に1回だけ関数 $f$ の処理を回しておく」方式を採用しています。（もちろん他にも解法はあるはずです。）
この方式を採用するなら、先ほど言った通り、関数 $f$ の処理を2回書く必要があるので、関数化しておくと便利でしょう。
以上で解説を終わります。
想定解はyukicoderの解説ページにありますので、参考にしてください。
今回はPythonも主が書きました...！（実はちょっとだけ使えるマン）
