A - Happy New Year 2025

2つの整数 $A$ と $B$ が与えられます。$(A + B)^2$ を出力するだけの問題です。計算結果が整数型の範囲に収まるか注意が必要ですが、今回の制約では問題ありません。

#include <iostream>

using namespace std;

void solve() {
    long long val1, val2;
    if (cin >> val1 >> val2) {
        long long combined = val1 + val2;
        cout << combined * combined << endl;
    }
}

int main() {
    solve();
    return 0;
}

B - 9x9 Sum

9×9の九九の表において、積が $P$ に等しくない要素の総和を求めます。全体の和は $\sum_{i=1}^9 \sum_{j=1}^9 i \times j = 45 \times 45 = 2025$ です。ここから $i \times j = P$ となる要素を引き算することで答えが得られます。

#include <iostream>

using namespace std;

int main() {
    int target_val;
    cin >> target_val;

    int total_sum = 0;
    for (int row = 1; row <= 9; ++row) {
        for (int col = 1; col <= 9; ++col) {
            int product = row * col;
            if (product != target_val) {
                total_sum += product;
            }
        }
    }
    cout << total_sum << endl;
    return 0;
}

C - Snake Numbers

「先頭の桁が他のすべての桁よりも厳密に大きい数」を「蛇数」と定義します。範囲 $[L, R]$ に含まれる蛇数の個数を求めます。$f(X)$ を $1$ から $X$ までの蛇数の個数とすると、答えは $f(R) - f(L-1)$ で求められます。

桁DP、あるいは桁数ごとの組み合わせ計算で解くことができます。累乗計算の精度に注意し、独自のべき乗関数を実装するのが安全です。

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

using namespace std;

typedef long long ll;

ll power_func(ll base, ll exp) {
    ll result = 1;
    for (int i = 0; i < exp; ++i) result *= base;
    return result;
}

ll count_snake_numbers(ll limit) {
    if (limit < 10) return 0;
    string s_num = to_string(limit);
    int len = s_num.length();
    ll count = 0;

    // 桁数がlimit未満の蛇数をカウント
    for (int d = 2; d < len; ++d) {
        for (int first = 1; first <= 9; ++first) {
            count += power_func(first, d - 1);
        }
    }

    // 桁数が同じで、先頭の数字がlimitより小さいものをカウント
    int first_digit = s_num[0] - '0';
    for (int f = 1; f < first_digit; ++f) {
        count += power_func(f, len - 1);
    }

    // 先頭の数字がlimitと同じものを順にチェック
    for (int i = 1; i < len; ++i) {
        int current_digit = s_num[i] - '0';
        int possible_choices = min(current_digit, first_digit);
        count += (ll)possible_choices * power_func(first_digit, len - i - 1);
        
        if (current_digit >= first_digit) return count;
    }

    return count + 1;
}

int main() {
    ll l, r;
    cin >> l >> r;
    cout << count_snake_numbers(r) - count_snake_numbers(l - 1) << endl;
    return 0;
}

D - Snaky Walk

グリッド上での最短経路を求めますが、「前回が垂直移動なら今回は水平移動」「前回が水平移動なら今回は垂直移動」という制約があります。BFSの際、各マスの状態を $(x, y, \text{直前の方向})$ のように持つことで解決できます。

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

using namespace std;

struct State {
    int r, c, dist;
    bool last_horizontal;
};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    int sr, sc, gr, gc;
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
        for (int j = 0; j < W; ++j) {
            if (grid[i][j] == 'S') { sr = i; sc = j; }
            if (grid[i][j] == 'G') { gr = i; gc = j; }
        }
    }

    auto bfs = [&](bool start_h) {
        queue<State> q;
        q.push({sr, sc, 0, start_h});
        vector<vector<vector<bool>>> visited(H, vector<vector<bool>>(W, vector<bool>(2, false)));
        visited[sr][sc][start_h] = true;

        while (!q.empty()) {
            State cur = q.front(); q.pop();
            if (cur.r == gr && cur.c == gc) return cur.dist;

            bool next_h = !cur.last_horizontal;
            int dr[] = {0, 0, 1, -1};
            int dc[] = {1, -1, 0, 0};

            for (int i = 0; i < 4; ++i) {
                if (next_h && dr[i] != 0) continue;
                if (!next_h && dc[i] != 0) continue;

                int nr = cur.r + dr[i], nc = cur.c + dc[i];
                if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc] != '#' && !visited[nr][nc][next_h]) {
                    visited[nr][nc][next_h] = true;
                    q.push({nr, nc, cur.dist + 1, next_h});
                }
            }
        }
        return (int)2e9;
    };

    int res = min(bfs(true), bfs(false));
    cout << (res >= 2e9 ? -1 : res) << endl;
    return 0;
}

E - Digit Sum Divisible 2

与えられた巨大な $n$ に対して、数位和で割り切れる隣接する2つの整数 $(a, a+1)$ を構築する問題です。 小さな $n$ については全探索を行い、大きな $n$ については特定のパターン（下位桁を0で埋めるなど）を用いて条件を満たす $a$ を構成します。

#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

int digit_sum(ll n) {
    int s = 0;
    while (n > 0) { s += n % 10; n /= 10; }
    return s;
}

void solve() {
    string n_str;
    cin >> n_str;

    if (n_str.length() <= 6) {
        ll n_val = stoll(n_str);
        for (ll i = n_val; i < 2 * n_val; ++i) {
            if (i % digit_sum(i) == 0 && (i + 1) % digit_sum(i + 1) == 0) {
                cout << i << endl;
                return;
            }
        }
        cout << -1 << endl;
        return;
    }

    // 構築アルゴリズムの例（1700...を用いた構成）
    if (n_str[0] == '9') {
        cout << "17";
        for (int i = 0; i < n_str.length() - 1; ++i) cout << '0';
    } else {
        int first = n_str[0] - '0';
        cout << first + 1 << 8 - (first + 1);
        for (int i = 0; i < n_str.length() - 2; ++i) cout << '0';
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

F - Count Arrays

条件 $x_i \le x_{A_i}$ を満たす数列の個数を数えます。各 $i \to A_i$ に辺を張ったグラフを考えます。これは各頂点の出次数が1の機能グラフになります。 強連結成分（SCC）内では、すべての $x_i$ が同じ値である必要があります。SCCを1つの頂点に縮約し、得られたDAG（実質的には反転した木構造の集まり）上でDPを行います。

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

using namespace std;

const int MOD = 998244353;

int N, M;
vector<int> adj[2005], dag_adj[2005];
int dfn[2005], low[2005], scc_id[2005], timer, scc_cnt;
bool in_stack[2005];
stack<int> st;
long long dp[2005][2005];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    in_stack[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int v = st.top(); st.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            if (u == v) break;
        }
    }
}

void dfs_dp(int u) {
    for (int v : dag_adj[u]) dfs_dp(v);
    for (int j = 1; j <= M; ++j) {
        long long ways = 1;
        for (int v : dag_adj[u]) {
            ways = (ways * dp[v][j]) % MOD;
        }
        dp[u][j] = (dp[u][j - 1] + ways) % MOD;
    }
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        int a; cin >> a;
        if (a != i) adj[a].push_back(i);
    }
    for (int i = 1; i <= N; ++i) if (!dfn[i]) tarjan(i);
    vector<int> in_degree(scc_cnt + 1, 0);
    for (int u = 1; u <= N; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                dag_adj[scc_id[u]].push_back(scc_id[v]);
                in_degree[scc_id[v]]++;
            }
        }
    }
    long long ans = 1;
    for (int i = 1; i <= scc_cnt; ++i) {
        if (in_degree[i] == 0) {
            dfs_dp(i);
            ans = (ans * dp[i][M]) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}