競プロ記録

問題を解いた際に自分の復習用として使ってます

ARC 072 D問題 Alice&Brown

解説

まずこのようなゲーム系の問題は終了時から遡って考えていきます。 そこでゲームが終了する場面を考えてみると

(x, y) = (0, 0), (1, 0), (0, 1),(1, 1)

この4通りぐらいは自分で見つけることができるかと思います。
次にx, yが0~5の6x6の表を書いてみることにします。
そのマスには(x, y)の場面が回ってきた場合に負けならばL, 勝ちならばWとします。
するとあるマスからあるマスへはy=-2xかy=2x上のマスに遷移することはゲームのルールからわかります。 それでもし遷移できる箇所にLのマスがあれば勝つことができ、もしWしかならば負けということになります。(Wの先にはLがあるはずなので) したがってこの法則に従って表を埋めていくと

|x-y| <= 1 => Brown
|x-y| >= 2 => Alice

がわかるかと思います。

コード

#include <iostream>
using namespace std;

int main(void){
    long long x, y;
    cin >> x >> y;
    if(abs(x-y) <= 1){
        cout << "Brown" << endl;
    }else{
        cout << "Alice" << endl;
    }
    return 0;
}