yukicoder No.334 - 門松ゲーム

問題

No.334 門松ゲーム - yukicoder

アイデア

「お互いに最善を尽くす」というところがとても悩ませる。

n個の数字それぞれに対して、ゲーム内でまだ使われてなければ1、既に使われてなくなっていれば0のbitで表した状態を考える。n<=12なので、状態は2^n-1個になる。ここでは、w[st]=状態stの場が自分の番に回ってきた時に勝てるかとして考える。

状態stから遷移出来る状態は、a,b,c番目のbitが立っていてk[a],k[b],k[c]が門松数であるもの全てである、この状態はst-(1<<a)-(1<<b)-(1<<c)で表される。これをa,b,c(a<b<c)に対して3重ループで列挙して、この遷移先にどこか１つでも「負け」の遷移先があればstにおいて自分の番がくれば、その状態に持っていけば相手の番で「負け」が確定するのでその状態は「勝ち」になる。逆に、どこに遷移しても「勝ち」に遷移してしまうなら相手が最善を尽くすので自分は「負け」になる。これをstが小さい方からbitloopする。立っているbitが3未満なら門松数は絶対作れないので負けとして設定する。

そして、初期状態(1<<n)-1が負けならば、勝てる手はない。ので-1を出力。勝ちならば、a,b,c(a<b<c) && k[a],k[b],k[c]が門松数であるに対してa,b,cが小さい方から3重ループで列挙して、最初に見つかるw[st-(1<<a)-(1<<b)-(1<<c)] = trueであるa,b,cの組合せが辞書順最小の初手になる。

実装(C++)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)

bool ch(int x, int y, int z){
  bool ret=true;
  if(x==y || x==z || y==z) ret=false;
  else{
    if(x<y && y<z) ret=false;
    if(x>y && y>z) ret=false;
  }
  return ret;
}

int main(int argc, char const *argv[]) {
  int n;
  int k[12];

  cin >>n;
  REP(i,n) cin >>k[i];

  //状態をbitで表し、この状態で自分の番が来たら勝てるのか
  bool w[4100];
  w[0]=false;

  FOR(st,1,1<<n){ //状態stのとき
    int ones=0;
    //立ってるbitが2つ以下なら負け確定
    REP(i,n) ones+=(st>>i)&1;

    //printf(" %d : %d\n", st, ones);
    if(ones<3){
      w[st]=false;
    }
    else{
      //bitが立ってる位置はまだ場に残っている
      //3重ループで列挙
      //どう選んでも勝ちの状態に行くならそこは負け
      //1つでも負けの状態に行く道があればそこは勝ち
      w[st]=false;
      FOR(a,0,n)FOR(b,a+1,n)FOR(c,b+1,n){
        //3つを列挙
        if((st>>a)&1 && (st>>b)&1 && (st>>c)&1){
          //全てbitが立ってれば試せる
          if(ch(k[a],k[b],k[c])){ //門松数？
            int nx=st-(1<<a)-(1<<b)-(1<<c);

            if(!w[nx]){
              w[st]=true;
              break;
            }
          }

        }
      }
    }

    //cout << st << " : " << w[st] << endl;
  }

  if(!w[(1<<n)-1]) printf("-1\n");
  else{
    //勝てる方法があるので小さい方から試して見つかったら終わり

    int aa,bb,cc;
    bool find=false;
    FOR(a,0,n){
      FOR(b,a+1,n){
        FOR(c,b+1,n){
          if(ch(k[a],k[b],k[c])){ //門松数？
            if(!w[(1<<n)-1-(1<<a)-(1<<b)-(1<<c)]){
              aa=a;
              bb=b;
              cc=c;
              find=true;
              break;
            }
          }
        }
        if(find) break;
      }
      if(find) break;
    }

    printf("%d %d %d\n",aa,bb,cc);
  }

  return 0;
}