AtCoder AGC 014 A - Cookie Exchanges (灰色, 300 点)

何回も何回も操作すると同じことになる系

問題へのリンク

問題概要

3 つの整数 があたえられる。以下の操作を行えなくなるまで繰り返す:

• 3 つの整数の中に奇数が 1 個でもあったら終了
• すべて偶数だったら を に置き換える

操作を何回行うか？無限に行う可能性がある場合は -1 を出力せよ。

考えたこと

ちょっと適当な場合を試してみて感触を確かめてみる。まず全部同じ数値だったら無限に繰り返されることが見て取れる:

(6, 6, 6) -> (6, 6, 6) -> (6, 6, 6) -> ...

ちょっと変えてみる。

(6, 8, 10) -> (7, 8, 9) end

すぐ終わった。ちょっと差を広げてみる

(8, 16, 32) -> (12, 20, 24) -> (16, 18, 22) -> (17, 19, 20) end

という具合。ちょっと眺めてみると

• 三つの数の合計値は不変である！！！(こういうのを不変量とよぶ、しばしば考察過程において重要な概念)
• 三つの数は操作を行うごとに均等化されていく

という様子をみてとることができる。このことから

• 最初から三つの数が等しかったら -1
• そうでなかったら、いつかは (a, a+1, ?) みたいに三つの整数の中に差が 1 のところが発生する。そのうちのどちらかは奇数なので終了する

という感じになりそうだなと思う。

必要回数を見積もる

そして、十分多い回数シミュレーションすればよさそうとはわかったが、どのくらいの操作回数がかかるのかを見積もってみる。実は簡単で、

• (8, 16, 32)：最大と最小の差が 24
• (12, 20, 24)：最大と最小の差が 12

という具合に、「最大と最小」の差は必ず半減する。よって、 オーダーの試行で十分なのだ。30 回くらいで十分。以下の実装ではとりあえず 1000 回回してる。1000 回回しても終わらなかったら -1 と判断している。

#include <iostream>
using namespace std;

long long A, B, C;
int solve() {
    for (int i = 0; i < 1000; ++i) {
        if (A & 1) return i;
        if (B & 1) return i;
        if (C & 1) return i;
        long long tA = (B + C) / 2;
        long long tB = (C + A) / 2;
        long long tC = (A + B) / 2;
        A = tA, B = tB, C = tC;
    }
    return -1;
}

int main() {
    cin >> A >> B >> C;
    cout << solve() << endl;
}