ICPC アジア地区予選 2015 C問題 Sibling Rivalry

ICPC

問題

http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2015/all_problems.pdf

解説

ゲームっぽい問題でもゲーム木みたいなものを書けば良いとは限らない。特に，状態遷移に閉路が生じるときはダメ。ベルマンフォードっぽい方法で，ゴールから決めていくようにすると良い (参考 http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf)

コンテスト中にはこんな感じのコードを書いていました (閉路に入ったら負けやろ的な気持ちで)

int N, M, STEP[3];
bool canMove[50][50][101];
bool vis[50];
int memo[50];
int solve(int v) {
  if(v == N - 1) return 0;
  if(memo[v] != -1) return memo[v];
  if(vis[v]) return INF;
  vis[v] = true;
  int ret = 0;
  REP(k,3) {
    int mn = INF;
    REP(u,N) {
      if(canMove[v][u][STEP[k]]) {
        int tmp = solve(u) + 1;
        mn = min(mn, tmp);
      }
    }
    ret = max(ret, mn);
  }
  return memo[v] = ret;
}

このコードは次のケースで破綻します

正解は4ですが，前述のコードはIMPOSSIBLEと出力しています。

バグの過程はこんな感じです

  1. v1が必勝か必敗か調べたいです
  2. v1にいるときにお兄さんがBを選んだ場合にどうなるか知りたいので，3ステップ先を調べます。3ステップ先はv3だけなので次はv3を調べましょう。
  3. v3にいるときにお兄さんがBを選んだ場合にどうなるか知りたいので，3ステップ先を調べます。3ステップ先はv4とv5がありますが，ここでは先にv4を調べてみましょう。
  4. 今v4にいます。お兄さんがAを選んだらどうなるでしょうか？v3に行くことになりますね。ループに入ってしまいました。v4にいる状態でAを選ばれると負けみたいですね。ざんねん。

本当は，v4とv5のどちらかを選ぶ際にv5から先に選んでいれば，v3は必勝マスであることが分かって，その結果v4も必勝マスとなります。というわけで，ゲームっぽい問題でもゲーム木にループが出来てしまう問題には気をつけましょう。

正答コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
#define int long long
const int INF = (int)1e9;
int N, M, STEP[3];
vector<vector<int>> G;
bool canMove[50][50][101];
int winning[50];
signed main() {
  ios::sync_with_stdio(false);
  cin >> N >> M >> STEP[0] >> STEP[1] >> STEP[2];
  G.resize(N);
  REP(i,M) {
    int u, v; cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
  }
  memset(canMove, 0, sizeof(canMove));
  REP(i,N) canMove[i][i][0] = true;
  REP(d,100) {
    REP(i,N) REP(j,N) {
      if(canMove[i][j][d]) {
        for(int k : G[j]) canMove[i][k][d + 1] = true;
      }
    }
  }
  REP(i,N) winning[i] = INF;
  winning[N - 1] = 0;
  while(true) {
    bool update = false;
    REP(v,N) {
      int mx = 0;
      REP(k,3) {
        int mn = INF;
        REP(u,N) {
          if(canMove[v][u][STEP[k]]) {
            mn = min(mn, winning[u] + 1);
          }
        }
        mx = max(mx, mn);
      }
      if(winning[v] > mx) {
        winning[v] = mx;
        update = true;
      }
    }
    if(!update) break;
  }
  if(winning[0] == INF) {
    cout << "IMPOSSIBLE" << endl;
  }
  else {
    cout << winning[0] << endl;
  }
}

バグ発見器

テストケースをランダムに作って正答コードの出力と比較しました。

import subprocess
import random
import io
import sys
def main():
    MAX_V = 3
    while True:
        v = random.randint(2,MAX_V)
        prob = random.random()
        es = []
        for i in range(v):
            for j in range(v):
                if i != j:
                    if random.random() < prob:
                        es.append((i+1, j+1))
        steps = [random.randint(1,v) for i in range(3)]
        with io.StringIO() as f:
            print('{} {} {} {} {}'.format(v, len(es), *steps), file=f)
            for e in es:
                print('{} {}'.format(*e), file=f)

            stdin = f.getvalue()
            correct = subprocess.check_output(['./C'], input=stdin.encode('UTF-8'))
            wrong = subprocess.check_output(['./Cmiss'], input=stdin.encode('UTF-8'))
            print('.', end='')
            sys.stdout.flush()
            if correct != wrong:
                print()
                print(stdin, end='')
                break

if __name__ == '__main__':
    main()