ABC116 B - Collatz Problem

問題はこちら atcoder.jp

方針

「コラッツの問題」を題材にした問題です。私は数学には詳しくないので名前は知りませんでしたが，これを題材にした入試問題を見たことがあります。

例を見れば分かりますが， になった後は の繰り返しになっています。どのような に対してもこうなるというのが「コラッツの問題（予想）」の主張で，これを証明なしに用いてコードを書いてしまいました。

AtCoderの解説PDFでは， を順番に求めていく方法が本解となっています（そりゃそうだ）。ちょうどコード例は掲載されていなかったので，近いうちにこちらの方法でのコードを追記しておきます。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int s;
    cin>>s;
 
    vector<int> a(1000000);
 
    int result=0;
    a[0]=s;
 
    if(a[0]==1 || a[0]==2){
        result=4;
    }else{
        for(int i=1; i<1000000; i++){
            if(a[i-1]==1){
                result=i+1;
                break;
            }
            if(a[i-1]%2==0){
                a[i]=a[i-1]/2;
            }else{
                a[i]=3*a[i-1]+1;
            }
        }
    }
    
    cout<<result<<endl;
}