C. キャンディの均等配分

問題の本質は「奇数個のキャンディは必ず偶数を生むため分割不可」という観察にある。したがって入力が偶数であれば単純に半分に分ければよく、奇数なら即座に不可と判定する。

void judge() {
    long long N;
    std::cin >> N;
    if (N & 1) {
        std::cout << "No\n";
        return;
    }
    std::cout << "Yes\n" << N/2 << ' ' << N/2 << '\n';
}

F. AND最小全域木クエリ

各ビットマスクに対して独立なUnion-Findを持ち、辺追加時にその重みの全サブマスクに対しても頂点を併合する。クエリでは上位ビットから貪欲に AND を最大化するマスクを決定する。

struct UnionFind {
    std::vector<int> par, sz;
    UnionFind(int n) : par(n), sz(n, 1) {
        std::iota(par.begin(), par.end(), 0);
    }
    int root(int x) {
        return x == par[x] ? x : par[x] = root(par[x]);
    }
    bool unite(int a, int b) {
        a = root(a); b = root(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) std::swap(a, b);
        par[b] = a; sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b) { return root(a) == root(b); }
};

void solveF() {
    int n, q; std::cin >> n >> q;
    std::vector<UnionFind> uf(1<<12, n);

    auto spread = [&](auto &self, int u, int v, int w) -> void {
        if (uf[w].same(u, v)) return;
        uf[w].unite(u, v);
        for (int k = 0; k < 12; ++k)
            if (w >> k & 1) self(self, u, v, w ^ (1<<k));
    };

    long long ans = 0;
    while (q--) {
        char op; int u, v, w;
        std::cin >> op >> u >> v; --u; --v;
        if (op == '+') {
            std::cin >> w;
            spread(spread, u, v, w);
        } else {
            if (!uf[0].same(u, v)) { ans -= 1; continue; }
            int res = 0;
            for (int k = 11; k >= 0; --k)
                if (uf[res | (1<<k)].same(u, v))
                    res |= 1<<k;
            ans += res;
        }
    }
    std::cout << ans << '\n';
}

G. バケツ最適化問題

容量最大と流速最小のペアを優先的に結合することで、損失を最小化できる。クエリを時間昇順にソートし、条件を満たすペアを貪欲に結合する。

void solveG() {
    int n; std::cin >> n;
    long long totalV = 0;
    std::priority_queue<long long, std::vector<long long>, std::greater<>> minV;
    for (int i = 0; i < n; ++i) {
        long long v; std::cin >> v;
        totalV += v; minV.push(v);
    }
    long long totalL = 0;
    std::priority_queue<long long> maxL;
    for (int i = 0; i < n; ++i) {
        long long l; std::cin >> l;
        totalL += l; maxL.push(l);
    }

    int m; std::cin >> m;
    std::vector<std::pair<int,int>> qs(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> qs[i].first;
        qs[i].second = i;
    }
    std::sort(qs.begin(), qs.end());

    std::vector<long long> res(m);
    for (auto [t, idx] : qs) {
        while (!maxL.empty() && !minV.empty() && maxL.top() * t >= minV.top()) {
            totalL -= maxL.top(); maxL.pop();
            totalV -= minV.top(); minV.pop();
        }
        res[idx] = totalV - totalL * t;
    }
    for (long long v : res) std::cout << v << ' ';
    std::cout << '\n';
}

I. 期待値ダイナミックプログラミング

逆順DPで「残り予算」「A/B支払い済みフラグ」を状態に持ち、食堂・外食それぞれの遷移を確率に応じて最大化する。予算が尽きる場合は-1を出力。

int main() {
    int n, m; std::cin >> n >> m;
    std::vector<std::tuple<int,int,int,int,int,int>> dat(n);
    for (auto &[a,b,c,d,e,p] : dat) std::cin >> a >> b >> c >> d >> e >> p;

    const double INF = -1e18;
    std::vector<double> dp0(m+1, 0), dp1(m+1, 0);
    for (int i = n-1; i >= 0; --i) {
        auto [a,b,c,d,e,p] = dat[i];
        double prob = p / 100.0;
        std::vector<double> ndp0(m+1, INF), ndp1(m+1, INF);
        for (int money = 0; money <= m; ++money) {
            if (money >= b)
                ndp0[money] = std::max(ndp0[money], a + prob * dp1[money-b] + (1-prob) * dp1[money-b]);
            if (money >= d + e)
                ndp0[money] = std::max(ndp0[money], c + 0.0);
            else if (money >= d)
                ndp0[money] = std::max(ndp0[money], c + prob * dp1[money-d] + (1-prob) * dp1[money-d]);
        }
        dp0.swap(ndp0); dp1.swap(dp0);
    }
    if (dp0[m] < 0) std::cout << "-1\n";
    else std::cout << std::fixed << std::setprecision(10) << dp0[m] << '\n';
}

K. チェスの回避戦略

馬が最初の一手で車の利き筋を外れ、かつ再び車の射程に入らない位置へ跳ねることができれば無限に逃げ続けられる。8方向の跳躍を全探索し、条件を満たすものが1つでもあれば車は詰められない。

bool canEscape(int hx, int hy, int rx, int ry) {
    const int dx[] = {2,1,-1,-2,-2,-1,1,2};
    const int dy[] = {1,2,2,1,-1,-2,-2,-1};
    for (int k = 0; k < 8; ++k) {
        int nx = hx + dx[k], ny = hy + dy[k];
        if (nx < 1 || nx > 9 || ny < 1 || ny > 10) continue;
        if (nx == rx || ny == ry) continue;
        return true;
    }
    return false;
}