A - Cookie Exchanges

問題

思考過程

  • 愚直にシミュレーションしてループを検出したら-1を出力する
  • 初項を含まずにループする可能性があるので出てきた組み合わせをsetに入れていくのが確実か
  • ループすることと無限に続くことが同値であるのは可能な組み合わせが有限個であることからわかる
  • ループするか停止するまでの計算量は評価できるか？→できる。X+Y+Z=Sとすると自由度は2しかなく、109の2乗で抑えられる→この評価だと緩すぎる
  • もう少し賢くやれるだろうか？
  • 賢くとは→①上の方法をより賢く評価して間に合うことを示す②より賢い方法を考える
  • 勘だけど②がよさそうなのでまず②から
  • 手を動かす
  • しばらくやってよくわからず
  • よく考えると3数のMAX-MINは指数的に減少するのではないか→①の方針に切り替える
  • 大きい順にMAX,MID,MINとすると、MIDがMAX,MINの平均に近い場合はMAX-MIDとMID-MINがおよそ半分になり、MIDがMINに近い場合にもMAX-MIDがおよそ半分になると考えられる
  • 証明してから当初方針で実装するか証明なしで実装するか
  • 証明できそう。3数の大きい順にL,M,Sとおくと、一回交換したあとのL',M',S'は、 L' = \frac{L+M}{2}

M' = \frac{L+S}{2}

S' = \frac{M+S}{2}

よって、

L'-S' = \frac{L-S}{2}

となり、交換回数に対して指数的に減少する。よって、シミュレーション＋ループ検出による方法で、対数時間で解くことができると考えられる。

実装 Python3

#一回の交換をするための関数
def exchangeOne(x,y,z):
    return(((y+z)//2,(z+x)//2,(x+y)//2))
#全部偶数であるときにTrueを返す
def isAllEven(x,y,z):
    return(x%2==0 and y%2==0 and z%2==0)
A,B,C=map(int,input().split())
appeared=set() #一度現れた組み合わせを記録しておくための集合
appeared.add((A,B,C))
ans = 0
while isAllEven(A,B,C):
    A,B,C = exchangeOne(A,B,C)
    #ループを検出したら-1にしてシミュレーション終了
    if (A,B,C) in appeared:
        ans = -1
        break
    appeared.add((A,B,C))
    ans += 1
print(ans)

Submission #2825945 - AtCoder Grand Contest 014 18msでACです。

実装2 C++

Pythonで書けるものをC++でも書けるようにするために練習。

#include<iostream>
#include<algorithm>
#include <tuple>
#include <set>
using namespace std;

std::tuple<int,int,int> exchange(int x,int y,int z) {
    return std::make_tuple((y+z)/2, (z+x)/2, (x+y)/2);
}
bool isAlleven(int x,int y,int z) {
    return (x%2==0)&&(y%2==0)&&(z%2==0);
}

int main() {
    int A,B,C;
    cin >> A >> B >> C;
    std::set<std::tuple<int,int,int>> appeared;
    appeared.insert(std::make_tuple(A,B,C));
    int ans=0;
    while(isAlleven(A,B,C)) {
        std::tuple<int,int,int> tuple = exchange(A,B,C);
        A=std::get<0>(tuple);
        B=std::get<1>(tuple);
        C=std::get<2>(tuple);
        tuple = std::make_tuple(A,B,C);
        if (appeared.find(tuple) != appeared.end()) {
            ans=-1;
            break;
        }
        appeared.insert(tuple);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

tupleとかsetの存在確認とかに苦戦しつつ何とか書きあがると、なんと1msで終了。やっぱり速いんですねえ。 Submission #2826138 - AtCoder Grand Contest 014