【競プロ】1日1AC : AGC14 A問題

今日で3日目になります。今日の問題はこちら。

しばらくはC問題をやるつもりだと書きましたが、AGCが近いのでAGCの問題を持ってきました。

1 提出コードと考えたこと
- 1.1 ループの回数について
2 終わりに

提出コードと考えたこと

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

int main(){
    vector<int> A(50), B(50), C(50);
    cin >> A[0] >> B[0] >> C[0];

    int ans = 0;
    bool flag = false;
    for(int i = 0;i < 40;i++){
        if(A[i] % 2 != 0 || B[i] % 2 != 0 || C[i] % 2 != 0){
            flag = true;
            break;
        }
        A[i + 1] = (B[i] + C[i]) / 2;
        B[i + 1] = (A[i] + C[i]) / 2;
        C[i + 1] = (A[i] + B[i]) / 2;
        ans++;
    }

    if(flag) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}

ループ回数の部分については数学的な根拠を与えないと不完全なので後述します。

処理自体は問題文の操作をそのまま順番に行なっており、A, B, C さんのうち少なくとも1人のクッキーの個数が奇数になった時点でループを抜けます。

ループの回数について

今回の場合、操作が有限回で終わるなら、その回数はそこまで大きい値にはなりません。以下、公式の解説の内容を噛み砕いて書きます。

まず \( A = B = C \) の時、クッキーの枚数が偶数であれば、3人のクッキーの数はずっと変わりません。

次に \( A = B = C \) でない時を考えますが、\( A \leq B \leq C \) としてもいいはずです。（そうなるように配りなおせばいいだけ）
この時、1人が持つクッキーの最大枚数と最小枚数の差（以下、単に枚数差とします）は \( C - A \) です。

全て偶数枚として、ここで操作を行うと、それぞれが持つクッキーの枚数の集合は \[ \displaystyle \left\{ \frac{A+B}{2},\frac{A+C}{2},\frac{B+C}{2} \right\} \] です。（要素の値は右のものほど大きく、少なくとも1つは他と異なる値です）

よって、枚数差は \( \displaystyle \frac{C-A}{2} ( \ge 1) \) になっています。先程の値の \( 1/2 \) です。すなわち \( n \) 回操作すると枚数差は、初めの \( 1/2^n \) 倍になります。（操作のたびにクッキーの枚数を \( A,B,C \) と置き直すことで確認できる）

十分な回数操作が可能であるとすると、操作後のクッキーの枚数差は0に近づきますが、この値は1以上でなければいけません。すなわち \[ \displaystyle \frac{C-A}{2^n} < \frac{10^9}{2^n} (\ge 1) \] より \( \displaystyle n \le \frac{9}{\log_{10}{2}} (\approx 29.9) \) となるので操作可能回数は高々30回になります。（ソースコードを書いた時点ではここまで見積もってなかったので40回にしていますが）