KUPC2013 : F - ７歳教

変なタイトルの問題。
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_f

問題

各惑星では、L[i]～R[i]の期間だけ宗教を布教することができる。
惑星間の移動時間と、初期の惑星の位置を与えられた場合、宗教を布教できる最長期間を答えよ。

解法

最初貪欲にL[i]が近い順にたどっていったところ、pretestは通ったけど後はダメだった。

ここで頭に浮かんだのが、蟻本にある区間スケジューリング。
すなわち、R[i]が後ろにあるものから時間を逆順に辿って布教期間を最大化すればよい。

事前に以下の処理をしておこう。

• 惑星とA→Bと移動するよりA→C→Bと移動する方が速い可能性があるので、先にワーシャルフロイト法で最短移動経路を求めておく。
• 開始惑星の位置を考えるのが面倒なので、開始惑星Sと各惑星Xの時間をT[S][X]とすると、L[X]

int N,S;
ll L[512],R[512];
ll dist[512][512];

ll DP[512];


void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>N>>S;
	S--;
	FOR(i,N) cin>>L[i]>>R[i];
	FOR(x,N) FOR(y,N) cin>>dist[x][y];
	FOR(i,N) FOR(j,N) FOR(k,N) dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
	
	vector<pair<ll,int> > cand;
	FOR(i,N) {
		L[i]=max(L[i],dist[S][i]);
		R[i]=max(L[i],R[i]);
		DP[i]=R[i]-L[i];
		cand.push_back(make_pair(R[i],i));
	}
	
	sort(cand.begin(),cand.end());
	reverse(cand.begin(),cand.end());
	
	ll ret=0;
	FOR(i,cand.size()) {
		ll cp=cand[i].first;
		int cur=cand[i].second;
		FOR(x,N) {
			if(L[x]>L[cur]-dist[x][cur]) continue;
			DP[x]=max(DP[x],DP[cur]+min(R[x],L[cur]-dist[x][cur])-L[x]);
		}
	}
	
	cout << *max_element(DP,DP+N) << endl;
	return;
}

まとめ

途中で蟻本の問題が思いついて気持ち良く解けた。