A - Middle Letter

奇数長の文字列が与えられるので、その中央の文字を出力します。

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::string input_str;
    std::cin >> input_str;
    // 0-indexedなので、長さLの文字列の中央は L/2
    std::cout <>> input_str[input_str.length() / 2] << '\n';
    return 0;
}

B - Modulo Number

与えられた整数 \(N\) (範囲: \([-10^{18}, 10^{18}]\)) と法 \(M = 998244353\) に対して、\(0 \le x < M\) かつ \((N-x) \pmod M = 0\) を満たす整数 \(x\) を求めます。

これは、\(N \equiv x \pmod M\) を満たす \(x\) を求める問題と同じです。C++の `%` 演算子は負の数に対して負の結果を返すことがあるため、適切な処理が必要です。具体的には `(N % M + M) % M` で \(0 \le x < M\) の範囲に収めることができます。

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    long long input_n;
    std::cin >> input_n;
    long long modulus = 998244353LL;

    // Nをmodulusで割った余りを求め、負の場合はmodulusを加算して非負にする
    long long result_x = input_n % modulus;
    if (result_x < 0) {
        result_x += modulus;
    }
    std::cout <>> result_x << '\n';
    return 0;
}

C - Convex Quadrilateral

4つの点の座標が与えられ、それらが凸四角形を構成するかどうかを判定します。点に重複や共線性はなく、隣接しない辺が交差することもないため、必ず四角形を形成します。

凸多角形であるかどうかの判定は、全ての頂点について「曲がる方向」が一定であるかを確認することで行えます。例えば、点P1, P2, P3, P4 が反時計回りに与えられていると仮定した場合、ベクトルP1P2とP2P3の外積、P2P3とP3P4の外積、P3P4とP4P1の外積、P4P1とP1P2の外積が全て同じ符号を持つならば凸多角形です。外積の代わりに、各頂点における左右判定（クロス積の符号）を利用します。

点 \(P_i = (x_i, y_i)\) とし、3点 \(P_a, P_b, P_c\) が与えられたとき、ベクトル \(\vec{P_a P_b}\) と \(\vec{P_b P_c}\) の2次元クロス積は \((x_b - x_a)(y_c - y_b) - (y_b - y_a)(x_c - x_b)\) で計算できます。この値が正なら左折、負なら右折、0なら共線です。四角形が凸であるためには、隣接する3点で作る全ての角が同じ方向（全て左折または全て右折）である必要があります。

#include <iostream>
#include <vector>

// 点を表す構造体
struct Point {
    long long x, y;
};

// 2次元ベクトルaとbのクロス積を計算
// (a.x * b.y - a.y * b.x)
// P1, P2, P3が与えられたとき、(P2-P1) と (P3-P2) のクロス積
// 結果が正なら左折、負なら右折、0なら共線
long long cross_product(Point p1, Point p2, Point p3) {
    long long vec1_x = p2.x - p1.x;
    long long vec1_y = p2.y - p1.y;
    long long vec2_x = p3.x - p2.x;
    long long vec2_y = p3.y - p2.y;
    return vec1_x * vec2_y - vec1_y * vec2_x;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::vector<Point> points(4);
    for (int i = 0; i < 4; ++i) {
        std::cin >> points[i].x >> points[i].y;
    }

    // 各頂点における曲がり方をチェック (P1-P2-P3, P2-P3-P4, P3-P4-P1, P4-P1-P2)
    // 最初の3点P0, P1, P2で得られるクロス積の符号を基準とする
    long long initial_sign = cross_product(points[0], points[1], points[2]);

    if (initial_sign == 0) { // 最初の3点が共線の場合、凸ではない
        std::cout <>> "No\n";
        return 0;
    }

    // P1-P2-P3
    if (cross_product(points[1], points[2], points[3]) * initial_sign <= 0) {
        std::cout <>> "No\n";
        return 0;
    }
    // P2-P3-P4
    if (cross_product(points[2], points[3], points[0]) * initial_sign <= 0) {
        std::cout <>> "No\n";
        return 0;
    }
    // P3-P4-P1
    if (cross_product(points[3], points[0], points[1]) * initial_sign <= 0) {
        std::cout <>> "No\n";
        return 0;
    }
    
    std::cout <>> "Yes\n";

    return 0;
}

D - Snuke Panic (1D)

プレイヤーは位置0から開始し、1秒につき左右に1マス移動できます。座標は0から4の範囲です。特定の時刻 \(t_i\) に特定の場所 \(x_i\) に価値 \(a_i\) のアイテムが出現します。最大でどれだけの価値を得られるかを求めます。

これは動的計画法 (DP) で解くことができます。`dp[t][x]` を時刻 `t` に位置 `x` にいる場合に、それ以降に得られる最大価値と定義します。時間軸を逆方向にたどることで、このDPを計算できます。最終的な答えは `dp[0][0]` です。

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

const int MAX_TIME = 100005; // 最大時刻
const int MAX_POS = 5;      // 最大位置 (0から4)

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_items;
    std::cin >> num_items;

    // dp[t][x]: 時刻tに位置xにいるときに、それ以降で得られる最大価値
    // 初期値は0
    std::vector<std::vector<long long>> dp(MAX_TIME, std::vector<long long>(MAX_POS, 0));

    int max_t_observed = 0; // アイテムが出現する最大時刻

    for (int i = 0; i < num_items; ++i) {
        int t, x, a;
        std::cin >> t >> x >> a;
        // アイテムは特定の時刻tに位置xに出現し、その時点で取得可能
        // dp配列には、その時刻その位置で取得できるアイテムの価値を加算する
        // 後で移動可能性を考慮して最大値を計算していく
        dp[t][x] += a;
        if (t > max_t_observed) {
            max_t_observed = t;
        }
    }

    // 最大時刻から0秒に向かってDPを計算
    for (int t = max_t_observed - 1; t >= 0; --t) {
        for (int x = 0; x < MAX_POS; ++x) {
            // 現在位置xから、次の時刻t+1で到達可能な位置からの最大価値を考慮
            long long current_max_future_value = 0;
            // 右に移動
            if (x + 1 < MAX_POS) {
                current_max_future_value = std::max(current_max_future_value, dp[t + 1][x + 1]);
            }
            // その場に留まる (位置が変わらない)
            current_max_future_value = std::max(current_max_future_value, dp[t + 1][x]);
            // 左に移動
            if (x - 1 >= 0) {
                current_max_future_value = std::max(current_max_future_value, dp[t + 1][x - 1]);
            }
            
            // 現在のアイテム価値 + 次の時刻から得られる最大価値
            dp[t][x] += current_max_future_value;
        }
    }
    
    // 0秒0位置から開始するので、dp[0][0]が答え
    std::cout <>> dp[0][0] << '\n';

    return 0;
}

E - Throwing the Die

\(N\) 回サイコロを振るゲームです。各ラウンドでサイコロを振り、出た目を得点としてゲームを終了するか、次のラウンドに進むかを選択できます。常に最適な戦略をとる場合の、\(N\) ラウンド後の期待値を求めます。

最適な戦略とは、「次のラウンドで得られる期待値よりも、現在のサイコロの目が高い場合のみゲームを終了する」というものです。したがって、DPで解くことができます。`dp[i]` を \(i\) 回サイコロを振ることができる場合の最適な期待値とします。

サイコロの目は1から6です。\(i\) 回振れる場合の `dp[i]` を計算する際、\(i-1\) 回振れる場合の期待値 `dp[i-1]` を利用します。 サイコロを振って出た目を \(j\) とします。 もし \(j \ge \text{dp}[i-1]\) ならば、現在の目 \(j\) の方がより良いため、ゲームを終了して \(j\) を得点とします。 もし \(j < \text{dp}[i-1]\) ならば、次のラウンドに進む方が良いため、ゲームを続行し、期待値は \(\text{dp}[i-1]\) となります。

これを全てのサイコロの目について合計し、6で割ることで `dp[i]` を求めます。

#include <iostream>
#include <vector>
#include <iomanip> // std::fixed, std::setprecision

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_rolls;
    std::cin >> num_rolls;

    // dp[i]: i回サイコロを振れる場合の最適な期待値
    std::vector<double> expected_value(num_rolls + 1, 0.0);

    // 1回振れる場合の期待値は (1+2+3+4+5+6)/6 = 3.5
    expected_value[1] = 3.5;

    // i=2からnum_rollsまで計算
    for (int i = 2; i <= num_rolls; ++i) {
        double sum_of_outcomes = 0.0;
        for (int die_roll = 1; die_roll <= 6; ++die_roll) {
            // サイコロの出た目 die_roll が前回の期待値より大きい場合
            // die_roll を採用
            if (static_cast<double>(die_roll) >= expected_value[i - 1]) {
                sum_of_outcomes += static_cast<double>(die_roll);
            } 
            // そうでない場合、前回の期待値を採用 (ゲーム続行)
            else {
                sum_of_outcomes += expected_value[i - 1];
            }
        }
        expected_value[i] = sum_of_outcomes / 6.0;
    }

    // N回振れる場合の期待値を出力 (小数点以下8桁まで)
    std::cout <>> std::fixed <>> std::setprecision(8) <>> expected_value[num_rolls] << '\n';

    return 0;
}

F - Well-defined Path Queries on a Namori

問題概要

\(N\) 個の頂点と \(N\) 個の辺からなる無向グラフが与えられます。\(Q\) 回のクエリで、2つの頂点 \(u_i, v_i\) 間でシンプルパス（同じ辺を2度通らない経路）がただ1つ存在するかどうかを判定します。

分析

\(N\) 個の頂点と \(N\) 個の辺を持つ連結無向グラフは、必ず「基環樹（unicyclic graph）」、つまり1つのサイクルと、そのサイクルに接続する複数の木（または独立した頂点）から構成されます。クエリで2点間のシンプルパスがただ1つであるかという問は、2点が同じ木の成分に属するかどうか、あるいはサイクルによって複数の経路が存在しないかという問題に帰着されます。

具体的には、2つの頂点 \(u, v\) が同じ「サイクルの根」（サイクル上の頂点）に属している場合のみ、パスは一意になります。これは、サイクル上のいずれかの頂点から生える木（またはパス）の中に \(u\) と \(v\) が同時に存在する場合です。もし \(u\) と \(v\) が異なるサイクルの根に属している場合、必ずサイクルを経由する2つ以上のシンプルパスが存在します。

アルゴリズム

1. グラフからサイクルを特定します。これは、次数が1の頂点（葉）をキューに入れ、その頂点とその辺を削除していくトポロジカルソートのような処理で行えます。最終的に残った頂点がサイクルを構成する頂点です。
2. サイクルを構成する各頂点を「サイクルの根」とします。
3. サイクルの根からDFS（深さ優先探索）を実行し、その根に属する木構造の全ての頂点に同じ「サイクルの根ID」を割り当てます。
4. クエリ \((u, v)\) が来た際、`root_id[u] == root_id[v]` であれば "Yes"、そうでなければ "No" と出力します。

#include <iostream>
#include <vector>
#include <queue>
#include <numeric> // for std::iota

// 各頂点が属するサイクルの根を格納
std::vector<int> cycle_root_id;
// 隣接リスト
std::vector<std::vector<int>> adj;
// 各頂点の次数
std::vector<int> degree;
int num_nodes;

// DFSでサイクルの根IDを割り当てる
void assign_roots_dfs(int u, int current_root) {
    cycle_root_id[u] = current_root;
    for (int v : adj[u]) {
        // まだサイクルの根IDが割り当てられておらず、かつサイクル上の頂点ではない場合
        // (degree[v]が1以上のままであれば、サイクルの一部か、別のツリーの根として既に処理されている可能性がある)
        // ここでは、cycle_root_idが0 (未割り当て) の頂点のみを処理
        // ただし、サイクルを構成する頂点自体は既にdegree > 1 で、拓撲ソートで除去されていない
        // cycle_root_id == 0 かつ degree[v] == 1 のようなノードは、拓撲ソートで処理済み
        // ここで再帰的に探索するのは、まだ`cycle_root_id`が設定されていないノード
        if (cycle_root_id[v] == 0) { // まだ訪問していない
            assign_roots_dfs(v, current_root);
        }
    }
}

void find_cycle_and_assign_tree_roots() {
    std::queue<int> q;

    // 次数1の頂点をキューに追加 (葉ノード)
    for (int i = 1; i <= num_nodes; ++i) {
        if (degree[i] == 1) {
            q.push(i);
        }
    }

    // トポロジカルソートのように葉を削除していく
    // cycle_root_idが-1の頂点は、サイクルに属さない葉から続くパス上の頂点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cycle_root_id[u] = -1; // サイクルに属さないノードであることをマーク

        for (int v : adj[u]) {
            degree[v]--; // 隣接頂点の次数を減らす
            if (degree[v] == 1 && cycle_root_id[v] == 0) { // 新たに葉になったらキューに追加
                q.push(v);
            }
        }
    }

    // 拓撲ソート後もcycle_root_idが0のままの頂点は、サイクル上またはその木構造の根
    // これらの頂点からDFSを開始し、サイクルの根IDを割り当てる
    for (int i = 1; i <= num_nodes; ++i) {
        if (cycle_root_id[i] == 0) { // サイクル上の頂点、またはサイクルに直接つながる頂点
            assign_roots_dfs(i, i); // 自分自身をサイクルの根IDとする
        }
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodes;

    adj.resize(num_nodes + 1);
    degree.resize(num_nodes + 1, 0);
    cycle_root_id.resize(num_nodes + 1, 0); // 0: 未処理, -1: サイクル外の葉側ノード

    for (int i = 0; i < num_nodes; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    find_cycle_and_assign_tree_roots();

    int num_queries;
    std::cin >> num_queries;
    while (num_queries--) {
        int u, v;
        std::cin >> u >> v;
        if (cycle_root_id[u] == cycle_root_id[v]) {
            std::cout >> "Yes\n";
        } else {
            std::cout >> "No\n";
        }
    }

    return 0;
}

G - Yet Another RGB Sequence

問題概要

文字 'R', 'G', 'B' をそれぞれ \(R\), \(G\), \(B\) 回使用して文字列を生成します。このとき、部分文字列 "RG" がちょうど \(K\) 回出現するような文字列が何種類作れるかを求めます。結果は \(998244353\) で割った余りを出力します。

分析

この問題は組み合わせ論とモジュロ演算を使用して解くことができます。

1. まず、'G'と'B'の文字の並べ方を考えます。これらは 'R' の配置に影響を与えないため、独立して考えることができます。`G`個の'G'と`B`個の'B'を並べる方法は、\(\binom{G+B}{G}\) 通りです。
2. 次に、部分文字列 "RG" がちょうど \(K\) 回出現するように、`R` の文字を配置します。これは、`G` のうち \(K\) 個が直後に `R` を持つように選ぶことを意味します。`G`個の'G'から\(K\)個を選ぶ方法は \(\binom{G}{K}\) 通りです。これらの\(K\)個の'G'は、それぞれ'R'とセットで"RG"ブロックを形成します。
3. 残りの \(R-K\) 個の 'R' の配置を考えます。これらの 'R' は、"RG" の数を増やさないように配置する必要があります。つまり、`RG`ブロックでない 'G' の直後には配置できません。これにより、残りの `R-K` 個の 'R' は、'B' の文字の前、または既に配置された 'R' の文字の後にしか置くことができません。 この状況は、`R-K` 個の 'R' と `B` 個の 'B' を並べ替える問題と考えることができます。これらを並べる方法は \(\binom{(R-K)+B}{R-K}\) 通りです。

したがって、最終的な答えは、上記3つのステップの組み合わせの積になります。

結果として、\(\binom{G+B}{G} \times \binom{G}{K} \times \binom{R+B}{R-K}\) となります。

組み合わせ \(\binom{n}{k}\) の計算には、階乗と逆元のモジュロ演算が必要です。\(P\) を法とする \(\binom{n}{k} = \frac{n!}{k!(n-k)!} \pmod P\) は、\(n! \times (k!)^{-1} \times ((n-k)! )^{-1} \pmod P\) として計算します。ここで \((X!)^{-1}\) は \(X!\) のモジュロ逆元です。

#include <iostream>
#include <vector>
#include <cassert> // for assert

// 法
const int MOD = 998244353;
const int MAX_N_COMB = 3000005; // R+G+Bの最大値+α

// modular arithmetic class
struct Modular {
    long long value;
    Modular(long long v = 0) : value(v % MOD) {
        if (value < 0) value += MOD;
    }
    Modular& operator+=(const Modular& other) {
        value += other.value;
        if (value >= MOD) value -= MOD;
        return *this;
    }
    Modular& operator-=(const Modular& other) {
        value -= other.value;
        if (value < 0) value += MOD;
        return *this;
    }
    Modular& operator*=(const Modular& other) {
        value = (value * other.value) % MOD;
        return *this;
    }
    Modular operator+(const Modular& other) const { return Modular(*this) += other; }
    Modular operator-(const Modular& other) const { return Modular(*this) -= other; }
    Modular operator*(const Modular& other) const { return Modular(*this) *= other; }
    
    // 逆元 (フェルマーの小定理を使用: a^(P-2) mod P)
    Modular inv() const {
        assert(value != 0);
        return power(*this, MOD - 2);
    }
    Modular& operator/=(const Modular& other) {
        return *this *= other.inv();
    }
    Modular operator/(const Modular& other) const { return Modular(*this) /= other; }

    static Modular power(Modular base, long long exp) {
        Modular res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) res *= base;
            base *= base;
            exp /= 2;
        }
        return res;
    }

    friend std::ostream& operator<<(std::ostream& os, const Modular& m) {
        return os << m.value;
    }
};

std::vector<Modular> fact(MAX_N_COMB); // 階乗
std::vector<Modular> inv_fact(MAX_N_COMB); // 階乗の逆元

// 階乗と階乗の逆元を事前計算
void precompute_factorials(int n) {
    fact[0] = 1;
    inv_fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i;
        inv_fact[i] = fact[i].inv(); // 事前計算で効率化
    }
    // inv_fact[N] = fact[N].inv(); // もしfact[N]まで計算済みなら
    // for (int i = N - 1; i >= 1; --i) {
    //     inv_fact[i] = inv_fact[i + 1] * (i + 1);
    // }
}

// 組み合わせ C(n, k) = n! / (k! * (n-k)!)
Modular combinations(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int R, G, B, K;
    std::cin >> R >> G >> B >> K;

    // 階乗の事前計算は、R+G+Bの最大値まで
    precompute_factorials(R + G + B);

    // 1. GとBの並べ方: C(G+B, G)
    Modular ways_gb = combinations(G + B, G);

    // 2. K個のGを選び、RとセットでRGブロックを作る: C(G, K)
    // K個のRGブロックと、(G-K)個のG、B個のB、(R-K)個のR
    Modular ways_k_rg = combinations(G, K);

    // 3. 残りのR-K個のRを配置: C(R+B, R-K)
    // これらのRはBの前か、他のRの前にしか置けない（Gの直後には置けない）
    // R-K個のRとB個のBを並べ替える組み合わせ
    Modular ways_remaining_r = combinations(R + B, R - K);

    Modular total_ways = ways_gb * ways_k_rg * ways_remaining_r;
    std::cout <>> total_ways << '\n';

    return 0;
}

Ex - Snuke Panic (2D)

この問題はD問題の2次元版で、座標の範囲が非常に広くなります。初期位置は(0,0)で、移動はx軸方向に1マス（左右）、y軸方向に1マス（正方向のみ）行うことができ、それぞれ1単位時間を消費します。アイテムは \((t_i, x_i, y_i, a_i)\) の形式で与えられます。

座標の範囲が非常に広いため、DPテーブルを直接定義することはできません。この種の制約がある問題は、通常、イベントソートとデータ構造（例: セグメントツリー、Fenwickツリー）を用いた動的計画法で解かれます。具体的には、時間軸でイベントをソートし、特定の時間で到達可能な範囲の最大値を効率的に更新・取得する手法が考えられます。

詳細な実装については、高度なアルゴリズムとデータ構造の理解が必要となるため、ここでは割愛します。