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

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

CADDi 2018 D - Harlequin (500 点)

一瞬 Nim に見えそうなのは確かにそんな気もするようなしないような...

問題へのリンク

問題概要

一本のりんごの木があり、 N 色のりんごが実っています。これらのりんごの  N 種類の色には 1 から  N までの番号が振られており、i 番の色のりんごは  a_i 個あります。

あなたとダックスフンドのルンルンは、以下の行動を交互に行います (あなたから始めます)。

  • 木から 1 個以上のりんごを選んで食べる。ただし、一度に選ぶりんごは全て異なる色でなければならない。

木から最後のりんごを食べた者を勝者とします。あなたとルンルンがともに最善を尽くすとき、どちらが勝つでしょうか?

制約

  •  1 \le N \le 10^{5}

考えたこと

段階を追って実験して行けば自然に解けるかなという気がする。とりあえず  N = 1 の状態を考えてみると

  •  a が奇数のとき、先手必勝
  •  a が偶数のとき、後手必勝

であることがわかる。なんとなく偶奇が関係ありそうな気持ちになる。続いて  N = 2 の場合を考えるとして、とりあえずまずは、 a = (1, m) の場合を考えてみる。

  •  m が奇数のとき、(1, 1) という取り方をして残りを偶数 1 個にすれば勝ちなので、先手必勝
  •  m が偶数のとき、(1, 0) という取り方をして残りを偶数 1 個にすれば勝ちなので、先手必勝

なんとなく、「残り全部偶数」にできたら勝ちな気がして来る。実際、たとえば

(4, 8, 2, 10, 6)

という状態にできたとして、相手がたとえば (0, 1, 1, 0, 1) みたいな削り方をして来たら、そっくりそのままお返しすることで

(4, 6, 0, 10, 4)

という風になって「残り全部偶数」という状態をキープできる。というわけでまとめると、

  • 初期盤面が「全部偶数」だったらどうしようもない。よって、後手必勝
  • 初期盤面に奇数が含まれていたら、それらを全部削って、偶数のみの盤面にすればよい。よって、先手必勝
#include <iostream>
using namespace std;

int main() {
    int N; cin >> N;
    bool exist_odd = false;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if (a & 1) exist_odd = true;
    }
    if (exist_odd) puts("first");
    else puts("second");
}