AGC014 - A: Cookie Exchange

見当違いの考察で時間を溶かしてしまった整数？数学系？の問題．こういう問題解けるようになりたい．完璧には飲み込めていないが，似たような問題にぶつかったときにこの記事戻ってこれるように書き残しておく．

問題

• AGC014 - A: Cookie Exchange

思考過程

奇数が一つでもあれば 0 回というのは自明．全てが偶数の時にどうなるかを考える．考えたことを箇条書きで連ねておく．

• 全てが等しい時は無限ループで -1．
• 素因数分解をして各数に含まれる 2 の数がどう変化するか調べた．
• 2¹ を因子に持つ数が，3 つの数の内 1 or 2 個のとき，次で収束する．必ず（偶数 + 奇数）という計算が生まれるから．

などと考えていたが，結局

和を取るような操作で素因数分解を考えるのはナンセンスだった．和をとることで因子は次々に変化してしまう．数同士の積，除算を考えるときは素因数分解，因子について考えるのもありだと思ったが．和を考えているときに因子について考えるのはあまり意味がないのかもしれない

と感じた．

解説

• editorial

www.youtube.com

解くのに時間をかけた割に方針が的外れだったので解答を見て辛くなった．解答は以下の通り．

　
まず，

• 一つでもが奇数があれば 0 を出力．
• 3 つの数が等しい場合は無限に操作を行えるため，-1 を出力．

ということは簡単に分かる．

次に操作を行える場合を考える．各人の持っているクッキーの個数の集合を，

とすると、操作後の集合は

になる．よって， とすると，持っているクッキーの個数の最大と最小の差が

• 操作前： ，
• 操作後：

となり，操作を行うと最大と最小の差がちょうど になる．最大と最小の差が次第に詰まっていく（半分ずつになっていく）．

よって， ではない場合， として，操作を高々 回しか行わないことが分かり，愚直にシュミレーションすることで解ける（ の最大値と最小値の差を考えた時，入力としてあり得る「差の初期値の最大値」はせいぜい 程度（A = 1，C = 10⁹，これは奇数ですが目安として）である）．10 億（）を 2 で割り続けるとせいぜい 30 回くらいで 1 になる（C++ での整数除算）という感覚は覚えておきたいところ．

シミュレーションの例を下図に示しておいた．

操作をしていく中で最終的に「最大値と最小値の差が 1 になる」は，「クッキーの数に偶数と奇数が現れる」と同じであるため，そのときに操作を停止することになる．結局，この問題は最悪計算量 で解ける．

コードは再帰で書くと分かりやすい．

#include <iostream>
using namespace std;

int func(int A, int B, int C) {
    if (A%2 == 1 || B%2 == 1 || C%2 == 1) {
        return 0;
    }
    if (A == B && A == C) {
        return -1;
    }
    
    return func((B+C)/2, (C+A)/2, (A+B)/2) + 1;
}

int main() {
    // input
    int A, B, C;
    cin >> A >> B >> C;
    
    int ans = func(A, B, C);
    cout << ans << "\n";
    return 0;
}

整数系の問題を解くときの自分的方針

反省というよりは問題を解いてこういうパターンがあるのだと覚えるしかない．現段階で，自分が整数系の問題を解く時の考えるべき方針のようなものをまとめて見た．この問題に直接関係のないものも挙げている．

• 倍数判定 = 余りの計算
• それぞれの和をとるような場合，因数分解はあまり考えなくて良い（和を取った後には素因数が保存されないため）．
• 積・徐算を行う時は素因数分解とか因子を考えても良さそう．
• お互いの差を取るとき，差を取り続けて余りを更新するという操作は，最小公倍数を求めることと同じである（ユークリッドの互除法）．（ABC118 - Cで出題）（日本語が下手）
• 偶数＋奇数＝奇数，それ以外は偶数．
• 1 ターンの動作が決まっている（１移動するとか N 移動する）とかの問題は，偶奇を見るとそれが実現できるかどうか分かることがある．
• 10 億（）を 2 で割り続けてもせいぜい 30 回くらいで 0 になる（C++ での整数除算）．