Google Code Jam 2022 Round 2 : D. I, O Bot

Cに比べ実装は軽め。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec/0000000000b15167

問題

1次元の座標上、原点に車がある。
また、それ以外に2種類の荷物がN個あり、それぞれ座標が与えられる。

車は全荷物を原点に持ち帰りたい。
ただし、

• 各種類、同時に1つしか荷物を持てない。
• 距離１車を移動するのにコストが１かかる。
• 荷物の種類をコストCかけて変えることができる。

全荷物を原点に集めるのにかかる総コストを求めよ。

解法

座標が正の位置にある荷物が、負の位置に運ばれることは明らかに最適でない。
よって、正の位置にある荷物と、負の位置にある荷物をそれぞれ考えればよい。
以下、荷物の座標はすべて正とする。

Smallを解くO(N^2)の解法は割と簡単。
2種類の荷物の座標をあらかじめそれぞれ2種類ソートしておく。
dp(a,b) := 1種類目が近い順から残りa個、2種類目が近い順から残りb個あり、車が原点にあるような状態に至る最小コスト
とする。dp(0,0)が求めたい解である。
ここから取れる最適手としては、(残る荷物が2個以上あるなら)異なる種類を1個ずつ一番遠い位置にあるものを持ち帰るか、同種のものをコストCかけて遠い位置にある2個を持ち帰るかである。
あとはこれをO(N^2)で解いていこう。メモ化再帰だと割と重くてTLEするが、DPなら間に合う。

Largeではこれは間に合わない。
そこでO(N)解法を取る。
2種類の荷物を合わせて昇順に並べておく。
また、事前に同種の荷物における座標の総和を累積和の形で事前に計算しておこう。

dp(n) := 近い方からn個の荷物を回収し終わるのにかかる最小コスト
とし、dp(0)=0から始めてdp(N)を求めよう。
Smallの解法を考えると、以下2つの遷移はわかりやすい。

• 原点からn個目の荷物を単独で持ち帰る。dp(n-1)からdp(n)に遷移する。
• 原点からn個目の荷物と(n-1)個目の荷物を持ち帰る。dp(n-2)からdp(n)に遷移する。

もう1つの遷移として、

• 原点からn個目の荷物と、別の種類のk個目の荷物を合わせて持ち帰る

がある。この時、詳細な議論はEditorialに譲るとして、ある区間[m,n]個目の荷物で、両種類の荷物が半々であり、また遠くにあるn個目と同じ種類のものと、より原点に近いn個目と異なる種類のものを合わせて持ち帰るのが最適というケースがある。これが発生するのは、荷物のprefixにおける両種類の個数の差が、n個目までと(m-1)個目までが一致し、かつ(m-2)～(n-1)個目まででは一致しないようなmの時だけである。その場合、dp(m-1)からdp(n)に遷移する。

int N,C;
ll dp[101010];
ll S[2][101010];

ll go(vector<pair<int,int>> X) {
	if(X.empty()) return 0;
	int N=X.size();
	sort(ALL(X));
	int i;
	FOR(i,N) {
		S[0][i+1]=S[0][i];
		S[1][i+1]=S[1][i];
		S[X[i].second][i+1]+=X[i].first;
	}
	
	map<int,int> M;
	int cur=0;
	M[0]=0;
	dp[0]=0;
	
	for(i=1;i<=N;i++) {
		int x=X[i-1].first;
		int c=X[i-1].second;
		dp[i]=dp[i-1]+2*x;
		if(i>=2) dp[i]=min(dp[i],dp[i-2]+2*x+(c==X[i-2].second)*C);
		
		if(c==1) cur++;
		else cur--;
		
		if(M.count(cur)) {
			int k=M[cur];
			dp[i]=min(dp[i],dp[k]+2*(S[c][i]-S[c][k]));
		}
		M[cur]=i;
	}
	
	
	return dp[N];
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>C;
	vector<pair<int,int>> X,Y;
	FOR(i,N) {
		cin>>x>>y;
		if(x>0) X.push_back({x,y});
		else Y.push_back({-x,y});
	}
	
	ll ret=go(X)+go(Y);
	cout<<"Case #"<<_loop<<": "<<ret<<endl;
	//_P("Case #%d:\n",_loop);
}

まとめ

コードは易しいけど考察が難しい。