CODE FESTIVAL 2014 決勝 : H - 部屋割り

状態遷移が混乱して本番に解けず…。
http://code-festival-2014-final.contest.atcoder.jp/tasks/code_festival_final_h

問題

N人の人がK個の部屋に分かれて泊まる。
先頭の人から順に部屋を選択するが、その際各人は以下のいずれかの手順で部屋を選択する。

• 現在最も人が少ない部屋を選択する。該当する部屋が複数ある場合、その中でランダムで選択する。
• 現在最も人が多い部屋を選択する。該当する部屋が複数ある場合、その中でランダムで選択する。

各人がどちらの手順を取るかが与えられる。
最終的に各人が泊まる部屋の人数の期待値を求めよ。

解法

i番の人がどの部屋に止まるかはランダム性があるので確定できないが、各人が部屋を選択したのち、その人が何人部屋P[i]に入って、かつ全体で何人部屋が何個あるかは確定する。
よってまず１回シミュレーションを行い、各人が何人部屋を選択するかを求める。

次に「今X人いる部屋はに今後追加される人数の期待値Q[X]」を導入し、後ろの人から順に最終的な期待値を求める。
i番の人はP[i]人いる部屋を選択し、結果的にP[i]+1人部屋を構築することになるので、各人の泊まる部屋の人数の期待値は(P[i]+1) + Q[P[i]+1]となる。
また、i番の人が選択する前、P[i]人部屋がR[P[i]]個あるとすると、i番の人はそのうち１つを選択するので、Q[P[i]]はQ[P[i]]と(1+Q[P[i]+1])をR[P[i]]-1:1で重みづけ平均を取ったものに更新される。

int N,K;
int rm[200001];
int num[200001];
double np[200001];
double res[200001];
int mi,ma;
string S;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	cin>>S;
	
	num[0]=K;
	FOR(i,N) {
		
		if(S[i]=='0') {
			rm[i]=mi;
			num[mi]--, num[mi+1]++;
			ma=max(ma,mi+1);
			if(num[mi]==0) mi++;
		}
		else {
			rm[i]=ma;
			num[ma]--, num[ma+1]++;
			while(num[mi]==0) mi++;
			ma++;
		}
	}
	
	for(i=N-1;i>=0;i--) {
		j=rm[i];
		res[i]=j+1+np[j+1];
		np[j] = (np[j]*(num[j]) + (np[j+1]+1))/(num[j]+1.0);
		num[j+1]--;
		num[j]++;
	}
	
	FOR(i,N) _P("%.12lf\n",res[i]);
}

まとめ

シンプルな問題設定で良かった。