AtCoderログ：0115 - ABC 116 B

問題

問題文

数列 $a=\{a_1,a_2,a_3, \ldots \}$ は、以下のようにして定まります。
・初項 $s$ は入力で与えられる。
・関数 $f(n)$ を以下のように定める: $n$ が偶数なら $f(n)=n/2$、$n$ が奇数なら $f(n)=3n+1$。
・$i=1$ のとき $a_i=s$、$i>1$ のとき $a_i=f(a_{i−1})$ である。
このとき、次の条件を満たす最小の整数 $m$ を求めてください。
・$a_m=a_n~(m>n)$ を満たす整数 $n$ が存在する。

制約

・$1 \le s \le 100$
・入力はすべて整数である。
・$a$ のすべての要素、および条件を満たす最小の $m$ は $1000000$ 以下となることが保証される。

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#020]

回答

回答1 (AC)

数式が多いため難しく見えますが，要は数列を計算し、はじめて同じ値になるようなインデックスの値 $m$ を求めれば良いです。コードは以下のようになりました。今回は $m \le 1000000$ であることがわかっているので、数列に登場したかどうかを配列でチェックしています。

abc116b-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int s;
  cin >> s;

  int counter = 1;
  vector<bool> c(1000001,false);
  c.at(s) = true;
  while ( true ) {
    if ( s%2==0 ) {
      s = s/2;
    } else {
      s = 3*s+1;
    }
    counter += 1;
    if ( c.at(s)==true ) {
      break;
    } else {
      c.at(s) = true;
    }
  }
  cout << counter << endl;
}

なお、設問が使用した関数 $f(n)$ に対し、どのような初期値 $s$ を入力しても数列の値が最終的には 1 になる (より正確には 4→2→1→4→... というループになる)ことが予想されています (Collatz 予想(または角谷予想))。つまり、従って、このループ以外では数列に同じ値が登場しないことがわかります (同じ値が登場したらそこでループしてしまい、4→2→1のループにならないため)。

調べたこと

AtCoder の解説 → ユーザ解説

計算した値を set 型変数に保持していました。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0114 - ABC 094 B
• 次の記事 → AtCoderログ：0116 - ABC 149 C