はまやんはまやんはまやん

hamayanhamayan's blog

Brave CHAIN [AtCoder Beginner Contest 176 F]

競技プログラミング

https://atcoder.jp/contests/abc176/tasks/abc176_f

前提知識

解説

https://atcoder.jp/contests/abc176/submissions/16164487

難しい問題。方針自体はやったことがあれば、すんなり出てくるかもしれないが、
効率的な実装方針決め、正確な場合分が要求される。

自明なO(N3)のDP

TwitterのTLで「自明なO(N3)のDPまでは行った」みたいなワードを見かけることがあったかもしれない。
その解法を見つけることが、今回の問題の第一ステップ。

dp[i][x][y] := A[i]まで処理が終わっていて、先頭の2つがx,yである場合の得点最大値
先頭から5要素操作をして、2つだけ残すので、状態として先頭の2つをもったDPを考える。
ここからの遷移を考えると、見るべき状態は、iで2000, xで2000, yで2000なので既にO(N3)となっている。
簡単に考えると、先頭から3番目をa, 4番目をb, 5番目をcとすると、
次に残せる選択肢はxyacbの中から2つなので、遷移先はそんなにない（定数倍）。
なので、状態がO(N3)で遷移はO(1)なので、全体でO(N3)となる。

インラインDP

in-placeとも言ったりするが、インラインDPという手法を使う。
遷移を見てみると、dp[i][x][y]からdp[i+1][x][y]への遷移が大多数となっている。
しかも、遷移後は値が変わっていない（a=b=cの場合だけ別）。
こういう場合はインラインDPが使えるチャンスである。
インラインDPとは、更新時にDPテーブルを使いまわし、更新が必要な部分だけを更新することで高速化するテクである。

詳しくはググるか、「インラインDP」というテクニックに関して - skyaozoraの日記 - TopCoder部がいいと思う。

遷移のパターン

先頭から3番目をa, 4番目をb, 5番目をcとすると、遷移先は

  1. dp[i][any][any] -> dp[i + 1][any][any]
  2. dp[i][any][any] -> dp[i + 1][any][a or b or c]
  3. dp[i][any][any] -> dp[i + 1][a or b or c][a or b or c]

この3種類となる。

1. について

基本的には得点はもらえない。
だが、例外があり、a=b=cの場合は1点もらえる。
なので、a=b=cの場合は全体が+1されることになる。
インラインDP自体では全体に+1ということは難しいので、別に全体に後で加算する用の変数を用意しておいて、最後に答えに足すことにしよう。
インラインDPを使えば、全体への更新は必要なくなるので、ここで遷移は発生しない。

2. について

遷移先をよく見てみるとN通りしかない。
各遷移先について貰うDPを考えると、区間最大値になっているので、代入された段階で最大値を更新するようにして、
ma_row[x] := 片方がxであるdp[x][any]の最大値
を作っていけば、O(1)で遷移可能。
大体はそのまま遷移させればいいが、例えば、dp[i][x][y]からdp[i+1][x][a]と遷移させたときに、y=b=cであればポイントがあがるので、
その部分だけ分けて計算する。

3. について

これは遷移先が6通りしかない（順番を無視すればもっと減る）。
各遷移先について貰うDPを考えると、全体の最大値になっているので、全体の最大値を更新するようにして保持しておけばO(1)で遷移可能。
2. が分かっていればこちらはあまり難しくない。

実装について

DP更新をするが、1イテレーションが終了するまでに変更してしまうと、更新後データで更新してしまう恐れがあるので、
修正点を洗い出して最後に更新するようにする。

あと、dp[i][x][y]とdp[i][y][x]は変わらないので更新時にどっちも更新することで、1番目2番目という意識をなくして実装している。
無駄な更新というか何度も更新してしまう形になるが、実装は楽になる。

int N, A[6010];
int dp[2010][2010];
using tiii = tuple<int, int, int>;
int ma_row[2020];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N * 3) cin >> A[i];

    rep(i, 1, N + 1) rep(j, 1, N + 1) dp[i][j] = -inf;
    dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0;
    rep(i, 1, N + 1) ma_row[i] = -inf;
    ma_row[A[0]] = ma_row[A[1]] = 0;

    int additionalPoint = 0;
    int ma = 0;

    rep(i, 0, N - 1) {
        int idx = i * 3 + 2;

        vector<int> nxt;
        rep(j, 0, 3) nxt.push_back(A[idx + j]);
        sort(all(nxt));

        if (nxt[0] == nxt[1] && nxt[1] == nxt[2]) {
            additionalPoint++;
            continue;
        }

        vector<tiii> changeQueue;
        rep(_a, 0, 3) rep(_b, 0, 3) if(_a != _b) {
            int a = nxt[_a], b = nxt[_b], c = (nxt[0] + nxt[1] + nxt[2] - a - b);

            // dp[i][x][y] -> dp[i + 1][x][a]
            rep(x, 1, N + 1) {
                int opt = ma_row[x];
                if (b == c) chmax(opt, dp[x][b] + 1);
                changeQueue.push_back(tiii(x, a, opt));
            }

            // dp[i][any][any] -> dp[i + 1][a][b]
            int ma2 = ma;
            chmax(ma2, dp[c][c] + 1);
            changeQueue.push_back(tiii(a, b, ma2));
        }

        fore(t, changeQueue) {
            int x, y, val;
            tie(x, y, val) = t;

            chmax(dp[x][y], val);
            chmax(dp[y][x], val);
            chmax(ma_row[x], val);
            chmax(ma_row[y], val);
            chmax(ma, val);
        }
    }

    int ans = 0;
    rep(x, 1, N + 1) rep(y, 1, N + 1) chmax(ans, dp[x][y] + ((x == y && x == A[N * 3 - 1]) ? 1 : 0));
    ans += additionalPoint;
    cout << ans << endl;
}