ABC472

A問題

結果: AC

解説とほぼ同じ解法だ。

#include <iostream>
#include <string>

using namespace std;

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

    for (char c : s) {
        cout << (c != 'A' ? '.' : 'A');
    }

    return 0;
}

別の書き方も試す。可読性は落ちる。

for (char c : s) cout << ".A"[c == 'A'];

B問題

結果: AC

O(n^2)を避けられた。 累積和を使って実装する。

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> l(n);
    int sum = 0;

    for (auto& i : l) {
        cin >> i;
        sum += i;
        i = sum;
    }

    int ans = sum;

    for (int i = 0; i < n - 1; ++i) {
        ans = min(abs(sum - l[i] * 2), ans);
    }

    cout << ans << endl;
    return 0;
}

C問題

結果: 未AC

解説で差分計算を知り、あとは自力実装。 ただし、llに最後まで気づかず未AC。 制約は確認する。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)

using ll = long long;

int main() {
    ll n, m, k;
    cin >> n >> m >> k;

    vector<ll> a(n);
    for (auto& i : a) cin >> i;

    ll partial_sum = 0;

    rep(i, n) {
        partial_sum += a[i];
        if (i >= m) {
            partial_sum -= a[i - m];
        }

        if (partial_sum > k) {
            partial_sum -= a[i];
            a[i] = 0;
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
    }

    return 0;
}

差分計算の用途:

• スライディングウィンドウ（しゃくとり法）
• いもす法（Imos Algorithm） / 階差配列
• 動的集合の管理（std::multiset や転倒数）
• 木の上での差分計算（Tree Imos / 全方位木DP）

いずれかの問題にも応用できる。