ICPC/Japan 2001/Problem G. Nim

Problem G. Nim

問題文

• PKU

難易度

★★★☆☆

問題概要

石取ゲームの変形版。

石がs個積んであって、プレイヤーは交互に石を取っていく。このとき、取れる石の個数は1からmまでのいずれかである。最後に石を取ったプレイヤーは負けとする。

今回はこのゲームをAとBの二つのチーム戦で行う。各チームにはn人のプレイヤーがいて、n*2人全てのプレイヤーに、それぞれ独立してm（取れる石の最大数）が与えられる。石を取る順序は、A1,B1,A2,B2, ... , An,Bnというようにチームで交互である。

チームAに必勝法があるかどうか答えよ。

解法

3時間くらい考えてやっとでけた。DP苦手杉。

Nimの変形問題は色々あるけど、この問題は各人によって取れる石の個数が違うというのが特徴。だから、DPで表を作るにしても、誰のターンなのかということを考えないといけない。

これを基に考察すると（別に基にしなくても思いつく人がほとんどなんだろうけど）、以下のようなことが言えることが分かる。

• 残り石がi個のときプレイヤーjが負けるなら、残り石がi+kのときプレイヤーiは勝つことができる。ただし、k=1,2,...,mj、

mjはjが取れる石の最大個数。例えば残り石が1個でプレイヤー3のターンが来たのなら、プレイヤー3は必ず負ける。したがって、ひとつ前のプレイヤーであるプレイヤー2は、残り石が1個でプレイヤー3のターンになるようにすれば勝てるという。なんとも当たり前のことだ。。。

後はこれを、sが1の場合から上に埋めていく。sが1のときは、全員が必ず負けると言えるから初期状態として適切。

ひとつ前のプレイヤーを計算するときに、-1するだけだと負の数になりうることに注意。こういうときは足して剰余取るのが良い。

これに3時間とかダメだわ。。。本番なら焦って絶対解けてない。

ソース

/*
  Nim
  Japan 2001
  Problem G
*/

#include
#include
#include

using namespace std;

int main() {
  int n, s;

  while(cin >> n >> s, n) {
    vector<int> m(n * 2);
    for(int i = 0 ; i < n * 2 ; i++) cin >> m[i];

    // tbl[i][j]:残り石がi個の時、プレイヤーjが負けるならfalse
    vector<vector<bool> > tbl(s + 1, vector<bool>(m.size(), false));

    for(int i = 1 ; i <= s ; i++) {
      for(int j = 0 ; j < m.size() ; j++) {
        if(tbl[i][j] == false) {
          // jの前のプレイヤー
          int p = ((j - 1) + m.size()) % m.size();

          for(int k = 1 ; k <= m[p] and i + k < tbl.size() ; k++) {
            tbl[i + k][p] = true;
          }
        }
      }
    }

    cout << tbl[s][0] << endl;
  }
}