Mister雑記

競プロやります。

AGC029-A 「Irreversible operation」 (300)

atcoder.jp

概要

 N個のオセロ石が直線状に並んでいて、左から i個目の石の色は最初 S_i ( W B) である。

このオセロ石に対して、以下の操作を考える。

  •  S_i = B, S_{i + 1} = Wなる iを1つ選び、 S_i = W, S_{i + 1} = Bに置き換える(要は2つの石をひっくり返す)。

この操作を最大何回行えるか求めよ。

制約

  •  1 \leq |S| \leq 2 \times 10^5

解説

 BW WBに入れ替える」、という操作を何回行えるか求める問題。

これが直感的に出るかというと厳しいかもしれないが、最終的な状態は

 \displaystyle WWW \dots WWBB \dots BBB

のように、全ての Wの後に Bが並ぶ形になる。

証明としては、「もし上の形でない場合は、 BWという並びが必ずどこかに存在する」ことから示せる。また面白いことに、「操作できる箇所があれば操作を行う」を繰り返すと、操作の手順に関係なく必ず上の形になる。


ではこの状態にするまでに必要な操作回数は何回だろうか。最大 10^{10}回の操作が必要になるので、シミュレーションは厳しい。

そこで、 T := S_i = Wなる iの合計」という値に注目する。例えば S = WWBBWなら T = 1 + 2 + 5 = 8となる。

1回の操作で Tがどれだけ変化するかというと、これは常に -1である。

さらに Wの個数を wと置くと、最終状態において

 \displaystyle T = \sum_{i = 1}^{w} i = \dfrac{1}{2}w(w + 1)

となる。つまり初期状態における Tからこれを引けば、答えである操作回数が求められる。

実装例

以下の実装例では上と違って1-indexedになっていることに注意。そのため最終状態における Tの式が上と異なる。

#include <iostream>
#include <string>

using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;

    ll T = 0, w = 0;
    for (ll i = 0; i < S.size(); ++i) {
        if (S[i] == 'W') {
            T += i;
            ++w;
        }
    }

    ll sum = w * (w - 1) / 2;
    // 最終状態におけるT

    cout << T - sum << endl;
    return 0;
}

なお答えの最大値は 10^{10}と、intではオーバーフローすることに注意。これは慣れていないととても気が付きにくい。

感想

  • 実にAGC-Aらしい典型感。
  • ちなみに操作を「 BWをswapする」と見なすと、答えが転倒数であることが分かる。
  • 本番では「左から i番目の Wは最終的に i文字目に来る」と考えて実装していた。
    • もしかしたらこっちの方が分かりやすい?