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

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

TopCoder SRM 309 D1H StoneGameStrategist

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

考えたこと

実は

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

{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();
    }
};