A - Digit Game

正整数 $n$ が与えられたとき、先手は奇数インデックスの位置、後手は偶数インデックスの位置を交互に消去していく。最後に残った数字の奇偶性によって勝者が決定する。二人が最適に行動する場合の勝者を判定する。

最後に残る位置は $n$ の偶奇によって一意に定まる。$n$ が奇数の場合は先手が制御する位置（0-indexed で偶数インデックス）、$n$ が偶数の場合は後手が制御する位置（奇数インデックス）が残る。対応するインデックス群に勝者が必要な奇偶性の数字が少なくとも1つ存在すれば、そのプレイヤーが必勝となる。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    
    bool first_can_force_odd = false;
    bool second_can_force_even = false;

    // 先手は 0, 2, 4... のインデックスを掌握
    for (int i = 0; i < n; i += 2) {
        if ((s[i] - '0') % 2 != 0) first_can_force_odd = true;
    }
    // 後手は 1, 3, 5... のインデックスを掌握
    for (int i = 1; i < n; i += 2) {
        if ((s[i] - '0') % 2 == 0) second_can_force_even = true;
    }

    // 最後の残りがどちらのターンか判定
    if (n % 2 == 1) {
        cout << (first_can_force_odd ? 1 : 2) << '\n';
    } else {
        cout << (second_can_force_even ? 2 : 1) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

B - Stairs

高さ $x$ の階段は $x$ 段あり、$i$ 段目の高さは $i$ である。この階段がちょうど $x$ 個の正方形で隙間なく覆えるとき「良い階段」と呼ぶ。与えられたレンガの総数 $n$ 以下で作れる「良い階段」の最大個数を求める。

数学的な考察により、良い階段の段数 $x$ は $2^k - 1$ の形に限定されることが分かる。段数 $x$ の階段に必要なレンガ数は三角数 $T_x = x(x+1)/2$ である。$k=1,2,\dots$ に対して $T_{2^k-1}$ を計算し、累積和が $n$ を超えない範囲で個数を数え上げればよい。

#include <iostream>
using namespace std;

void solve() {
    long long limit;
    cin >> limit;
    long long consumed = 0;
    int count = 0;
    for (int k = 1; ; ++k) {
        long long x = (1LL << k) - 1;
        long long bricks = x * (x + 1) / 2;
        if (consumed + bricks > limit) break;
        consumed += bricks;
        ++count;
    }
    cout << count << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C - Killjoy

$n$ 人のユーザーと root が存在し、root の rating は $x$ である。試合を行うと rating の総和は変化せず、同じ rating を持つユーザー同士で感染が拡大する。初期状態から最小何試合で全員に感染するかを求める。

場合分けは以下の通りである。

• 初期状態で全員が rating $x$ を持っていれば $0$ 回。
• 1人以上が $x$ を持っていれば、残りのユーザーを操作で $x$ に統一できるため $1$ 回。
• 誰も持っていないが、全ユーザーの rating 平均が $x$ であれば、1試合で全員を $x$ にできるため $1$ 回。
• それ以外は最大 $2$ 回で感染させられる。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void solve() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> ratings(n);
    long long sum = 0;
    bool has_target = false;
    for (int i = 0; i < n; ++i) {
        cin >> ratings[i];
        sum += ratings[i];
        if (ratings[i] == target) has_target = true;
    }

    bool all_same = true;
    for (long long v : ratings) if (v != target) all_same = false;

    if (all_same) cout << 0 << '\n';
    else if (has_target || (sum % n == 0 && sum / n == target)) cout << 1 << '\n';
    else cout << 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D1 / D2 - Sage's Birthday

配列 $a$ を並べ替え、両隣の値より厳密に小さい要素の数を最大化する。最大値と配列の一例を出力する。

答え $k$ について単調性が成り立つため二分探索が適用可能。候補値 $mid$ に対し、ソート済みの配列を用いて貪欲に配置する。小さい要素から順に偶数インデックスに、大きい要素から順に奇数インデックスに配置することで、局所最小値を効率よく作成できる。配置後の条件を満たすか検証し、二分探索を更新する。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool verify(int target, int n, const vector<int>& sorted_a, vector<int>& out) {
    out.assign(n, 0);
    int small_ptr = 0, large_ptr = n - 1;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) out[i] = sorted_a[small_ptr++];
        else out[i] = sorted_a[large_ptr--];
    }
    int cnt = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (out[i] < out[i-1] && out[i] < out[i+1]) ++cnt;
    }
    return cnt >= target;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    vector<int> best_arr(n);
    int max_k = 0;
    int lo = 0, hi = (n - 1) / 2;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        vector<int> temp;
        if (verify(mid, n, a, temp)) {
            max_k = mid;
            best_arr = temp;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << max_k << '\n';
    for (int i = 0; i < n; ++i) cout << best_arr[i] << (i == n-1 ? "" : " ");
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) solve();
    return 0;
}

E - Decryption

合数 $n$ の $1$ より大きい約数を環状に並べる。隣接する2数の最小公倍数を間に挿入して隣接要素が互いに素でなくなるようにする。必要な挿入回数の最小値と、その後の数列を出力する。

隣接要素が互いに素にならない条件は、共通の素因数を持つことと同値である。約数を素因数ごとにグループ化し、各グループ内で連続するように配置する。グループ間の接続を考慮し、先頭と末尾の素因数の冪乗を適切にスワップすることで、連結を維持したまま環状構造を構築できる。特殊ケース（素因数が2種類で両方次数1）のみ例外処理を行う。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> prime_info;
vector<int> partial_divs;

void generate(int idx, int val) {
    if (idx == prime_info.size()) {
        partial_divs.push_back(val);
        return;
    }
    int p = prime_info[idx].second;
    int max_k = prime_info[idx].first;
    int cur = val;
    for (int k = 0; k <= max_k; ++k) {
        generate(idx + 1, cur);
        cur *= p;
    }
}

void solve() {
    long long n_in;
    cin >> n_in;
    prime_info.clear();
    partial_divs.clear();
    long long tmp = n_in;
    for (long long i = 2; i * i <= tmp; ++i) {
        if (tmp % i == 0) {
            int c = 0;
            while (tmp % i == 0) tmp /= i, ++c;
            prime_info.push_back({c, (int)i});
        }
    }
    if (tmp > 1) prime_info.push_back({1, (int)tmp});

    generate(0, 1);
    partial_divs.erase(partial_divs.begin());

    if (prime_info.size() == 2 && prime_info[0].first == 1 && prime_info[1].first == 1) {
        cout << prime_info[0].second << " " << prime_info[1].second << " " << n_in << "\n1\n";
        return;
    }

    vector<int> result;
    for (size_t i = 0; i < prime_info.size(); ++i) {
        partial_divs.clear();
        generate(i + 1, 1);
        vector<int> group;
        for (int base : partial_divs) {
            int mul = 1;
            for (int k = 0; k <= prime_info[i].first; ++k) {
                group.push_back(base * mul);
                mul *= prime_info[i].second;
            }
        }
        for (size_t j = 0; j < group.size(); ++j) {
            if (i + 1 < prime_info.size() && group[j] == (int)(prime_info[i].second * prime_info[i+1].second)) {
                swap(group[j], group.back());
            }
            if (i == 0) {
                if (prime_info.size() > 2 && group[j] == (int)(prime_info[i].second * prime_info.back().second)) {
                    swap(group[j], group.front());
                }
            }
        }
        result.insert(result.end(), group.begin(), group.end());
    }
    for (size_t i = 0; i < result.size(); ++i) cout << result[i] << " ";
    cout << "\n0\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

F - Rain of Fire

平面上の $n$ 点を全て visits するための最小距離 $t$ を求める。各点から同行・同列の距離 $t$ 以内の点に移動できる。最大1つの補助点を追加可能。

答え $t$ について単調性が成り立つため二分探索を行う。判定関数では、各行・列ごとに距離 $t$ 以内の最近傍ノードのみ辺を張るグラフを構築し、連結成分数を求める。成分数が1であれば成立。成分数が2以下の場合は、行または列の隙間に補助点を置いて連結できるか確認する。成分数が3〜4の場合は、座標圧縮後の行・列の交点候補すべてを試す。交点候補における隣接成分の集合が全ての連結成分をカバーすれば、1点追加で全域連結が可能となる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct Pt { int x, y, id; };
int n;
vector<Pt> points;
vector<int> cx, cy;
vector<vector<Pt>> rows, cols;
vector<vector<int>> adj;
vector<int> comp_id;
int comp_cnt;

void dfs(int u) {
    comp_id[u] = comp_cnt;
    for (int v : adj[u]) {
        if (comp_id[v] == 0) dfs(v);
    }
}

bool test(int t) {
    adj.assign(n + 1, vector<int>());
    for (int i = 0; i < (int)cx.size(); ++i) {
        for (size_t j = 1; j < rows[i].size(); ++j) {
            if (rows[i][j].y - rows[i][j-1].y <= t) {
                adj[rows[i][j].id].push_back(rows[i][j-1].id);
                adj[rows[i][j-1].id].push_back(rows[i][j].id);
            }
        }
    }
    for (int i = 0; i < (int)cy.size(); ++i) {
        for (size_t j = 1; j < cols[i].size(); ++j) {
            if (cols[i][j].x - cols[i][j-1].x <= t) {
                adj[cols[i][j].id].push_back(cols[i][j-1].id);
                adj[cols[i][j-1].id].push_back(cols[i][j].id);
            }
        }
    }

    comp_id.assign(n + 1, 0);
    comp_cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (comp_id[i] == 0) {
            ++comp_cnt;
            dfs(i);
        }
    }
    if (comp_cnt == 1) return true;

    if (comp_cnt == 2) {
        for (int i = 0; i < (int)cx.size(); ++i) {
            for (size_t j = 1; j < rows[i].size(); ++j) {
                if (comp_id[rows[i][j].id] != comp_id[rows[i][j-1].id] &&
                    (rows[i][j].y - rows[i][j-1].y + 1) / 2 <= t) return true;
            }
        }
        for (int i = 0; i < (int)cy.size(); ++i) {
            for (size_t j = 1; j < cols[i].size(); ++j) {
                if (comp_id[cols[i][j].id] != comp_id[cols[i][j-1].id] &&
                    (cols[i][j].x - cols[i][j-1].x + 1) / 2 <= t) return true;
            }
        }
    }

    if (comp_cnt <= 4) {
        vector<int> rp(cx.size(), 0), cp(cy.size(), 0);
        for (size_t i = 0; i < cx.size(); ++i) {
            for (size_t j = 0; j < cy.size(); ++j) {
                long long px = cx[i], py = cy[j];
                while (rp[i] < (int)rows[i].size() && rows[i][rp[i]].y < py) rp[i]++;
                while (cp[j] < (int)cols[j].size() && cols[j][cp[j]].x < px) cp[j]++;

                set<int> seen;
                if (rp[i] < (int)rows[i].size() && abs(rows[i][rp[i]].y - py) <= t) seen.insert(comp_id[rows[i][rp[i]].id]);
                if (rp[i] > 0 && abs(rows[i][rp[i]-1].y - py) <= t) seen.insert(comp_id[rows[i][rp[i]-1].id]);
                if (cp[j] < (int)cols[j].size() && abs(cols[j][cp[j]].x - px) <= t) seen.insert(comp_id[cols[j][cp[j]].id]);
                if (cp[j] > 0 && abs(cols[j][cp[j]-1].x - px) <= t) seen.insert(comp_id[cols[j][cp[j]-1].id]);

                if ((int)seen.size() == comp_cnt) return true;
            }
        }
    }
    return false;
}

void solve() {
    cin >> n;
    points.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        points[i].id = i + 1;
        cx.push_back(points[i].x);
        cy.push_back(points[i].y);
    }
    sort(cx.begin(), cx.end());
    cx.erase(unique(cx.begin(), cx.end()), cx.end());
    sort(cy.begin(), cy.end());
    cy.erase(unique(cy.begin(), cy.end()), cy.end());

    rows.assign(cx.size(), vector<Pt>());
    cols.assign(cy.size(), vector<Pt>());
    for (int i = 0; i < n; ++i) {
        int rx = lower_bound(cx.begin(), cx.end(), points[i].x) - cx.begin();
        int ry = lower_bound(cy.begin(), cy.end(), points[i].y) - cy.begin();
        rows[rx].push_back(points[i]);
        cols[ry].push_back(points[i]);
    }
    for (auto& r : rows) sort(r.begin(), r.end(), [](const Pt& a, const Pt& b){ return a.y < b.y; });
    for (auto& c : cols) sort(c.begin(), c.end(), [](const Pt& a, const Pt& b){ return a.x < b.x; });

    int lo = 0, hi = 2000000000, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (test(mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}