ABC 443

Table of Contents

https://atcoder.jp/contests/abc443

A. Append s

https://atcoder.jp/contests/abc443/tasks/abc443_a

2026/1/31 コンテスト中に自力 AC

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

    string s;
    cin >> s;
    cout << s + "s" << endl;
}

B. Setsubun

https://atcoder.jp/contests/abc443/tasks/abc443_b

2026/1/31 コンテスト中に自力 AC

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

    ll N, K;
    cin >> N >> K;

    ll sum = 0;
    rep(m, (ll)1e5) {
        sum += N + m;
        if (sum >= K) {
            cout << m << endl;
            return;
        }
    }
}

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

    ll N, K;
    cin >> N >> K;

    auto f = [&](ll m) -> bool {
        ll sum = (m + 1) * N + m * (m + 1) / 2;
        return sum >= K;
    };

    ll wa = -1, ac = K;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj))
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

C. Chokutter Addiction

https://atcoder.jp/contests/abc443/tasks/abc443_c

2026/1/31 コンテスト中に自力 AC

高橋くんが chokutter を開く時間を $t$ とする。

これを繰り返す。 コンテストでは $T$ を超えたときに loop を抜ける処理を入れてなかったせいで 1WA した。

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

    ll N, T;
    cin >> N >> T;
    vll A(N);
    rep(i, N) cin >> A[i];
    A.push_back(T);
    N++;

    ll ans = 0;
    ll now = 0;
    int i = 0;
    while (i < N && now < T) {
        while (i < N && A[i] < now) i++;
        ans += A[i] - now;
        now = A[i] + 100;
        i++;
    }
    cout << ans << endl;
}

D. Pawn Line

https://atcoder.jp/contests/abc443/tasks/abc443_d

2026/1/31 コンテスト中に自力 AC

重要な制約としてコマは上方向にしか動かない。

これより1番上にあるコマは動かす必要がない。 行番号が小さいコマを基準に次のように処理していく

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

    auto cal = []() -> void {
        ll N;
        cin >> N;
        vll R(N);
        rep(i, N) {
            cin >> R[i];
            R[i]--;
        }

        // row number, index
        using P = pair<ll, ll>;

        priority_queue<P, vector<P>, greater<P>> pq;
        rep(i, N) {
            pq.push({R[i], i});
        }

        ll ans = 0;
        while (pq.size()) {
            auto [num, base_id] = pq.top();
            pq.pop();

            if (R[base_id] < num) continue;
            for (ll d : {-1, 1}) {
                ll neigh_id = base_id + d;
                if (clamp(neigh_id, 0ll, N - 1) != neigh_id) continue;
                if (R[neigh_id] > num + 1) {
                    ans += R[neigh_id] - (num + 1);
                    R[neigh_id] = num + 1;
                    pq.push({num + 1, neigh_id});
                }
            }
        }
        cout << ans << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

解説に書かれていた別解法。

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

    auto cal = []() -> void {
        ll N;
        cin >> N;
        vll R(N);
        rep(i, N) {
            cin >> R[i];
            R[i]--;
        }

        vll origin = R;
        rep(_, 2) {
            rep2(i, 1, N) {
                chmin(R[i], R[i - 1] + 1);
            }
            reverse(all(R));
        }

        ll ans = 0;
        rep(i, N) {
            ans += origin[i] - R[i];
        }
        cout << ans << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

E. Climbing Silver

https://atcoder.jp/contests/abc443/tasks/abc443_e

2026/1/31 コンテスト中に自力 AC

$B_i$ を $i$ 列目の壁を壊せるかどうかのフラグとする。 $(N,i)$ 壁がある場合は $B_i=1$ と初期化する。

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

    auto cal = []() -> void {
        ll N, C;
        cin >> N >> C;
        C--;

        vector<string> grid(N);
        rep(i, N) cin >> grid[i];

        vll blocks(N);
        rep(j, N) {
            if (grid[N - 1][j] == '#') blocks[j] = 1;
        }

        vvint dp(N, vint(N));
        dp[N - 1][C] = 1;

        vint dir = {-1, 0, 1};
        ll row = N - 1;
        rep(_, N - 1) {
            rep(j, N) {
                if (dp[row][j]) {
                    for (ll d : dir) {
                        ll nj = j + d;
                        if (clamp(nj, 0ll, N - 1) != nj) continue;
                        if (grid[row - 1][nj] == '#' && blocks[nj]) continue;
                        grid[row - 1][nj] = '.';
                        dp[row - 1][nj] = 1;
                    }
                }
            }

            row--;
            rep(j, N) {
                if (grid[row][j] == '#') blocks[j] = 1;
            }
        }

        string ans = "";
        rep(i, N) ans.push_back(dp[0][i] ? '1' : '0');
        cout << ans << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

F. Non-Increasing Number

https://atcoder.jp/contests/abc443/tasks/abc443_f

G. Another Mod of Linear Problem

https://atcoder.jp/contests/abc443/tasks/abc443_g