2012 WUPC2 : H - ダイヤグラム

こちらは最近の練習のおかげで解けるようになった問題。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_08

まず、列車の数が高々200で、始点終点で合わせて400個の駅だけ考慮すればいいので、座標圧縮で余計な駅を削除する。
次に、列車ごとに始点の駅が西(数字の小さい方)から並ぶようにして、DPすればよい。

DPは、２本以上列車が止まる駅の東端と１列車が止まる駅の東端の２つを要素に持ち、そのような列車運行を行うパターンを値に持つ２次元配列で行う。

ある駅が区間S～Tを運行する場合、S-1以降に２本以上列車が止まる上記配列に対し、以下のようにDPする。
たとえばXまで２本、Yまで１本列車が止まるパターンに対し：

T＜＝X以下の場合、すでにTまでの駅は２本以上列車が止まるので、今見ている列車は通っても通らなくてもよい。よってパターン数を２倍にする
X＜T＜＝Yの場合、つまりTが１本だけ列車が止まる駅の場合、Tまで２本止まる配列要素に今の値を加算する
Y＜T、つまりTが１本も列車が止まらない駅の場合、Yまで２本、Tまで１本止まる配列要素に今の値を加算する。

最終的には、東端の駅に２本以上列車が止まるパターン数を回答すればよい。
計算量はO(駅数^3)なので駅が200程度なら問題なし。

int N,M;
int TS[201];
int TT[201];
int rm[100001];
vector<int> rmv;
vector<pair<int,int> > TR;
ll num[1000][1000]; // num[y][x] xまで2個以上、yまで1個

void solve() {
	int x,y,i,j,rr,TM,nc;
	int tx,ty,ng,LS;
	char cmd[100];
	ll p,cch;
	
	N=GETi();
	M=GETi();
	ng=0;
	
	rmv.clear();
	ZERO(rm);
	FOR(i,M) {
		TS[i]=GETi();
		TT[i]=GETi();
		if(TS[i]==1) ng |= 1;
		if(TT[i]==N) ng |= 2;
		rmv.push_back(TS[i]);
		rmv.push_back(TT[i]);
	}
	sort(rmv.begin(),rmv.end());
	
	
	if(ng!=3) {
		_P("0\n");
		return;
	}
	sort(rmv.begin(),rmv.end());
	rmv.erase(unique(rmv.begin(), rmv.end()), rmv.end());
	
	FOR(i,rmv.size()) {
		if(i==0) rm[rmv[0]]=1;
		else if(rmv[i]==rmv[i-1]+1) rm[rmv[i]]=rm[rmv[i-1]]+1;
		else rm[rmv[i]]=rm[rmv[i-1]]+2;
		LS=rm[rmv[i]];
	}
	
	TR.clear();
	FOR(i,M) TR.push_back(make_pair(rm[TS[i]],rm[TT[i]]));
	sort(TR.begin(),TR.end());
	
	ZERO(num);
	num[0][0]=1;
	FOR(i,TR.size()) {
		int s = TR[i].first;
		int t = TR[i].second;
		
		for(y=LS;y>=s-1;y--) {
			for(x=LS;x>=y;x--) {
				if(!num[y][x]) continue;
				if(t<=y) {
					num[y][x] +=num[y][x];
					num[y][x] %= 1000000007;
				}
				else if(t<=x) {
					num[t][x] +=num[y][x];
					num[t][x] %= 1000000007;
				}
				else {
					num[x][t] +=num[y][x];
					num[x][t] %= 1000000007;
				}
			}
		}
	}
	_P("%lld\n",num[LS][LS]%1000000007);
	return;
}

まとめ

例題の一番下にあるけど、必ずしも駅間で列車が通らない区間があってもいいのね。
これを正しく処理できなくて何度かWAしてしまった。

kmjp's blog

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

2012 WUPC2 : H - ダイヤグラム

まとめ