yukicoder : No.2434 RAKUTAN de RAKUTAN

これも割と素直。
https://yukicoder.me/problems/no/2434

問題

0番からN番まで(N+1)マスからなる双六を考える。
初期状態で駒は0番のマスにあり、N番のマスに移動するものとする。
一部のマスはスコアを1得られるマスであり、また一部のマスはスコアを1失うマスである。

駒は、1進んだマスに動かすかX進んだマスに動かすかの二択を選ぶことができる。
ただし後者は最大H回までしか利用できない。
スコアが負の値を取ることもできるとき、得られるスコアの最大値を求めよ。

解法

Nが大きいが、座標圧縮をしてしまおう。
圧縮後に残すマスは、0番とN番に加え、スコアに変動があるマスから±X以内のマスである。

また、上記より、Xマスの移動は高々スコアの変動があるマス数程度しか使う必要がないため、Hの上限を抑えることができる。
あとは単純なDPで、現在位置とX進める残り回数を状態とし、スコアの最大値を求めればよい。

int N,H,X;
set<int> G,B;
vector<int> Xs;

int dp[25252][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H>>X;
	Xs.push_back(0);
	Xs.push_back(N);
	cin>>x;
	FOR(i,x) {
		cin>>j;
		G.insert(j);
		for(y=max(0,j-X);y<=min(N,j+X);y++) Xs.push_back(y);
	}
	cin>>x;
	FOR(i,x) {
		cin>>j;
		B.insert(j);
		for(y=max(0,j-X);y<=min(N,j+X);y++) Xs.push_back(y);
	}
	sort(ALL(Xs));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	H=min(H,(int)(B.size()+G.size()+1));
	FOR(i,Xs.size()) FOR(x,2020) dp[i][x]=-1<<30;
	dp[0][H]=0;
	FOR(i,Xs.size()) {
		x=i+1;
		y=lower_bound(ALL(Xs),Xs[i]+X)-Xs.begin();
		int addx=G.count(Xs[x]);
		int delx=B.count(Xs[x]);
		int addy=(y<Xs.size())&&G.count(Xs[y]);
		int dely=(y<Xs.size())&&B.count(Xs[y]);
		FOR(j,H+1) {
			dp[x][j]=max(dp[x][j],dp[i][j]+addx-delx);
			if(j&&y<Xs.size()) dp[y][j-1]=max(dp[y][j-1],dp[i][j]+addy-dely);
		}
	}
	int ma=-101010;
	FOR(j,H+1) ma=max(ma,dp[Xs.size()-1][j]);
	cout<<ma<<endl;
}

まとめ

大学の単位と、いわゆる普通の単位(unit)ってなんで同じ日本語になったんだろうな。