ABC 313

Tue, Feb 17, 2026

https://atcoder.jp/contests/abc313

A. To Be Saikyo

https://atcoder.jp/contests/abc313/tasks/abc313_a

B. Who is Saikyo?

https://atcoder.jp/contests/abc313/tasks/abc313_b

C. Approximate Equalization 2

https://atcoder.jp/contests/abc313/tasks/abc313_c

D. Odd or Even

https://atcoder.jp/contests/abc313/tasks/abc313_d

2026/2/17 数日かけて自力 AC

$K+1$ 回の質問で初めの $K+1$ 個の数字が何であるかが決定できる。残りの数字はここで決まった $K-1$ 個の数字とまだ使っていない数字で質問することで新規の分の数字を決定できる。

例えば $K=3$ のとき、次のように質問する。

+----+---+---+---+---+
|    | 1 | 2 | 3 | 4 |
+----+---+---+---+---+
| Q1 |   | o | o | o |
+----+---+---+---+---+
| Q2 | o |   | o | o |
+----+---+---+---+---+
| Q3 | o | o |   | o |
+----+---+---+---+---+
| Q4 | o | o | o |   |
+----+---+---+---+---+

$Q_2 \oplus Q_3 \oplus Q_4$ の結果から1つ目の数字がわかる。同様にして $Q_1 \oplus Q_3 \oplus Q_4$ から2つ目の数字、 $Q_1 \oplus Q_2 \oplus Q_4$ から3つ目の数字、 $Q_1 \oplus Q_2 \oplus Q_3$ から4つ目の数字がわかる。

$K$ が奇数であるので列単位で見たときに o の数が $K$ 個となるような質問を組み合わせて XOR を取ると着目した列以外の数字の出現回数は偶数階なので XOR を取ると消すことができる。

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

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

    vvint qs(N, vint(N));
    rep(i, K + 1) rep(j, K + 1) {
        qs[i][j] = 1;
        if (i == j) qs[i][j] = 0;
    }

    rep2(i, K + 1, N) rep(j, K - 1) {
        qs[i][j] = 1;
    }
    rep2(i, K + 1, N) qs[i][i] = 1;

    vll ret(N);
    rep(i, N) {
        cout << "?";
        rep(j, N) {
            if (qs[i][j]) cout << ' ' << j + 1;
        }
        cout << endl;
        cout << flush;

        ll t;
        cin >> t;
        ret[i] = t;
    }

    int parity = 0;
    rep(i, K + 1) parity ^= ret[i];

    vll ans(N);
    rep(i, K + 1) {
        ans[i] = parity ^ ret[i];
    }

    int head = 0;
    rep(i, K - 1) {
        head ^= ans[i];
    }

    rep2(i, K + 1, N) {
        ans[i] = head ^ ret[i];
    }

    cout << "! ";
    print(ans);
}

E. Duplicate

https://atcoder.jp/contests/abc313/tasks/abc313_e

2026/2/18 数日かけて自力 AC

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

    ll N;
    string S;
    cin >> N >> S;
    rep(i, N - 1) {
        if (S[i] != '1' && S[i + 1] != '1') {
            cout << -1 << endl;
            return;
        }
    }

    using P = pair<mint, ll>;
    deque<P> deq;
    ll cnt = 0;
    rep(i, N) {
        if (S[i] != '1') {
            deq.push_back({cnt, S[i] - '0'});
            cnt = 0;
        } else {
            cnt++;
        }
    }
    if (cnt) deq.push_back({cnt, 1});

    mint ans = 0;
    while (deq.size()) {
        auto [num, d] = deq.back();
        deq.pop_back();
        if (num == 0) {
            break;
        }

        if (d != 1)
            ans += num + (d - 1) * (ans + 1);
        else
            ans += num - 1;
        if (deq.size()) ans++;
    }

    cout << ans.val() << endl;
}