2019-03-17

AtCoder AGC 031 B - Reversi (水色, 700 点)

AtCoder AtCoder700点 AGC-B DP テク:区間ごとに分割する区間分割型ナップサックDP 変化・遷移が限られる操作条件の言い換え操作:上書き操作後の結果の数え上げ数え上げ問題ダブルカウントを防ぐ場合分け操作:区間水色diff テク:区間の交差関係や包含関係を除去できる区間分割の仕方を走査する問題

これは安定感のある思考過程を経て解けた気がするので共有したい気持ち！！！

問題へのリンク

問題概要

長さ $N$ の数列 $c_1, c_2, \dots, c_N$ が与えられる。各 $c_i$ は $1$ 以上 $M$ 以下の整数値である。今、以下のような操作を何回でも行うことができる:

$c_i = c_j$ となるような $i, j (i$ < $j)$ を選んで、 $c_i$ と $c_j$ との間の区間の値をすべてその値に置き換える

こうして出来上がる数列として考えられるものの個数を 1000000007 で割ったあまりを求めよ。

制約

$1 \le N, M \le 2 × 10^{5}$

考えたこと: 区間を分割していくタイプの DP

この問題固有の性質を調べる前に、まず物凄く典型的な DP の一群について振り返ってみたいと思う。なお、紛らわしいけどこの DP は俗に「区間 DP」と呼ばれているタイプの DP とはまた別物である。。。

世の中には、以下のように、 $N$ 個のものを区間に分割する方法を最適化したり、数え上げたりする問題がたくさんある！！！

こういう問題はつまり、「どこで仕切りを入れるのか」を考えていく問題だと言える。そして DP の形としては多くの場合、

dp[ i ] := 左から i 個のところでちょうど区切る場合について、左から i 個分についての値

として、遷移を考えるときは、「前回どこで区切ったのか」を場合分けします。前回の区切りを j とすると

dp[ i ] += dp[ j ] + (何か)
chmax(dp[ i ], dp[ j ] + (何か))

といった遷移式が立つことになる。

そして何も工夫しないと多くの場合、 $O(N^{2})$ になるので、問題に応じて様々な高速化方法を考えることになる:

j の候補が高々数通りしか考えなくて良い (今回はこれ、他にソシャゲ DP と呼ばれている例など)
上手く式を解釈すると「前回の値」のみで良くなる
累積和で高速化
DP 配列をセグ木に乗せて高速化 (in-place DP)
スライド最小値で高速化
Convex Hull Trick で高速化
Monotone Minima な分割統治法で高速化

といったものたちがある。今回は、特に 1 番目の見方が自然だと思うので、それに則ってやってみる！！！

区間に対する操作の問題で考えること

今回の問題の特徴として言えることは 2 つある:

区間に対する操作である
過去の履歴をすべて破壊して上書きしてしまう操作である

このうち 2 番目の構造だとしばしば「操作を逆順に見る」という見方が有力だが、今回はあまりそれは関係なかった。もう 1 つ、区間に対する操作の問題として考えたいこととして

区間 [a, b) への操作と、区間 [c, d) への操作が交差しているとき、なんらかの方法によってそれをもっと単純なもので置き換えられないか？

というのがあると思う。例えば、以下のような見方はよくある:

このようにして結局「各区間操作は交わらないとしてよい」という結論を導くケースが多い。そして今回の問題は実は、もっと単純で、

上のようなケースでは、初期配置では

3 に対する操作を行う区間
2 に対する操作を行う区間

は互いに交差している。しかし、

3 に対する操作を先に行うと、2 に対する操作は行えなくなる
2 に対する操作を先に行うと、3 に対する操作は行えなくなる

という風になっている。つまり、操作の流れを単純化する考察をすることなく、元々

交差している 2 つの区間に対して操作を行うことはないものとしてよい

ということが言えている。注意点として、交差する区間が「同じ数字に対する操作」である場合には一応交差させることは可能だが、そのようなものを考える必要はない。。。

区間分割 DP へ！

さて、以上のことを踏まえると、この問題は「区間ごとに分割する問題」に見えて来る。

よって、区間分割する DP が自然に思い浮かぶ。そのような DP は、通常はナイーブにやると $O(N^{2})$ となって間に合わない。

しかし今回は「dp[ i ] += dp[ k ] + (何か)」という形の遷移式において、「考えられる遷移元が実質 2 通りしかない」という構造になっている！！！！！！

特に何も考えずに前回のところで区切る
手前の中から、現在の色と同じ色のところで区切る

注意点として、2 番目についてダブルカウントしないように

必ず、現在の色と同じ場所のうち、もっとも右のものを選ぶ

というルールを設ける。これをしないと以下のように、ダブルカウントを生じてしまう。必ず「同じ数字で挟む操作をするとき、挟まれた中にその数字が含まれないようにする」とすればよい。

地味な注意点

あともう 1 つ地味な注意点として、

現在の色と同じ色の手前のやつが、自身の 1 個前の要素である場合は、挟むものがないため操作をしても数列は変わらない
よって、これは「操作はできない」ものと考える

という風にした。これをしないと「操作した」「操作しない」が重複してダブルカウントしてしまう。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;

vector<int> places[210000];
long long dp[210000];
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }

int main() {
    // 入力
    int N; cin >> N;
    vector<int> c(N);
    for (int i = 0; i < N; ++i) cin >> c[i];

    // places[i] := (c[j] = i となるような j の集まり)
    for (int i = 0; i < 210000; ++i) places[i].clear();
    for (int i = 0; i < N; ++i) places[c[i]].push_back(i);

    // DP
    dp[0] = 1;
    for (int i = 1; i <= N; ++i) {
        // 特に操作しない場合
        add(dp[i], dp[i-1]);

        // 操作する場合
        int color = c[i-1];
        int it = lower_bound(places[color].begin(), places[color].end(), i-1)
            - places[color].begin(); // c[i] が color 色の何番目の要素か
        if (it > 0) {
            int j = places[color][it - 1]; // c[j] = c[i] となる j
            if ((i-1) - j > 1) add(dp[i], dp[j+1]);
        }
    }
    cout << dp[N] << endl;
}

解法 2

このような DP を高速化する例として

j の候補が高々数通りしか考えなくて良い (今回はこれ、他にソシャゲ DP と呼ばれている例など)
上手く式を解釈すると「前回の値」のみで良くなる
累積和で高速化
DP 配列をセグ木に乗せて高速化 (in-place DP)
スライド最小値で高速化
Convex Hull Trick で高速化
Monotone Minima な分割統治法で高速化

を挙げており、今回は 1 個目のパターンで解いたが、editorial では「累積和」による方法で解説している。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます