kmjp's blog

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

第15回 アルゴリズム実技検定 : M - 点の距離

まぁこれはゴリ押しがきくかな。
https://atcoder.jp/contests/past15-open/tasks/past202306_m

問題

1次元の数直線上にN個の点がある。
i番と(i+1)番の点の距離D(i)が与えられたとき、1番とN番の点の距離の最小値を求めよ。

解法

dp(n,x) := 1番目の点を位置0に置き、番号の小さい順に場所を確定させたとき、n番目の点を位置xに置けるか
とすると
dp(n+1,x) = dp(n,x-D[n]) or dp(n,x+D[n])
となる。bitsetであればこれらを短時間で処理できる。

int N;
bitset<4040400> BS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	BS[2020200]=1;
	FOR(i,N-1) {
		cin>>x;
		BS=(BS>>x)|(BS<<x);
	}
	int mi=1<<30;
	FOR(i,4040400) if(BS[i]) mi=min(mi,abs(i-2020200));
	cout<<mi<<endl;
}

まとめ

Bitsetを使う典型問題。