【AtCoder】ABC 421 C - Alternated | 緑コーダーが解くAtCoder

配点: 350 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 378 / NoviSteps: ???

問題概要
制約
考察
実装例
コメント

問題概要

長さ $2N$ の文字列 $S$ が与えられる。 $S$ はA, Bを $N$ 個ずつ含む。 $S$ に対して隣り合う文字を入れ替える操作を0回以上行って、同じ文字が隣り合う箇所がない状態にするために必要な操作回数の最小値を求めよ。

制約

$1\leq N \leq 5\times 10^5$
$N$ は整数

考察

重要な考察として、最終的な文字列の状態 $T$ にはABAB ... ABとBABA ... BAの2パターンしかない。

また、 $S$ におけるAの順序と $T$ におけるAの順序を入れ替えるような操作はする必要がない。

したがって、 $S$ における先頭から $i$ 番目のAを、 $T$ における先頭から $i$ 番目のAに移すための操作回数を最小化すればよい。

この回数は、　 $\mathrm{pos\_A}_i$ を $S$ における先頭から $i$ 番目のAのインデックスを格納した配列とすれば、例えば $T =$ ABAB ... ABなら、Aは $T$ の偶数番目に配置したいので、

$\begin{align*} \sum_{i=0}^{N} |\mathrm{pos\_A}_i - 2i| \end{align*}$

であり、 $T =$ BABA ... BAなら、Aは $T$ の奇数番目に配置したいので、

$\begin{align*} \sum_{i=0}^{N} |\mathrm{pos\_A}_i - (2i+1)| \end{align*}$

と計算できる。

あとは両者の小さい方を答えとすればよい。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

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

    vector<int> pos_A;
    rep(i, 0, 2 * N)
    {
        if (S[i] == 'A')
            pos_A.push_back(i);
    }

    ll cost1 = 0, cost2 = 0;
    rep(i, 0, N)
    {
        cost1 += abs(pos_A[i] - (2 * i));
        cost2 += abs(pos_A[i] - (2 * i + 1));
    }

    cout << min(cost1, cost2) << endl;

    return 0;
}