A. 369

整数 $C$ が存在して $A, B, C$ が等差数列となる条件は、$A+B$ が偶数であることです（$C = (A+B)/2$ が整数であることと同値）。特別な場合として、$A=B$ であれば数列の長さは1となるため、答えは1です。それ以外の場合、$A+B$ が偶数ならば $A$ と $B$ の間に整数が1つ、$A$ と $B$ の外側に整数が1つずつ存在するため、選択肢は3つになります。奇数の場合は $A$ と $B$ の間に整数はないため、選択肢は外側の2つのみです。

x, y = map(int, input().split())

if x == y:
    print(1)
elif (x + y) % 2 == 0:
    print(3)
else:
    print(2)

B. Piano 3

左手と右手の現在位置を変数で管理し、各操作ごとに移動距離を累積していきます。同じ手で連続して鍵盤を押す場合は、現在位置からターゲット位置までの距離を加算し、位置を更新します。異なる手の場合は位置の更新のみを行います。初期値は未入力として扱うため、最初の入力では距離を加算しません。

#include <iostream>
#include <cmath>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    
    long long total_dist = 0;
    int l_pos = -1, r_pos = -1;
    
    for (int i = 0; i < n; ++i) {
        int note;
        char hand;
        std::cin >> note >> hand;
        
        if (hand == 'L') {
            if (l_pos != -1) total_dist += std::abs(note - l_pos);
            l_pos = note;
        } else {
            if (r_pos != -1) total_dist += std::abs(note - r_pos);
            r_pos = note;
        }
    }
    
    std::cout << total_dist << '\n';
    return 0;
}

C. Count Arithmetic Subarrays

等差数列である連続部分配列（区間）の個数を数える問題です。公差が一定である区間を効率的に見つけるために、スライディングウィンドウ（両端のポインタ）を使用します。右端のポインタを伸ばしながら、隣接する要素の差分が一定であるかを判定し、条件を満たさなくなったら左端を進めます。各左端に対する最大の右端の位置が分かれば、その区間の長さだけ答えに加算できます。

#include <iostream>
#include <vector>

using ll = long long;

int main() {
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for (int i = 0; i < n; ++i) std::cin >> arr[i];
    
    ll count = 0;
    int right = 0;
    
    for (int left = 0; left < n; ++left) {
        while (right < n) {
            if (right > left + 1) {
                long long diff1 = arr[right] - arr[right-1];
                long long diff2 = arr[right-1] - arr[right-2];
                if (diff1 != diff2) break;
            }
            ++right;
        }
        count += right - left;
    }
    
    std::cout << count << '\n';
    return 0;
}

D. Bonus EXP

動的計画法（DP）を用いて解きます。状態として「$i$ 番目までのモンスターを見て、倒した回数の偶奇が $j$ の時の最大経験値」を持ちます。$i$ 番目のモンスターを倒す場合、倒した回数の偶奇が反転し、現在奇数回目なら経験値は2倍、偶数回目ならそのまま加算されます。倒さない場合、経験値と偶奇は変わりません。

#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

int main() {
    int n;
    std::cin >> n;
    std::vector<int> exps(n);
    for (int i = 0; i < n; ++i) std::cin >> exps[i];
    
    const ll INF = -1e18;
    std::vector<std::vector<ll>> dp(n + 1, std::vector<ll>(2, INF));
    dp[0][0] = 0;
    
    for (int i = 0; i < n; ++i) {
        int next = i + 1;
        for (int parity = 0; parity < 2; ++parity) {
            // Fight the monster
            int next_parity = parity ^ 1;
            ll gain = (parity == 1) ? exps[i] * 2 : exps[i];
            dp[next][next_parity] = std::max(dp[next][next_parity], dp[i][parity] + gain);
            
            // Skip the monster
            dp[next][parity] = std::max(dp[next][parity], dp[i][parity]);
        }
    }
    
    ll ans = std::max(dp[n][0], dp[n][1]);
    std::cout << ans << '\n';
    return 0;
}

E. Sightseeing Tour

$K \leq 5$ という小さな制約を利用します。まず、ワーシャルフロイド法を用いて全頂点間の最短距離を前計算します。次に、通る必要がある $K$ 本の辺の順序を順列で全探索し、それぞれの順序において各辺をどの向きに通るかをビット全探索します。各パターンについて、頂点0からスタートし、選択した順序と向きで辺を通りながら最後に頂点 $N-1$ に到着するまでの距離を、前計算した最短距離を用いて計算します。

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using ll = long long;

int main() {
    int n, m;
    std::cin >> n >> m;
    
    struct Edge { int u, v, cost; };
    std::vector<Edge> special_edges(m);
    
    const ll INF = 1e18;
    std::vector<std::vector<ll>> dist(n, std::vector<ll>(n, INF));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;
    
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        --a; --b;
        special_edges[i] = {a, b, c};
        dist[a][b] = std::min(dist[a][b], (ll)c);
        dist[b][a] = std::min(dist[b][a], (ll)c);
    }
    
    // Floyd-Warshall
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    
    int q;
    std::cin >> q;
    while (q--) {
        int k;
        std::cin >> k;
        std::vector<int> idxs(k);
        for (int i = 0; i < k; ++i) {
            std::cin >> idxs[i];
            --idxs[i];
        }
        
        ll min_total = INF;
        
        std::sort(idxs.begin(), idxs.end());
        do {
            for (int mask = 0; mask < (1<<k); ++mask) {
                ll current_cost = 0;
                int current_node = 0;
                
                for (int i = 0; i < k; ++i) {
                    int edge_idx = idxs[i];
                    int u = special_edges[edge_idx].u;
                    int v = special_edges[edge_idx].v;
                    int w = special_edges[edge_idx].cost;
                    
                    if (mask >> i & 1) std::swap(u, v);
                    
                    current_cost += dist[current_node][u];
                    current_cost += w;
                    current_node = v;
                }
                
                current_cost += dist[current_node][n-1];
                min_total = std::min(min_total, current_cost);
            }
        } while (std::next_permutation(idxs.begin(), idxs.end()));
        
        std::cout << min_total << '\n';
    }
    
    return 0;
}

F. Gather Coins

この問題は二次元平面上での最長増加部分列問題として扱えます。コインを行（$x$座標）の昇順にソートし、各コインの列（$y$座標）に対して、それ以前のコインで $y$座標が小さいものの中から最大のコイン数をセグメント木で管理します。セグメント木の更新時に、直前のコインのインデックスを記録しておくことで、最後にゴールからスタートへ向かってパスを復元できます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using Pair = std::pair<int, int>;

// Simple Segment Tree
class SegTree {
    int size;
    std::vector<Pair> data;
    Pair combine(Pair a, Pair b) { return std::max(a, b); }
public:
    SegTree(int n) : size(1) { while (size < n) size <<= 1; data.assign(2 * size, {0, -1}); }
    void update(int pos, Pair val) {
        pos += size;
        data[pos] = val;
        for (pos /= 2; pos; pos /= 2) data[pos] = combine(data[2*pos], data[2*pos+1]);
    }
    Pair query(int l, int r) {
        Pair res = {0, -1};
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1) res = combine(res, data[l++]);
            if (r & 1) res = combine(res, data[--r]);
        }
        return res;
    }
};

int main() {
    int h, w, n;
    std::cin >> h >> w >> n;
    
    std::vector<Pair> coins(n);
    for (int i = 0; i < n; ++i) std::cin >> coins[i].first >> coins[i].second;
    std::sort(coins.begin(), coins.end());
    
    const int MAX_COORD = 200005;
    SegTree seg(MAX_COORD);
    std::vector<int> prev_idx(n, -1);
    
    for (int i = 0; i < n; ++i) {
        int col = coins[i].second;
        auto [max_len, best_j] = seg.query(0, col);
        prev_idx[i] = best_j;
        seg.update(col, {max_len + 1, i});
    }
    
    std::string path = "";
    int curr_r = h, curr_c = w;
    
    auto move_to = [&](int tr, int tc) {
        while (curr_r > tr) { --curr_r; path += 'D'; }
        while (curr_c > tc) { --curr_c; path += 'R'; }
    };
    
    auto [length, last_i] = seg.query(0, MAX_COORD);
    
    while (last_i != -1) {
        move_to(coins[last_i].first, coins[last_i].second);
        last_i = prev_idx[last_i];
    }
    move_to(1, 1);
    
    std::reverse(path.begin(), path.end());
    std::cout << length << '\n';
    std::cout << path << '\n';
    
    return 0;
}

G. As far from as possible

答えの構造として、頂点1から選ばれた $K$ 個の頂点への距離の和の2倍が考えられます。青木君は答えを最大化するため、頂点1から遠い葉ノードを優先的に選びます。この操作は木DPを用いてシミュレートできます。各頂点において、子孫からの距離を保持したマルチセット（多重集合）を管理します。親ノードへの遷移時には、子ノードのマルチセットから最大値を取り出し、その辺の重みを加えたものを親のマルチセットにマージします。「小さい集合を大きい集合にマージする」テクニックを用いることで、計算量を $O(N \log N)$ に抑えることができます。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using ll = long long;

struct Edge { int to; long long weight; };

int main() {
    int n;
    std::cin >> n;
    std::vector<std::vector<Edge>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        --u; --v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    std::vector<ll> ans_list;
    
    auto dfs = [&](auto self, int node, int parent) -> std::multiset<ll> {
        std::multiset<ll> current_distances;
        for (const auto& e : adj[node]) {
            if (e.to == parent) continue;
            auto child_dists = self(self, e.to, node);
            
            // Extract max value from child and add edge weight
            ll max_val = *child_dists.rbegin();
            child_dists.erase(std::prev(child_dists.end()));
            child_dists.insert(max_val + e.weight);
            
            // Merge smaller set into larger set
            if (current_distances.size() < child_dists.size()) {
                std::swap(current_distances, child_dists);
            }
            current_distances.merge(child_dists);
        }
        current_distances.insert(0);
        return current_distances;
    };
    
    auto root_dists = dfs(dfs, 0, -1);
    std::vector<ll> sorted_dists(root_dists.begin(), root_dists.end());
    std::sort(sorted_dists.rbegin(), sorted_dists.rend());
    
    ll cumulative = 0;
    for (size_t i = 0; i < sorted_dists.size(); ++i) {
        cumulative += sorted_dists[i] * 2;
        std::cout << cumulative << '\n';
    }
    
    return 0;
}