みんなのプロコン 2019 D - Ears (青色, 600 点)

郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。

問題へのリンク

問題概要

すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。

このとき、各区間 [ ] () について、すぬけ君が通過した回数を として、これに対して

• を 1 個選んで に 1 を足す
• であるような を 1 個選んで から 1 を引く

という操作を好きな回数行った結果が となるようにしたい。操作を行う総回数として考えられる最小値を求めよ。

制約

• 

考えたこと

すぬけ君が操作を行った直後に のとりうる必要十分条件を求めることが肝要に思える。ちょっと考えると

1. すぬけ君が通った回数が 0 の区間
2. すぬけ君が通った回数が偶数回な区間 (折り返しがあるため)
3. すぬけ君が通った回数が奇数回な区間 (始点と終点との間)
4. すぬけ君が通った回数が偶数回な区間
5. すぬけ君が通った回数が 0 の区間

といったように、一般に 5 つのパートに分かれることがわかる (各区間長が 0 になることはありうる)。逆にこのようになっているものは、うまくすぬけ君を動かすことで実現可能であることも比較的すぐにわかる。注意したいのは、すぬけ君が通った回数が 0 でない区間は連結でなければならない。

さて、ここまでの考察を元にして考えよう。「どこが区間の変わり目になるのか」を考えたくなるのだが、それだと計算量が破綻してしまう。こういうゴチャゴチャした状態遷移を扱う問題はそのまんま DP になるイメージがある。

• dp[ i ][ s ] := 最初の i マスを終えた時点で、すぬけ君の区間状態が s の状態になっているときの、操作回数の最小値

とする。各マスについて、区間の属性を指定したときのコストを cost(i, s) としておくと

---

k >= j に対して

• chmin(dp[ i + 1 ][ k ], dp[ i ][ j ] + cost(i, k))

---

という遷移で求められる。
...あとから考えるとこんなに単純明快なのに、ぐちゃぐちゃしてしまった。。。

#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }

long long dp[510000][5];

long long cost(int i, int s, const vector<long long> &A) {
    if (s == 0) return A[i];
    else if (s == 4) return A[i];
    else if (s == 1 || s == 3) {
        if (A[i] % 2 == 0 && A[i] > 0) return 0;
        else if (A[i] > 0) return 1;
        else return 2;
    }
    else {
        if (A[i] % 2 == 0) return 1;
        else return 0;
    }
}

int main() {
    int L; cin >> L;
    vector<long long> A(L);
    for (int i = 0; i < L; ++i) cin >> A[i];

    for (int i = 0; i < 510000; ++i) for (int j = 0; j < 5; ++j) dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j < 5; ++j) {
            for (int k = j; k < 5; ++k) {
                chmin(dp[i+1][k], dp[i][j] + cost(i, k, A));
            }
        }
    }
    long long res = INF;
    for (int j = 0; j < 5; ++j) chmin(res, dp[L][j]);
    cout << res << endl;
}