[AtCoder] ABC 174 D – Alter Altar

2020年8月3日2020年12月14日

問題

方針

条件を満たす石の並びは、先頭から \( i  (0 \leq i \leq N)\) 個目までが赤石で、以降は白石です。\( i = 0 \) のときは全てが赤石で、\( i = N \) のときは全てが白石です。したがって、全探索によって最小回数を求めます。左右で赤と白に分かれている状態をイメージするといいかもしれません。

先頭から \( i \) 個目までに存在する赤石の数を \( a_i \) とします。また、\( a_0 = 0 \) です。このとき、\( i \) 個までに存在する白石の数は、\( i – a_i \) です。先頭から \( i \) 個までの石を赤石にして、\( i + 1 \) 個目以降を白石にする操作回数は、先に \( i \) 個目までの白石と \( i + 1 \) 個目以降の赤石を入れ替えた方が良いので、石の色を変える操作は赤にするか白にするかのどちらかになります。したがって、求める操作回数は、

\[ \max(i – a_i, a_N – a_i)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    string C;
    cin >> N >> C;
    int a[N + 1]{};
    for (int i = 0; i < N; i++) {
        if (C[i] == 'R') {
            a[i + 1] = a[i] + 1;
        } else {
            a[i + 1] = a[i];
        }
    }
    int ans = N;
    for (int i = 0; i <= N; i++) {
        int t = max(i - a[i], a[N] - a[i]);
        ans = min(ans, t);
    }
    cout << ans << "\n";
    return 0;
}