みんなのプロコン2019 D - Ears (600)

D - Ears

概要

長さLの数列Bを準備しておく。値はすべて0。

数直線上に0, 1, 2, ..., Lの点がある。
上記点の好きな場所からスタートし、隣接した点を移動してゆく。
i-1からiに、もしくはiからi-1に移動するとB[i]が1加算される。
これを好きなだけ繰り返し、好きな場所で終了する。（散歩）

長さLの数列Aが与えられる。
上記で得られた数列Bに対し、以下の操作を繰り返すことで数列Bを数列Aに一致させることを考える。

• iを1つ選び、B[i]に1加算もしくは1減算する

このとき必要な操作の回数の最小値を求めよ。ただし、散歩での操作回数は「必要な操作」に含まれない。

制約

1 <= L <= 2* 10^5
0 <= A[i] <= 10^9

方針

散歩のパターンをいくつか試すと、散歩の後の数列は以下の部分に区分できる。

1. B[i] = 0
2. B[i]は偶数
3. B[i]は奇数
4. B[i]は偶数
5. B[i] = 0

（2と3の境界→2→1と2の境界→2→3→4→4と5の境界→4→3と4の境界）

2～4で偶奇のみが定まった任意の数が取れるのは、1つのi-1, i間を適当に往復すればよいから。
各部分の長さは0でもよい。ただし順番は崩れない。

よってこのパターンを数列Aに適用させて最小操作数をみていきたい。
このときDPが使える。

dp[i][k]：数列Aのi番目に対し、上記のk+1部分にいるときの最小操作数とする。
DPの遷移は、コスト関数cost(k, a)を用いることで、次のようにあらわせる。
dp[i][k] = min(dp[i][k], dp[i-1][j] + cost(k, A[i-1]))

コスト関数の実装では、
2, 4の部分の各区間は最低でも2回通過する必要があることに注意。

感想

DPの発想はなかった。。

解答

Submission #4220670 - Yahoo Programming Contest 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
// 散歩後の石数は 0 | e | o | e | 0 に区分される
// この状態を0, 1, 2, 3, 4とする
ll cost(int k, ll a){
	if(k == 0 || k == 4) return a;
 
	if(k == 1 || k == 3){
		if(a == 0) return 2;
		if(a % 2 == 1) return 1;
		return 0;
	}
 
	// k = 2;
	if(a % 2 == 0) return 1;
	return 0;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int L;
	cin >> L;
 
	ll A[L];
	rep(i, L) cin >> A[i];
 
	ll INF = 1e15;
	ll dp[L+1][5];
	rep(i, L+1) rep(j, 5) dp[i][j] = INF;
	dp[0][0] = 0;
 
	for(int i = 1; i <= L; i++){
		for(int j = 0; j < 5; j++){
			for(int k = j; k < 5; k++){
				dp[i][k] = min(dp[i][k], dp[i-1][j] + cost(k, A[i-1]));
			}
		}
	}
 
	ll ans = INF;
	rep(i, 5) ans = min(ans, dp[L][i]);
	cout << ans << endl;
}