CPSCO2019 Session2 D - Two Piles(400)

D - Two Piles

概要

A枚のコインの山とB枚のコインの山がある。次のルールで2人ゲームを行い、最後に操作した人を勝者とする。先手勝ちならYes、後手勝ちならNoを出力せよ。

• 2山のうちコインがある山を一つ選ぶ。その山のコインの枚数をX枚とする。
• 各山から0枚以上のコインを取り去る。このとき取り去るコインの枚数はちょうどX枚とする。

制約

1 ≦ A, B ≦ 10^5

方針

2山のコインの数を(X, Y)と表記する。

(0, X)なら先手がX枚をまるまるとればよいので先手勝ち。

(X, Y)のとき、試しに(1, Z)にする手を考えてみる。(Z = Y-1 or X - 1)
すると後手が選べる手は(0, 1), (0, Z), (1, Z-1)の多くとも3通りだが、前者2つはすぐにその後先手に(0, 0)とされてしまうため選べない。よって(1, Z-1)を選択するしかない。
するとその後の先手は同じ理由で(1, Z-2)を選択するしかない。
よってゲームは(1, Z-1) → (1, Z-2) → … → (1, 0)→ (0, 0)と進行し、勝敗が決する。(1, Z)の勝敗は問題を解くカギとなりそう。

(1, Z)の勝敗を考えると(1, 0)なら先手勝ち、(1, 1)なら後手勝ち、(1, 2)なら先手勝ち…なので(1, 偶数)が先手勝ち、(1, 奇数)が後手勝ちとなる。

一般の(X, Y)に戻る。X, Yの偶奇で場合分けしてあげるとよさそう。
①(X, Y) = (偶数, 偶数)：先手が(X - (X - 1), Y - 1) = (1, Y - 1)とすることで、(1, 奇数)の状態で後手に手を回せるため、先手勝ち
②(X, Y) = (奇数, 偶数)：先手が(X - (X - 1), Y - 1) = (1, Y - 1)とすることで、(1, 奇数)の状態で後手に手を回せるため、先手勝ち
③(X, Y) = (偶数, 奇数)：先手が(X - 1, Y - (Y - 1)) = (X - 1, 1)とすることで、(奇数, 1)の状態で後手に手を回せるため、先手勝ち
④(X, Y) = (奇数, 奇数)：どのようにしても(偶数, 奇数)の状態で後手に手を回してしまうため、後手勝ち

解答

Submission #5383179 - CPSCO2019 Session2

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int A, B;
	cin >> A >> B;
 
	if(A % 2 == 1 && B % 2 == 1){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
}