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); } };
感想
問題を読むのに時間がかかり、結局読み間違えていてとても時間がかかった。コンテスト中には絶対に終わらない