ARC 168

Thu, Jul 10, 2025

A. <Inversion>

https://atcoder.jp/contests/arc168/tasks/arc168_a

自力 AC.

数字をうまいこと選ぶことによって下降する区間の転倒数について考えればよくできる。具体的な構成方法としては公式解説にある通りに作ればよい。

減少する区間の長さ $L$ のとき、転倒数は $L(L-1)/2$ であるから、$i$ 個目の減少する区間の長さが $L_i$ のとき、求める答えは $\sum_i L_i(L_i-1)/2$ となる。

区間の長さは文字列 $S$ をランレングス圧縮して > の個数+1 を使えばよい。

vector<pair<char, long long int>> runLengthEncode(const string& input) {
    vector<pair<char, long long int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        long long int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    auto ps = runLengthEncode(S);
    ll ans = 0;
    for (auto [c, x] : ps) {
        if (c == '>')
            ans += (ll)x * (x + 1) / 2;
    }
    cout << ans << endl;
}