kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round2C Medium LongSeat

これは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の訳はないよなー」と思ってたけどね。