けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CPSCO 2019 session2 D - Two Piles

AtCoder 有志コン ゲーム パリティ 競技数学色強め

これ好き！！！
しばらく、CPSCO の良さげな問題を解説するターンをやってみたい。

問題へのリンク

問題概要

石の山が 2 個あって、それぞれ初期状態では A, B 個積まれている。ここから先手と後手が交互に

  • 残っている石の山から 1 つ選び、その石の個数を X とする
  • 残っている石の山から、それぞれ x, y 個の石を、 x + y = X を満たすようにとる (このとき、 x, y はそれぞれの石の山の個数以下である必要がある)

というのを繰り返す。取り除ける石がなくなった方が負けである。双方最善を尽くしたときに、どちらが勝つか？

制約

  • 1 \le A, B \le 10^{5}

考えたこと

ゲームな問題で一番簡単に解けるパターンは「ありうる盤面の個数が 10^{7} 個とかそんなもんなので、何も考えずに DP すれば解けてしまう」というもの。例として以下の問題など。

atcoder.jp

今回はありうる状態が (A+1)(B+1) で最大で 10^{10} 個くらいあるのでそこまで単純には行かない。こんなときに一つ有力な方法として「この局面は勝ち、この局面は負け」というのを積み上げていく、というのがある。考え方として

  • 詰んだ盤面は負け (今回で言えば (0, 0) は負け)

から出発して

  • 今ある盤面からどんな手を打っても相手に勝ち盤面を与えてしまうときは「負け」
  • 今ある盤面からある手を選べば相手に負け盤面をあたえられるときは「勝ち」

というもの。それをしていくうちにやがて解けたりする。その際に、パリティ (偶数奇数) に着目すると幸せになれることが多い。今回まず

  • (0, 0) は負け (自明)
  • (0, 1) は勝ち (1 を取って相手に渡せば終わり)
  • (0, 2) も勝ち
  • ...
  • (0, x) も勝ち

ということがわかる。

(1, x) の場合

この調子で次は

  • (1, 1) は何やっても相手に勝ち盤面を渡すので負け
  • (1, 2) は 1 を選んで 2 から 1 を削れば (1, 1) が残る。この負け盤面を相手に渡せるので勝ち
  • (1, 3) は 1 を選んでも 3 を選んでも相手に勝ち盤面を渡してしまうので負け
  • ...
  • (1, 奇数) は負け
  • (1, 偶数) は勝ち

ということがわかる。

(偶数, 奇数), (奇数, 偶数), (偶数, 偶数) の場合

次にわかりやすいのが、

  • (奇数, 偶数) は、奇数を 2n+1 とすると、奇数の山から 2n 個、偶数の山から 1 個とれば (1, 奇数) にできて、負け盤面を相手に渡せるので勝ち
  • (偶数, 奇数) も同様に勝ち

ということがわかる。さらに

  • (偶数, 偶数) も、左の偶数を 2n とすると、左から 2n-1 個、右から 1 個とれば (1, 奇数) にできて、相手に負け盤面を渡せるので勝ち ( (0, 0) だけ例外)

(奇数, 奇数) の場合

残ったのは (奇数, 奇数) の場合である。実はもう簡単で、

  • (奇数, 奇数) の場合は、どうやっても、取り除く石の個数の合計が奇数なので、「一方から偶数個、他方から奇数個」の石を取り除くことになる。
  • このとき残るのは (偶数, 奇数) か (奇数, 偶数) か (0, 奇数) か (奇数, 0) になる。いずれも勝ち盤面を相手に渡してしまうことになるので、負けである

まとめ

以上をまとめると、石の山が 1 個しかない場合 (一方が 0 個) を除いて考えると、

  • (奇数, 奇数) は負け
  • それ以外は勝ち

ということになる。

#include <iostream>
using namespace std;

int main() {
    int A, B; cin >> A >> B;
    if (A % 2 == 1 && B % 2 == 1) cout << "No" << endl;
    else cout << "Yes" << endl;
}