TopCoder SRM 676 Div2 Hard RailroadSwitchOperator

なかなか面白い問題。
https://community.topcoder.com/stat?c=problem_statement&pm=13770

問題

バランスした完全二分木の形状をした路線がある。
葉の頂点番号を左から1～N(=2^L)とする。

葉以外の各頂点には切替機があり、その切替機が左右どちらを向いているかによって、親頂点から来た列車が左右どちらの子頂点に行くか決まる。
初期状態では全切替機は左を向いている。

ここでR個の列車が、時刻t[i]に頂点x[i]に向けて発車する。(tは重複しない)
全列車が適切にx[i]に到着させるため、プレイヤーは切替機を操作することができる。
この手順は時刻z=1,2,3...ごとに以下のように行う。

1. t[i]=zな列車があれば、根頂点に出現させる
2. ここでプレイヤーは切替機の設定変更である。1回の設定変更で任意の個数の切替機の状態を変えられる。
3. 既に葉にいる列車は取り除く。
4. 線路上の列車は切替機の設定に則り１つ子の頂点に移動する。

全列車をx[i]に到着させるために必要な設定変更の最小回数を求めよ。

解法

各列車が通過する頂点について、直前にその頂点を訪れた列車の移動先と比較し、その時点から切り替えが必要かどうかをチェックする。
切り替えが必要な場合、時刻の区間[前の列車の到達時刻+1,今の列車の到着時刻]の間に最低1回設定変更が必要なことになる。

このような設定変更が必要な時刻の区間を列挙したら、あとは区間スケジューリングである。
出来るだけ少ない設定変更で全区間をカバーしたいので、区間を終端順でソートし、カバーしてない区間のうち最も早い終端時刻を設定変更を行うようにすればよい。

int state[1<<19];
int tim[1<<19];
vector<pair<int,int> > Q;

class RailroadSwitchOperator {
	public:
	int minEnergy(int N, vector <int> x, vector <int> t) {
		int M=x.size();
		int i,j,L=0;
		
		while((1<<(L+1))<=N) L++;
		
		ZERO(state);
		MINUS(tim);
		Q.clear();
		FOR(i,M) {
			x[i]--;
			FOR(j,L) {
				int pos=(1<<j)+(x[i]>>(L-j));
				int ns=(x[i]>>(L-j-1))&1;
				if(state[pos]!=ns) Q.push_back({t[i]+j,tim[pos]+1});
				state[pos]=ns;
				tim[pos]=t[i]+j;
			}
		}
		
		sort(Q.begin(),Q.end());
		
		int cnt=0;
		int right=-1;
		FORR(r,Q) if(r.second>right) right = r.first, cnt++;
		return cnt;
	}
}

まとめ

難易度の割に本番正答数少ないけど、今回Div2 Mediumがちょっと難しめだったからかな。