SRM 479 Div2 Hard TheBoardingDivTwo

誰も問題文を翻訳してくれない、まじめに読みます。

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11033

横一列に並んだ1~2*N個のセルがある。N個のシートがありi番目のシートはN+i番目のセルのそばにある。

N人の乗客が飛行機に搭乗しようとしている。はじめ1~Nのセルに立っている。

oooooooooooooooo
        xxxxxxxx

oがセルでxがシート、はじめはみんな飛行機の中に入ってないっぽい。

piが与えられる。pは乗客の初期位置で、p[i]は乗客iの初期位置。-1であるなら1~Nの任意の整数を選べ、整数ならその場所に確定している。

搭乗プロセスはいくつかのステップに分けられ、それぞれ1秒を要する。右から各乗客がルールに従い何をするかチェックできる。

  • 今チェックしている乗客をX、Xの現在のセルをYとする。
  • Y < N+X かつ Y+1が空であるなら、Y+1に1ステップで移動できる。
  • Y < N+X かつ Y+1に誰かが居て、このステップ中にY+1の人が移動するならY+1に1ステップで移動できる(これは右から乗客を見ていくことから明らか)。
  • Y < N+X かつ Y+1に誰かが居て、このステップ中にY+1の人が移動しないなら、このステップでは何もしない
  • Y = N+X なら自分の席に到達したことを表す。そして座るのに74ステップを要する。現在のステップをSとしてS,S+1...S+73の間、Yを占有する(S+73で座り終わる)。S+74のはじめに空になる。

pに一致する順番のうちboardingTime以下で全員が座り終わるものは何通りあるか。

 
 
 

解法

N≤8なので全探索できる。next_permutationかなんかでpのパターンと一致する順列を生成する。

生成した初期状態からboardingTime以下で全員が座り終わるかどうかを判定していく。

 
 
     
  

心臓に悪いコード

int bt, N;
vector<int>pat;

class TheBoardingDivTwo{
public:
    int ok(int f[8]){
        for(int i = 0; i < N; i++) if(!f[i]) return 0;
        return 1;
    }
    
    int check(int per[8]){
        int cell[16], t[16], f[8] = {};
        for(int i = 0; i < N*2; i++){
      if(i < N) cell[i] = per[i]; else cell[i] = -1;
      t[i] = 74;
    }
        for(int i = 1; i <= bt; i++){
            for(int Y = 2*N-1; Y >= 0; Y--){
                if(cell[Y] == -1) continue;
                if(t[Y]==0){ cell[Y] = -1; t[Y] = -1;}
                if(Y == cell[Y] + N){
                    t[Y]--;
                    if(t[Y] == 0) f[Y-N] = 1;
                }else if(cell[Y+1]==-1){
                    cell[Y+1] = cell[Y]; cell[Y] = -1;
                }
            }
            if(ok(f))   return 1;
        }
        return 0;
    }
    
    int permutation(int n, int bit, int per[8]){
        if(n==N){
            for(int i = 0; i < N; i++) if(pat[i]!=-1 && pat[i]!=per[i]) return 0;
            return check(per);
            return 0;
        }
        int res = 0;
        for(int i = 0; i < N; i++){
            if((bit>>i)&1) continue;
            per[n] = i;
            res += permutation(n+1, bit | (1<<i), per);
        }
        return res;
    }
    
    int find(vector <int> pattern, int boardingTime){
        N = pattern.size(), bt = boardingTime, pat = pattern;
        for(int i = 0; i < N; i++) if(pat[i]!=-1) pat[i]--;
        int per[8] = {};
        return permutation(0, 0, per);
    }
};

感想

問題を読むのに時間がかかり、結局読み間違えていてとても時間がかかった。コンテスト中には絶対に終わらない