これは600pt位でもよさそう。
http://community.topcoder.com/stat?c=problem_statement&pm=13911
問題
長さLのベンチがある。
ここにN人の人が順にやってくる。
各人はベンチで長さW[i]分の区間を占有して座りたい。
もしそのような連続した空き区間があれば必ず座るし、なければ立つ。
なお、占有する区間の座標は整数でなくても良い。また空き区間の取り方が一意でない場合、どこをどうとるかはあらゆる可能性が考えられる。
この条件の元で、各人は以下のどれに相当するか答えよ。
- 必ず座る
- 必ず立つ
- 座る場合も立つ場合もある
解法
next_pemutation等を使い、以下を総当たりする。
- 座る人と立つ人のバリエーション
- 座る人の端から座る順
上記2つを考慮して、そのようなベンチの利用状況があり得るなら、「座る人と立つ人のバリエーション」をもとに各人の座る/立つ可能性がある、と判断できる。
あとは「座る人と立つ人のバリエーション」「座る人の端から座る順」が与えられたとき、そのような状態が存在しうるか考える。
まず座る人のW[i]の総和がLを超える場合には、明らかにそのような状態は発生しないのでこれは除く。
P人が座るとすると、座る人と座る人の間、及びベンチの端とベンチよりに座る人の間に計(P+1)個のスキマができる。
ここで1次元座標上にX[0]~X[P+1]の(P+2)頂点があることを考える。
X[0]=0、X[P+1]=Lとし、X[i]とX[i+1]の距離はすなわち(i+1)個目のスキマであると考える。
人が順々にやってきて、途中立つ人iがやってきた場合に、各スキマの大きさがW[i]未満であればよい。
なお、i番より後に来る予定の人の分は、まだスキマが分かれておらず連結していると考える。
例えば3番目と4番目の隙間の間に座る人jがiの後に来る場合、この2つの隙間はまだ連結していて、実質X[4]-X[2]+W[j]分のスキマがある、と考える。
このような2変数の不等式からなる条件群が成り立つかどうかは、最短経路問題で置き換えることができる。
(牛ゲー等と呼ばれる。蟻本p.105あたり参照)
上記条件より、X[0]~X[P+1]の(P+2)頂点に対応するグラフを考え、以下のように辺を張る。
条件を満たすXの配置があるなら、このグラフはコストが負になる閉路を持たないので、ベルマンフォード法で検出すればよい。
- X[P+1]-X[0]≧Lなので、0→(P+1)にコスト-Lの辺を張る。
- X[i]≦X[i+1]なので、i→(i+1)にコスト0の辺を張る。
- 立つ人が来たときのスキマの条件X[q]-X[p]<constより、q→pにコスト(const-eps)の辺を張る。
template<int MV> class Bellman_Ford { public: int NV; ll cost[MV]; vector<pair<int,ll> > E[MV]; void add_edge(int from,int to,ll cost){ E[from].push_back(make_pair(to,cost));} bool calc(int start,int NV) { // true:ok false:cycle int i,j,k; FOR(i,NV) cost[i]=1LL<<61; cost[start]=0; FOR(i,NV) { bool up=false; FOR(j,NV) FOR(k,E[j].size()) { if(cost[E[j][k].first]>cost[j]+E[j][k].second) cost[E[j][k].first]=cost[j]+E[j][k].second, up=true; } if(!up) return true; } return false; } }; class LongSeat { public: ll L; int N; vector<int> W; bool can(vector<int> V) { int i,j,k,num=0; ll left=L*1000; vector<int> did; Bellman_Ford<14> bf; ll rev[10]={}; FOR(i,10) rev[i]=-1; FOR(i,N) if(V[i]>=0) rev[V[i]]=1000LL*W[i],num++; did.push_back(-1); did.push_back(num); FOR(i,N) { if(V[i]==-1) { FOR(j,did.size()-1) { ll ts=0; for(k=did[j]+1;k<did[j+1];k++) ts += rev[k]; bf.add_edge(did[j+1]+1,did[j]+1,(W[i]*1000LL-ts)-1); } } else { if(W[i]*1000LL>left) return false; left -= W[i]*1000LL; did.push_back(V[i]); sort(did.begin(),did.end()); } } FOR(i,num+1) bf.add_edge(i,i+1,0); bf.add_edge(0,num+1,-left); return bf.calc(0,num+2); } vector <string> canSit(int L, vector <int> width) { this->L=L; this->W=width; this->N=width.size(); int i,j; int sit[10]={}; int V[10]; FOR(i,N) V[i]=i; do { vector<int> V2(N,-1); for(i=0;i<=N;i++) { V2[V[i-1]]=i-1; if(can(V2)) FOR(j,N) sit[V[j]]|=1<<(j>=i); } } while(next_permutation(V,V+N)); vector<string> R; FOR(i,N) { if(sit[i]==1) R.push_back("Sit"); if(sit[i]==2) R.push_back("Stand"); if(sit[i]==3) R.push_back("Unsure"); } return R; } }
まとめ
まぁ本番O(2^N*N)の解法でsubmitして、「Nの上限が8の訳はないよなー」と思ってたけどね。