Codeforces #298 Div2 D. Handshakes

あまり自信がなかったが通ってよかった。
http://codeforces.com/contest/534/problem/D

問題

N人の生徒が順に部屋に入ってくる。
生徒は部屋に入ると、部屋内のチームに属さない他の生徒と１回ずつ握手を行う。
また、任意のタイミングで部屋内で３人チームを構成することができる。

各生徒の入室時の握手回数A[i]が与えられる。
この握手回数を実現できるような生徒の入室順があれば、それを答えよ。

解法

色々な解法が考えられそうな問題。
まず握手回数ごとに生徒を分類し、生徒の番号をmultimapで管理する。

部屋内の人数初期値x=0から始め、以下のようにxを推移させる。

• x人と握手した人がいたら、その人を入室させ(x+1)人にする。
• この時点で、未入室のx,(x-1),(x-2)人と握手した３人組がいたら、今部屋にいる生徒で３人組を作り、生徒数を(x+1)人から(x-2)人に減らす。
• 上記処理をx人と握手した未入室の人がいなくなるまで続ける。

この結果、握手人数x人以下で、未入室の生徒が残る場合がある。
あとはこれを以下のように回収する。

• x人と握手した人がいたら、その人を入室させ(x+1)人にする。
• x人と握手した人がいない場合、そこから３人組を作り(x-3)人にする。
• 上記処理をx<0となるまで繰り返す。

これで全員が入室できていればok。そうでなければ条件を満たす入室順は無い。

まとめると上記アプローチは以下のように考えられる。

• 前半パートではとにかくxを増やしていきたい。ただ、xを減らしても元のxに戻れそうな場合は戻っても良い。
• 後半パートで残った人を回収する。

int N;
multiset<int> D[303030];
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, D[x].insert(i+1);
	
	x=0;
	while(D[x].size()) {
		R.push_back(*D[x].begin());
		D[x].erase(D[x].begin());
		x++;
		if(x>=3&&D[x-3].size()&&D[x-2].size()&&D[x-1].size()) x-=3;
	}
	
	while(x>=0) {
		if(D[x].size()) {
			R.push_back(*D[x].begin());
			D[x].erase(D[x].begin());
			x++;
		}
		else x-=3;
	}
	
	if(R.size()!=N) return _P("Impossible\n");
	
	_P("Possible\n");
	FORR(r,R) _P("%d ",r);
	_P("\n");
}

まとめ

Div1 B相当にしては簡単…？でも落とし穴もちょこちょこあるしこのぐらいでいいのかな。