staircase nim の流れで

問題概要

$N$ 個の石の山が左から順に一列に並んでいて、各山には $a_1, a_2, \dots, a_N$ 個の石が積まれている。初期状態では

$a_1 \le a_2 \le \dots \le a_N$

を満たしている。今先手と後手が交互に

石が 1 個以上ある好きな山を 1 つ選んで
何個かの石を取り去る
ただし $a_1 \le a_2 \le \dots \le a_N$ という状態を維持しなければならない、この条件を満たす限りは任意個数の石を取り去ることができる

という条件でプレイする。先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

また先手必勝の場合は、最初にとるべき石の個数として考えられる最小値を求めよ。

制約

$1 \le N \le 50$

考えたこと

実は

隣の山に石を渡していく Nim

と同じ問題になっている。具体的には、例えば

{3, 9, 10} -> {3, 7, 10}

のように石を減らす操作は、隣り合う石の個数の差でみると

{3, 6, 1} -> {3, 4, 3}

というように、「左隣の山から石を何個か選んで右隣の山に石を移す操作」と思うことができる。そして「単調非減少」という条件は、石の個数の差の世界では「どの山の石の個数もマイナスにはならないように」というのにピッタリ対応する。

よって隣り合う石の個数で見た世界において、必勝法は

$a_n$ ^ $a_{n-2}$ ^ $\dots$ = 0

となることであり、実際に取るべき石の個数も比較的容易に復元できる。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

class StoneGameStrategist {
public:
    string play(vector<int> a) {
        vector<int> b;
        b.push_back(a[0]);
        for (int i = 0; i + 1 < a.size(); ++i) {
            b.push_back(a[i+1] - a[i]);
        }
        int nim = 0;
        for (int i = b.size() - 1; i >= 0; i -= 2) nim ^= b[i];
        if (nim == 0) return "YOU LOSE";

        int mi = 1<<29, mii = -1;
        // i を試す場合を考える
        for (int i = b.size() - 1; i >= 0; i -= 2) {
            int need = nim ^ b[i];

            // i から i+1 へ移す、これは a では i から取ることに相当
            if (need < b[i]) {
                if (mi >= b[i] - need) mi = b[i] - need, mii = i;
            }
            // i-1 から i へ移す、これは a では i-1 から取ることに相当
            else {
                // 左がマイナスになってはダメ
                if (i == 0 || need - b[i] > b[i-1]) continue;
                if (mi >= need - b[i]) mi = need - b[i], mii = i-1;
            }
        }
        stringstream ss;
        ss << "TAKE " << mi << " STONES FROM PILE " << mii;
        return ss.str();
    }
};

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

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

TopCoder SRM 309 DIV1 Hard - StoneGameStrategist (本番 4 人)

問題概要

制約

考えたこと