ABC 441

Sat, Jan 17, 2026

A. Black Square

https://atcoder.jp/contests/abc441/tasks/abc441_a

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

    ll P, Q, X, Y;
    cin >> P >> Q >> X >> Y;

    yesno(P <= X && X < P + 100 && Q <= Y && Y < Q + 100);
}

B. Two Languages

https://atcoder.jp/contests/abc441/tasks/abc441_b

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

    ll N, M;
    cin >> N >> M;

    string S, T;
    cin >> S >> T;

    ll Q;
    cin >> Q;

    set<char> takahashi, aoki;
    for (char c : S) takahashi.insert(c);
    for (char c : T) aoki.insert(c);

    rep(i, Q) {
        string w;
        cin >> w;

        ll state = 0;
        {
            int ok = 1;
            for (char c : w) {
                if (!takahashi.count(c)) ok = 0;
            }
            if (ok) state += 1;
        }
        {
            int ok = 1;
            for (char c : w) {
                if (!aoki.count(c)) ok = 0;
            }
            if (ok) state += 2;
        }

        string ans = "Unknown";
        if (state == 1) ans = "Takahashi";
        if (state == 2) ans = "Aoki";
        cout << ans << endl;
    }
}

C. Sake or Water

https://atcoder.jp/contests/abc441/tasks/abc441_c

結果に影響しないので $A$ は昇順にソートしておく。

$\sum_{i=1}^K A_i < X$ 場合は容量が少ない方から $K$ 個を日本酒が入っていることにすると $X$ 以上にできないことが確定するので $-1$ を出力。

$\sum_{i=1}^K A_i \geq X$ の場合、小さい方から $K$ 個が日本酒、後半 $N-K$ 個が水となっているケースが最悪のケースで、このとき水は全て選び、残りの $K$ 個の日本酒の中から容量の合計が $X$ 以上になるまでカップを選ぶ。このときカップは容量が多い順から選ぶのが最適。

コンテスト中は容量が小さい方から選ぶとしてしまって 2 WA 出してしまった。

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

    ll N, K, X;
    cin >> N >> K >> X;
    vll A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));

    {
        ll sum = 0;
        rep(i, K) sum += A[i];
        if (sum < X) {
            cout << -1 << endl;
            return;
        }
    }

    ll ans = N - K;

    ll sum = 0;
    for (int i = K - 1; i >= 0; i--) {
        sum += A[i];
        ans++;
        if (sum >= X) break;
    }
    cout << ans << endl;
}

D. Paid Walk

https://atcoder.jp/contests/abc441/tasks/abc441_d

出次数が4以下で辺をたどる回数が $L$ なので愚直に全探索すると $4^L = 1,048,576$ なので愚直に全探索すればよい。コンテストでは $L$ 回辿ったがコストの合計が条件を満たさなかったときに return していなかったせいで TLE を起こしてしまった。

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

    ll N, M, L, S, T;
    cin >> N >> M >> L >> S >> T;

    // to, cost
    using P = pair<ll, ll>;

    vector<vector<P>> graph(N);
    rep(i, M) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        graph[u].push_back({v, c});
    }

    vint visited(N);
    ll cnt = 0;

    auto dfs = [&](auto dfs, int now, int depth, ll sum) -> void {
        if (cnt == N) return;
        if (sum > T) return;
        if (depth == L) {
            if (S <= sum && sum <= T) {
                if (!visited[now]) cnt++;
                visited[now] = 1;
            }
            return;
        }

        for (auto [nx, cost] : graph[now]) {
            if (sum + cost > T) continue;
            dfs(dfs, nx, depth + 1, sum + cost);
        }
    };

    dfs(dfs, 0, 0, 0);

    vint ans;
    rep(i, N) {
        if (visited[i]) ans.push_back(i + 1);
    }
    print(ans);
}

E. A > B substring

https://atcoder.jp/contests/abc441/tasks/abc441_e

$A$ を $+1$, $B$ を $-1$, $C$ を $0$ としてに置き換えた数列を $X$ とする。$X$ の累積和をまず取る。また $Y_i = \sum_{j=1}^i$ とする。

例えば AACBBBCAC では以下のようになる。

i	1	2	3	4	5	6	7	8	9
S	A	A	C	B	B	B	C	A	C
$X_i$	1	1	0	-1	-1	-1	0	1	0
$Y_i$	1	2	2	1	0	-1	-1	0	0

また累積和として出現する数を出現回数を数えておく。上記の例では (number, freq) = (-1, 2), (0, 3), (1, 2), (2, 2) である。

$offset = 0$ からスタートし $i$ を $1$ から $N$ まで以下の操作を繰り返す。

$i$ 文字目の左端としたときに、区間に含まれる $A$ の数が $B$ よりも多くなる右端の選び方は $Y_j > \text{offset}, (i \leq j \leq N)$ を満たす $j$ の個数である。愚直に調べると $O(N)$ かかるので $Y_i$ の値と出現回数を座標圧縮の容量でデータとして持っておき、条件を満たす個数は fenwick tree や segment tree で高速に計算すればよい。

$i$ 文字目が $A$ の場合、$i+1$ 文字目以降の累積和全体的に -1 されるが、愚直にそんなことをやると TLE するので、offset を1増やすことで実質的に全体的に -1 したことと同じになる。$i$ 文字目が $B$ の場合は offset を -1 して $C$ の場合は何もしない。 1文字終わるごとに $Y_i$ の出現回数は -1 する。

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

    ll N;
    string S;
    cin >> N >> S;

    vll cm(N);
    if (S[0] == 'A') cm[0] = 1;
    if (S[0] == 'B') cm[0] = -1;
    rep2(i, 1, N) {
        ll x = 0;
        if (S[i] == 'A') x = 1;
        if (S[i] == 'B') x = -1;
        cm[i] = cm[i - 1] + x;
    }

    map<ll, ll> cnts;
    rep(i, N) {
        cnts[cm[i]]++;
    }

    int m = cnts.size();
    fenwick_tree<ll> fw(m);

    vll ks;
    {
        int i = 0;
        for (auto [key, freq] : cnts) {
            ks.push_back(key);
            fw.add(i, freq);
            i++;
        }
    }

    ll offset = 0;
    ll ans = 0;
    rep(i, N) {
        char c = S[i];
        auto it = upper_bound(all(ks), offset);
        if (it != ks.end()) {
            ll l = it - ks.begin();
            ans += fw.sum(l, m);
        }

        if (c == 'A') {
            offset++;
        }
        if (c == 'B') {
            offset--;
        }
        ll l = lower_bound(all(ks), cm[i]) - ks.begin();
        fw.add(l, -1);
    }
    cout << ans << endl;
}

2026/1/18 解き直し

累積和のところで負数が出てくるのが面倒なので全てに $N$ を足して $0 \leq x \leq 2N$ の値に変換して扱う。このとき offset は $N$ から始める。 $offset + 1$ 以上の値を出現個数を fenwick tree などで高速に求めればいい

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

    ll N;
    string S;
    cin >> N >> S;

    vll cm(N);
    if (S[0] == 'A') cm[0] = 1;
    if (S[0] == 'B') cm[0] = -1;
    rep2(i, 1, N) {
        ll x = 0;
        if (S[i] == 'A') x = 1;
        if (S[i] == 'B') x = -1;
        cm[i] = cm[i - 1] + x;
    }

    rep(i, N) cm[i] += N;

    vll freq(N * 2 + 1);
    for (auto x : cm) freq[x]++;
    fenwick_tree<ll> fw(N * 2 + 1);
    rep(i, N * 2 + 1) fw.add(i, freq[i]);

    ll ans = 0;
    ll offset = N;
    rep(i, N) {
        ans += fw.sum(offset + 1, N * 2 + 1);
        if (S[i] == 'A')
            offset++;
        else if (S[i] == 'B')
            offset--;
        fw.add(cm[i], -1);
    }
    cout << ans << endl;
}

2026/1/19 解き直し 2

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

    ll N;
    string S;
    cin >> N >> S;

    fenwick_tree<ll> fw(N * 2 + 1);
    ll offset = N;
    ll ans = 0;
    rep(i, N) {
        fw.add(offset, 1);
        if (S[i] == 'A') {
            offset++;
        }
        if (S[i] == 'B') {
            offset--;
        }
        ans += fw.sum(0, offset);
    }
    cout << ans << endl;
}

F. Must Buy

https://atcoder.jp/contests/abc441/tasks/abc441_f

2026/2/24 解説 AC

コンテストの日は解説読んでもよくわからなかったが、AWC0011 E を解いていたらこの問題も同じような考え方で解けることに気づいて解き直し AC できた。

https://atcoder.jp/contests/awc0011/tasks/awc0011_e

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

    ll N, M;
    cin >> N >> M;
    vll P(N + 2), V(N + 2);
    rep(i, N) cin >> P[i + 1] >> V[i + 1];

    // dp[i][j]: 1~i 番目の商品を使って値段が j 円以下のときの価値の最大値
    vvll dp(N + 2, vll(M + 1));

    // dp[i][j]: i 番目以降の商品を使って値段が j 円以下のときの価値の最大値
    vvll dp2(N + 2, vll(M + 1));

    rep(_, 2) {
        rep2(i, 1, N + 1) {
            rep(p, M + 1) {
                chmax(dp[i][p], dp[i - 1][p]);
                if (p > 0)
                    chmax(dp[i][p], dp[i][p - 1]);
                if (p - P[i] < 0) continue;
                chmax(dp[i][p], dp[i - 1][p - P[i]] + V[i]);
            }
        }
        swap(dp, dp2);
        reverse(all(P));
        reverse(all(V));
    }
    reverse(all(dp2));

    ll mxval = dp[N][M];

    vint memo(N + 1);
    rep2(i, 1, N + 1) {
        rep(p, M + 1) {
            // i 番目の商品を使わないで最大価値を達成できるか
            if (M - p >= 0 && dp[i - 1][p] + dp2[i + 1][M - p] == mxval) {
                memo[i] |= 1;
            }

            // i 番目の商品を使って最大価値を達成できるか
            if (M - p - P[i] >= 0 && dp[i - 1][p] + V[i] + dp2[i + 1][M - p - P[i]] == mxval) {
                memo[i] |= 2;
            }
        }
    }

    string ans;

    rep2(i, 1, N + 1) {
        int x = memo[i];
        if (x == 1) {
            ans.push_back('C');
        } else if (x == 3) {
            ans.push_back('B');
        } else if (x == 2) {
            ans.push_back('A');
        }
    }

    cout << ans << endl;
}

G. Takoyaki and Flip

https://atcoder.jp/contests/abc441/tasks/abc441_g