ゲーム問題が苦手すぎる・・・・

CPSCO2019 Session2 D Two Piles

問題概要

枚のコインがある 1 つの山と、 枚のコインがある 1 つの山がある。 この2つの山を使ってAliceとBobがゲームをする。Aliceを先手として、2 人は以下の操作を交互に繰り返す。

• 1枚以上のコインがある山を選ぶ。この山の枚数をとする
• その後2つの山から合計で枚のコインを取り除く

どちらの山にもコインがなくなったときの操作を終了し、最後に操作した人が勝者となる。

問題リンク

https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_d

制約

考察

• サンプルだけでは分からないので実験してみる

• 以下に例と最適に行動したときの遷移を示す。
• 例1 初期状態が = の時、この後は → となり勝者はBob
• 例2 初期状態が = の時、この後は → → となり勝者はAlice
• 例3 初期状態が = の時、この後は → → → となり勝者はBob

• どうやら片方の山の枚数が1枚になるとその後は1枚ずつ取るのが最適になるっぽい
• そして片方が1枚になった時、もう片方の枚数が奇数ならば、相手に負けの状態を押し付けられるのでAliceが勝者となる（1枚の山の枚数も数えて残り枚数が偶数ならば勝利と考えても良い）（実験より分かったこと）ということで、先手が最初に片方の山を1枚にする操作をしてみる。
• ここではまず、山を選び、が1枚になるように取り（つまり枚取る）、からは1枚取るとする（を1枚にしてから1枚取る操作も同様に説明できる）
• この時取るコインの枚数は枚となり、山を選んだ時に取る枚数の条件である枚を 満たしている。さて、この時、山が1枚になっているので残りは交互に1枚ずつ取ることになる。これは残り枚数の奇偶で判定できる。上述したように、残り枚数は山の1枚と山の枚なので、残り枚数の合計は枚となる。つまり、操作後の枚が偶数の場合、相手に負けの状態を押し付けられるので先手（Alice）は勝利できる。一方奇数の場合は先手は敗北する。
• 山を選ぶ場合も考慮すると、最終的にはとの奇偶判定をすれば良いことになる
• 以上をまとめると、とのどちらかが偶数ならば先手必勝、それ以外は後手必勝となる。

ソースコード

※マクロは使っていないので無視してください

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;
typedef pair<int, int> pii;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 1005
const ll INF = 1e9 + 7;

int main() {

	int a, b;
	cin >> a >> b;

	if ( (a % 2) == 0 || (b % 2) == 0)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}