AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) B Three Coins

AtCoder

問題

全部裏を向いたコインがN枚並んでいます。コインにはそれぞれスコアaiが設定されています。
以下の操作を好きなだけ行うことが出来ます：

  • 連続した3枚のコインについて、すべて表裏が一致していた場合に限りその3枚を裏返す

表になっているコインのスコア総和の最大値を求めてください。

制約

  • 3 <= n <= 500
  • -100 <= a[i] <= 100


解法

小さい問題に分割することを考えます。
すると以下の2パターンの分割が思い浮かびます：

パターン１：別々の2区間で独立して表裏をわーわー変更したものをくっつけた形

 -1 10 20 30 -1 -1 -1 10 20 30
================================
  X  O  O  O  X  X  X  O  O  O

「連続する3枚のコインを表側にする」操作を左右で行っています。

パターン２：表側にした一続きの区間のうち一部を裏返しにする

  3 -2 -1  0 -1  4
====================
  O  O  O  O  O  O

↓

  3 -2 -1  0 -1  4
====================
  O  X  X  X  O  O

サンプル２の例です。全部表にしたあと、表になっている中の一部分を裏に戻しています。


この２つのパターンはどちらもDP（区間DP）の漸化式で考えることができます。
説明のため、

  • dp1[l][r] : 区間[l, r] を全部裏の状態から最適な状態に変更した場合の最大スコア
  • dp2[l][r] : 区間[l, r] を全部表の状態から最適な状態に変更した場合の最大スコア

と置きます。

パターン1は

dp1[l][r] = max(dp1[l][med] + dp1[med + 1][r]) (l<=med<r)
dp2[l][r] = max(dp2[l][med] + dp2[med + 1][r]) (l<=med<r)

と考えられ、
パターン２は

dp1[l][r] = max(dp1[l][r], dp2[ll][rr]) (l <= ll < rr <= r, (rr-ll+1) % 3 = 0)
dp2[l][r] = max(dp2[l][r], dp2[ll][rr] + sum(a[l..ll]) + sum(a[rr..r])) (l <= ll < rr <= r, (rr-ll+1) % 3 = 0)

と考えられます。

パターン２のほうの式では全部表or裏の区間から1区間だけ裏or表に変更する操作のみ考えていますが、
連続していない複数区間の表裏を変更するような操作はパターン１のほうでカバーすることができます。

これでこの問題が区間DPで解けそうな雰囲気を帯びてきました。

ただしこのままだとパターン２のほうの遷移式で ll, rrの組み合わせが O(N^2)通りあるため、
区間数のO(N^2)と合わせてO(N^4)となってしまい間に合いません。

実はll, rrの組み合わせは

  • ll : l, l+1, l+2の3通り
  • rr : 区間[ll, rr]の長さが3の倍数になるように、r以下でなるべく大きい値

の3通りだけを試せば十分です。

全てのll,rrの組み合わせは上の3通りの区間に対し、両端を3の倍数だけ削ったような区間になっているため、
パターン2ではなるべく広い範囲で操作しておき、両端を削るような操作はパターン1のほうで賄うことができるためです。

OOOOXXXXXOOOXOOOOOOO // これがこの区間の最適解となるコインの状態とします

OOOOOOOOOOOOOOOOOOOO // 最初：すべて表
↓
OXXXXXXXXXXXXXXXXXXO // 端をひとつ残し、すべて裏返す（パターン２）


XXX | XXXXXXXXX | XXXXXX // 裏返した区間にパターン１を適用
↓
（中略）
↓
OOO | XXXXXOOOX | OOOOOO // 個別の区間が最適な状態になる

ということで、

  • dp1[l][r] : 区間[l, r] を全部裏の状態から最適な状態に変更した場合の最大スコア
  • dp2[l][r] : 区間[l, r] を全部表の状態から最適な状態に変更した場合の最大スコア

を2パターンの遷移式で更新していくことにより、
区間数O(N^2)、区間ごとの遷移パターン数O(N)のO(N^3)の区間DPで解くことが出来ました。
なおパターン２におけるa[i]の部分和計算は累積和による高速化も可能ですが、
ll, rrの区間をめいっぱい取ることによって加算数が高々4個となるため愚直に都度ループで足しても問題ありません。

コード

長さが3の倍数となる区間について、「全部裏返す」操作を表→裏、裏→表の両方で許容してしまうと無限ループとなるのでそこだけ注意が必要です。

#include<bits/stdc++.h>
using namespace std;

#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define bit(n)      (1ll<<(li)(n))
#define INF bit(60)

li a[555];

li dp1[555][555]; // dp1[l][r] : 区間[l, r]が全部裏の状態から好きに操作した後の区間[l, r]の最大スコア
li dp2[555][555]; // dp2[l][r] : 区間[l, r]が全部表の状態から好きに操作した後の区間[l, r]の最大スコア

li calc1(li l, li r);
li calc2(li l, li r);

// 区間[l, r]が全部裏だった場合の区間[l, r]の最大スコア
inline li calc1(li l, li r) {
    if (dp1[l][r] != INF)return dp1[l][r];

    li res = 0;
    // 2区間のマージ
    repp(med, l, r) {
        res = max(res, calc1(l, med) + calc1(med + 1, r));
    }

    // 一部裏返してどうにかする
    repp(ll, l, l + 3) {
        li num = r - ll + 1;
        if (num < 3) continue;
        li rr = ll + (num / 3) * 3 - 1;
        res = max(res, calc2(ll, rr));
    }

    return dp1[l][r] = res;
}

// 区間[l, r]が全部表だった場合の区間[l, r]の最大スコア
inline li calc2(li l, li r) {
    if (dp2[l][r] != INF)return dp2[l][r];

    li res = 0;
    repp(i, l, r + 1) {
        res += a[i];
    }
    // 2区間のマージ
    repp(med, l, r) {
        res = max(res, calc2(l, med) + calc2(med + 1, r));
    }

    // 一部裏返してどうにかする
    // 左端から裏返すケースはやらない（無限ループだしそもそも前段で表側にする必要がない）
    repp(ll, l + 1, l + 3) {
        li len = r - ll + 1;
        if (len < 3) continue;
        li rr = ll + (len / 3) * 3 - 1;

        li amari = 0;
        repp(j, l, ll) {
            amari += a[j];
        }
        repp(j, rr + 1, r + 1) {
            amari += a[j];
        }
        res = max(res, calc1(ll, rr) + amari);
    }

    return dp2[l][r] = res;
}


int main() {
    li n;
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        rep(j, n) {
            dp1[i][j] = INF;
            dp2[i][j] = INF;
        }
    }
    cout << calc1(0, n - 1) << endl;

    return 0;
}