AtCoderログ：0096 - AGC 014 A

問題

問題文

高橋君と青木君とすぬけ君はそれぞれクッキーを $A,B,C$ 個持っています。
この $3$ 人はお互いにクッキーを交換することにしました。具体的には、以下の操作を繰り返します。
・$3$ 人は同時に、各々が持っているクッキーを半分ずつに分けて、残りの $2$ 人にそれぞれ一方を渡す。
ただし、誰かの持っているクッキーの個数が奇数個になったら、そこで操作を繰り返すのをやめます。
さて、クッキーの交換は何回行うことができるでしょうか。 ただし、無限に続けられる場合もあることに注意してください。

制約

・$1 \le A,B,C \le 10^9$

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

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #013

回答

回答1 (AC)

クッキーを交換する前のクッキーの枚数を $A,B,C$ $(A \le B \le C)$ 枚とすると、交換後のクッキーの枚数は $\frac{A+B}{2}, \frac{A+C}{2}, \frac{B+C}{2}$ $(\frac{A+B}{2} \le \frac{A+C}{2} \le \frac{B+C}{2})$ 枚になります。よって、交換前の最大個数と最小個数の差は $C-A$ 枚であるのに対し、交換後の最大枚数と最小枚数の差は $\frac{B+C}{2}-\frac{A+B}{2}=\frac{C-A}{2}$ 枚となることがわかります。

$A \ne C$ ならば差はちょうど半分になるので、交換を繰り返すことでいつかは交換が終了することがわかります。$C-A$ の最大値は $10^9-1$ なので、クッキー交換は高々 $\log_2(10^9-1)$ 回の操作で終了するので、具体的な値は計算すれば良いことがわかります。逆に $C-A=0$ のときは $A \le B \le C$ より $B$ も同じ値になるので、$A,B,C$ が偶数ならばこの操作は無限に続くこともわかります。

以上をまとめたコードは以下のようになりました。上記のような数学的な考察に気づかなくても、具体的な数値を計算することで無限ループの場合は見当が付くでしょうから、AC にするのはそこまで難しくないと思います。

agc014a-1.cpp

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  int answer = 0;
  while ( a%2==0 && b%2==0 && c%2==0 ) {
    if ( a==b && b==c ) {
      answer = -1;
      break;
    }
    int x, y, z;
    x = (b+c)/2;
    y = (c+a)/2;
    z = (a+b)/2;
    a = x;
    b = y;
    c = z;
    answer += 1;
  }

  cout << answer << endl;
}  

調べたこと

AtCoder の解説 → 公式解説

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

リンク

前後の記事

• 前の記事 → AtCoderログ：0095 - ABC 160 C
• 次の記事 → AtCoderログ：0097 - ABC 216 に参加しました