一瞬 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");
}

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

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

CADDi 2018 D - Harlequin (緑色, 500 点)

問題概要

制約

考えたこと