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

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

AtCoder AGC 059 A - My Last ABC Problem (青色, 500 点)

AtCoder AGC-A AtCoder500点 青色diff 不変量 最適化テク:自明な上界が最適解 操作 最小回数・最小個数を求める クエリ処理問題 文字列 連続部分列を扱う問題 区間 0と1と2の問題 操作:区間 操作:特定の文字を特定の文字に入れ替える 数学的帰納法に基づく考察 数珠 中間値の定理 個人的要復習 最適化問題

ひたすらに迷走してしまった。今回の記事は解説というより、個人的備忘録として書く。

問題概要

一般に、'A' と 'B' と 'C' の 3 種類の文字からなる文字列 T のスコアを次のように定める

文字列 T に対して、以下の操作を繰り返し実施していく。各操作では、

  • 文字列 T の連続する区間 \lbrack l, r)
  • 文字 'A'、'B'、'C' の順列 (p_{A}, p_{B}, p_{C})

を好きなように選んで、文字列 T の区間 \lbrack l, r) において、文字 'A' を文字 p_{A} に置き換えて、文字 'B' を文字 p_{B} に置き換えて、文字 'C' を文字 p_{C} に置き換える

文字列 T が最終的に「すべての文字が等しい」という状態を達成するための、操作回数の最小値を文字列 T のスコアとする

'A' と 'B' と 'C' の 3 種類の文字からなる文字列 S が与えられるので、次の Q 回のクエリに答えよ。

各クエリでは、整数 l, r が与えられるので、 S の l 文字目から r 文字目までを抜き出した部分文字列のスコアを答えよ。

制約

  • 1 \le N \le 10^{5}
  • 1 \le Q \le 10^{5}

考えたこと

僕自身が考えたことと反省点を備忘録として残す

この手のクエリ問題では最初のステップとして、単体の文字列のスコアを求める方法を考えるのがよさそう。

まずは色々な文字列を試してみよう。"AB" のスコアは 1、"ABC" のスコアは 2、"ABCA" のスコアは 2、"ABCBA" のスコアは 2......

ひとまず、A が連続している箇所や、B が連続している箇所は、1 箇所に潰してよいことはわかった。すべての隣接箇所が異なる文字だと仮定できる。

さらに、1 回の操作を行うとき、「文字が異なる隣接箇所」が最大で 2 ずつ減りそうだとも思った (この方面の考察をやめてしまったことが悔やまれる)。しかし、

  • "ABCBA" は、文字の異なる隣接箇所が 4 箇所で、2 回の操作で OK
  • "ABCAC" は、文字の異なる隣接箇所が 4 箇所で、3 回の操作が必要

という例を見つけてしまい、(隣接箇所 + 1) / 2 という仮説をあっさり棄却してしまった。

実際には、上記の例では、前者は両端が A だが、後者はそうではない。その違いをもっとちゃんと考察できていればよかった。

ここから先は、もうひたすら迷走した。ナイーブ解法と比較できるようにとナイーブ DP を組んでみたのに、その解法さえも間違っていたりしてめちゃくちゃに。

"ABCABC" は 4 回必要だと思い込んだりもした。実際には

ABCABC → AACBBC → AAABBA → AAAAAA

と 3 回でできる。

操作の考察

迷走したまま解けずに、公式解説を読んだ。

「文字の異なる隣接箇所」が 4 箇所以上ある文字列は、1 回の操作で「文字の異なる隣接箇所」を必ず 2 減らせるとあってビックリした。それが無理だと思い込んでしまったからだ。しかしたとえば

  • ...AB...BA... のような形は、B → A によって、...AA...AA... にできる
  • ...AB...AB... のような形は、B → A、A → B によって、...AA...AA... にできる

となる。後者のパターンを見落としてしまった。確かに少し考えれば上のいずれかのパターンは必ず出現することがわかる。

文字数が少なくなった場合だけ要注意。

  • "AxA" パターン → 1 回
  • "AxyA" パターン → 2 回
  • "AB" パターン → 1 回
  • "AxB" パターン → 2 回
  • "AxyB" パターン → 2 回

これらを帰納法の起点と考えると、「文字の異なる隣接箇所」の個数を m としたとき、

  • 両端が等しいとき、(m + 1) / 2
  • 両端が異なるとき、m / 2 + 1

が答えになると予想できる。

ちゃんと証明

両端が異なっていても、うまく操作を続けて行えば、操作を上手に繰り返していくうちに「両端が等しい状態」にできるかもしれないという懸念がある。

公式解説の証明が巧みだった。まず、「両端を連結させて数珠にしても変わらない」と考察している。賢い！！

この考察によって、両端が等しい場合と異なる場合とを統一できる。両端が異なる場合には、「文字の異なる隣接箇所」が 1 増えることになって、統一的に次のように言える。

「文字の異なる隣接箇所」を m としたときに、(m + 1) / 2 が答えである

証明も明快になる。数珠にしたときの「文字の異なる隣接箇所」も、1 回の操作で 2 しか減らせないので、(m + 1) / 2 回より少ない回数は達成できない。そしてそれが実際に達成できる。QED。

コード

あとは、累積和などを用いれば OK。計算量は O(N + Q)。

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

int main() {
    // 入力
    int N, Q;
    string S;
    cin >> N >> Q >> S;

    // 区間 [0, i) における、「文字の異なる隣接箇所」の個数
    vector<int> num(N + 1, 0);
    for (int i = 1; i < N; ++i) {
        num[i+1] = num[i] + (S[i-1] != S[i]);
    }

    // クエリ処理
    while (Q--) {
        // 1-indexed にして、右開区間にする
        int l, r;
        cin >> l >> r;
        --l;

        // 文字の異なる隣接箇所 (両端が異なる場合は 1 加算)
        int m = num[r] - num[l+1];
        if (S[l] != S[r-1]) ++m;

        // 答え
        cout << (m + 1) / 2 << endl;
    }
}