AtCoder Regular Contest 231 : A - Two Dimensional Invader

あまり振るわず。
https://atcoder.jp/contests/arc231/tasks/arc231_a

問題

初期状態でプレイヤーは原点にいる。
敵がN体現れるので順次倒していきたい。
倒す手段は、敵の位置に移動して剣で倒すのと、魔法で遠隔で倒すのがあり得る。

移動の際は、距離の二乗のコストがかかる。また、魔法の場合は敵毎に指定されたコストがかかる。
全敵を倒すのにかかる総コストの最小値を求めよ。

解法

dp(n,x,y) := n体目まで敵を倒したとき、最終位置がx,yでかつ全部魔法で倒す場合に比べ浮くコストの最大値
とする。
dp(n,x,y)からdp(n+1,x,y)で変化するのは、(n+1)体目の敵の座標(x',y')のみである。
では、dp(n,x,y)からdp(n+1,x',y')を求めることを考える。
愚直に総当たりすると、O(max(x)*max(y))かかるので、これをO(max(x)+max(y))で済ませることを考える。

距離の計算式から、X座標の移動量とY座標の移動量は別々に考えられる。

以下がわかったとする。
dp2(n,x,y) := dp(n,*,y)の状態から(x,y)に移動したときの浮くコストの最小値
この時、dp2(n,x',y)をyごとに総当たりすればdp(n+1,x,y)を更新できる。
その後、dp2(n+1,x,y')を更新しよう。

int T,N;
ll X[252525],Y[252525],Z[252525];

ll dp[505][505];
ll Yma[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(y,500) {
			FOR(x,500) dp[y][x]=-1LL<<60;
		}
		dp[0][0]=0;
		FOR(y,500) {
			FOR(x,500) {
				Yma[y][x]=-1LL<<60;
				FOR(k,500) Yma[y][x]=max(Yma[y][x],dp[y][k]-(x-k)*(x-k));
			}
		}
		
		ll sum=0;
		FOR(i,N) {
			cin>>X[i]>>Y[i]>>Z[i];
			sum+=Z[i];
			ll tma=-1LL<<60;
			FOR(y,500) tma=max(tma,Z[i]+Yma[y][X[i]]-(y-Y[i])*(y-Y[i]));
			y=Y[i];
			dp[Y[i]][X[i]]=tma;
			FOR(x,500) {
				Yma[y][x]=max(Yma[y][x],dp[y][X[i]]-(x-X[i])*(x-X[i]));
			}
		}
		ll mi=sum;
		FOR(y,500) FOR(x,500) mi=min(mi,sum-dp[y][x]);
		cout<<mi<<endl;
		
	}
}

まとめ

２軸分けて考えればよいのは割とすぐ思いつけた。