kmjp's blog

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

Codeforces #299 Div1 D. Tavas in Kansas

Codeforces

DPに持っていくまでの発想が難しいし、その後のDPも結構複雑。
http://codeforces.com/contest/536/problem/D

問題

N頂点M距離付無向辺からなるグラフが与えられる。
また各頂点にはスコアP[i]が振られている。

２人で以下のようなゲームを行う。
２人は異なる頂点S,Tを初期位置とし、交互に自分のターンを迎える。

自分のターンでは、距離Dを申告する。
すると自分の初期位置から距離D内にある未カウントの点のスコアを自分のスコアに加える。
どちらかが1度スコアを加えた頂点は、以後どちらのスコアにもカウントされない。
また、距離Dを申告する際は、２人とも未カウントの頂点を1個以上含む値を申告しなければならない。

２人が最適手を取った場合、スコアの合計値はどちらが優勢か答えよ。

解法

まず各頂点について、S,Tからの最短距離を求めそれを座標圧縮する。
xにおけるS,Tからの距離をそれぞれ座標圧縮後の値を(DS(x),DT(x))とする。

各頂点xについて、２次元座標上で(DS(x),DT(x))の点がスコアP[x]を持つ、と考える。
初期状態で、先手はX軸と平行なy=0の棒、後手はY軸と平行なx=0の棒を持っていると考える。
そうすると、各人のターンでは、先手は棒を上に上げ、後手は棒を右に動かし、その過程で棒と触れた未カウントの頂点のスコアが自分のスコアに加算する、と考えられる。

実際は２人のスコアを個別に求める必要はなく、その差だけを求めればよい。
あとはDPの要領でDP[横棒の位置][縦棒の位置][手番]=スコアの差、という状態をDPで更新していけば良い。
先手はスコアの差が最大となるように横棒を上に動かし、後手はスコアの差が最小となるように縦棒を右に動かす。

愚直に行うと状態がO(N^2)通りで、棒の遷移がO(N)通りで合わせた計算量がO(N^3)となってTLEするので、うまく累積和などを使い全体の計算量をO(N^2)に落とす必要がある。

int N,M,S,T;
vector<pair<int,int> > E[2020];
ll P[2020];
ll dist[2][2020];
map<ll,int> MM[2];

int MX,MY;
ll SC[2020][2020],np[2020][2020];
ll sum[2020][2020],snp[2020][2020];
ll dp[2020][2020][2];
int may[2020],mix[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S>>T;
	S--, T--;
	FOR(i,N) cin>>P[i], dist[0][i]=dist[1][i]=1LL<<60;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].emplace_back(y-1,r);
		E[y-1].emplace_back(x-1,r);
	}
	
	dist[0][S]=dist[1][T]=0;
	priority_queue<pair<ll,int> > Q;
	Q.emplace(0,S);
	Q.emplace(0,T+1000000);
	while(Q.size()) {
		auto r=Q.top();
		int type=r.second/1000000;
		int cur=r.second%1000000;
		ll co=-r.first;
		Q.pop();
		if(co!=dist[type][cur]) continue;
		
		FORR(e,E[cur]) if(co+e.second < dist[type][e.first]) {
			dist[type][e.first] = co+e.second;
			Q.emplace(-dist[type][e.first],e.first + type*1000000);
		}
	}
	FOR(i,N) MM[0][dist[0][i]]=MM[1][dist[1][i]]=0;
	ITR(it,MM[0]) it->second=MX++;
	ITR(it,MM[1]) it->second=MY++;
	FOR(i,N) SC[MM[0][dist[0][i]]][MM[1][dist[1][i]]]+=P[i], np[MM[0][dist[0][i]]][MM[1][dist[1][i]]]++;
	FOR(y,MY) FOR(x,MX) sum[y+1][x+1]=SC[y][x]+sum[y][x+1]+sum[y+1][x]-sum[y][x];
	FOR(y,MY) FOR(x,MX) snp[y+1][x+1]=np[y][x]+snp[y][x+1]+snp[y+1][x]-snp[y][x];
	
	FOR(x,MX) may[x]=MY;
	FOR(y,MY) mix[y]=MX;
	
	for(y=MY-1;y>=0;y--) for(x=MX-1;x>=0;x--) {
		int& my=mix[y];
		int& mx=may[x];
		dp[y][x][0]=dp[y+1][x][0]+sum[y+1][MX]-sum[y][MX]-sum[y+1][x]+sum[y][x];
		dp[y][x][1]=dp[y][x+1][1]-(sum[MY][x+1]-sum[MY][x]-sum[y][x+1]+sum[y][x]);
		
		if(snp[y+1][MX]-snp[y][MX]-snp[y+1][x]+snp[y][x]) {
			ll tc=dp[y+1][x][1]+sum[y+1][MX]-sum[y][MX]-sum[y+1][x]+sum[y][x];
			if(dp[y][x][0]<tc) dp[y][x][0]=tc, my=y;
		}
		if(snp[MY][x+1]-snp[MY][x]-snp[y][x+1]+snp[y][x]) {
			ll tc=dp[y][x+1][0]-(sum[MY][x+1]-sum[MY][x]-sum[y][x+1]+sum[y][x]);
			if(dp[y][x][1]>tc) dp[y][x][1]=tc, mx=x;
		}
	}
	ll cp=dp[0][0][0];
	if(cp==0) cout<<"Flowers"<<endl;
	else if(cp<0) cout<<"Cry"<<endl;
	else cout<<"Break a heart"<<endl;
	
}

まとめ

シンプルな問題設定ながら結構ややこしいDPになる問題だなぁ。