けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 014 A - Cookie Exchanges (300 点)

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

問題へのリンク

問題概要

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

  • 3 つの整数の中に奇数が 1 個でもあったら終了
  • すべて偶数だったら  (a, b, c) (\frac{b+c}{2}, \frac{c+a}{2}, \frac{a+b}{2}) に置き換える

操作を何回行うか?無限に行う可能性がある場合は -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

という具合に、「最大と最小」の差は必ず半減する。よって、 \log オーダーの試行で十分なのだ。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;
}