A - Yay!

長さが3以上の文字列中に2種類の文字が含まれており、そのうち1つはちょうど1回だけ出現する。その位置を1-indexedで出力せよ。

最初の文字が一意であれば、残りにその文字は存在しない。そうでなければ、最初の文字とは異なる最初の文字を探せばよい。

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

int main() {
    string s;
    cin >> s;
    if (s.find(s[0], 1) == string::npos)
        cout << 1 << '\n';
    else
        cout << s.find_first_not_of(s[0]) + 1 << '\n';
}

B - Which is ahead?

N人の順列が与えられ、Q個のクエリで2人のIDが与えられる。順列上で前にいる方のIDを答えよ。

各IDのインデックスを配列に記録しておき、比較するだけ。

#include <iostream>
using namespace std;

int pos[101];

int main() {
    int N, Q;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int p;
        cin >> p;
        pos[p] = i;
    }
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        cout << (pos[a] < pos[b] ? a : b) << '\n';
    }
}

C - Many Replacement

初期文字列Sに対して、Q回「文字cをdに置換」する操作を行う。最終的な文字列を出力せよ。

各文字が最終的にどの文字に変換されるかをマッピングで管理。初期はa→a, b→b,…。各クエリで、現在cにマップされているすべての文字をdに更新する。

#include <iostream>
#include <map>
using namespace std;

int main() {
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    map<char, char> mp;
    for (char c = 'a'; c <= 'z'; ++c) mp[c] = c;
    while (Q--) {
        char c, d;
        cin >> c >> d;
        for (char x = 'a'; x <= 'z'; ++x)
            if (mp[x] == c) mp[x] = d;
    }
    for (char c : S) cout << mp[c];
    cout << '\n';
}

D - Square Pair

非負整数列Aが与えられる。i < j かつ A[i] * A[j] が完全平方数となるペアの個数を求めよ。

各数を「平方因子を取り除いた形」に正規化（例：108 → 3）。0は特別扱い。0は他の任意の数とペアになり得るが、0同士は重複カウントに注意。

#include <iostream>
#include <map>
using namespace std;

long long normalize(long long x) {
    if (x == 0) return 0;
    long long res = 1;
    for (long long p = 2; p * p <= x; ++p) {
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        if (cnt % 2) res *= p;
    }
    if (x > 1) res *= x;
    return res;
}

int main() {
    int N;
    cin >> N;
    map<long long, long long> freq;
    long long zero_cnt = 0, ans = 0;
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        if (a == 0) {
            zero_cnt++;
        } else {
            long long key = normalize(a);
            ans += freq[key];
            freq[key]++;
        }
    }
    ans += zero_cnt * (N - zero_cnt) + zero_cnt * (zero_cnt - 1) / 2;
    cout << ans << '\n';
}

E - Last Train

N駅間を結ぶM本の列車がある。各列車は定期的に運行され、所定の時刻に発車・到着する。各駅から駅Nへ到達可能な場合の最遅出発時刻を求めよ。

終点Nから逆向きにダイクストラ法を適用。各辺について、現在の到着時刻から逆算して利用可能な最遅の便を計算し、発車時刻を更新する。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge {
    int to;
    ll l, d, k, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<vector<Edge>> g(N);
    for (int i = 0; i < M; ++i) {
        ll l, d, k, c, a, b;
        cin >> l >> d >> k >> c >> a >> b;
        g[b - 1].push_back({a - 1, l, d, k, c});
    }

    vector<ll> dist(N, -1);
    priority_queue<pair<ll, int>> pq;
    dist[N - 1] = INF;
    pq.emplace(INF, N - 1);

    while (!pq.empty()) {
        auto [t, u] = pq.top(); pq.pop();
        if (t != dist[u]) continue;
        for (auto& e : g[u]) {
            if (dist[u] <= e.c) continue;
            ll latest = dist[u] - e.c;
            if (latest < e.l) continue;
            ll trips = min(e.k, (latest - e.l) / e.d + 1);
            if (trips <= 0) continue;
            ll depart = e.l + (trips - 1) * e.d;
            if (depart > dist[e.to]) {
                dist[e.to] = depart;
                pq.emplace(depart, e.to);
            }
        }
    }

    for (int i = 0; i < N - 1; ++i) {
        if (dist[i] == -1)
            cout << "Unreachable\n";
        else
            cout << dist[i] << '\n';
    }
}

F - Black Jack

D面サイコロを使ったゲームで、プレイヤーとディーラーが順にサイコロを振る。プレイヤーは任意のタイミングで止められ、ディーラーは合計がL以上になるまで振り続ける。プレイヤーが勝つ最大確率を求めよ。

動的計画法で後ろから計算。dp[i]は現在のスコアがiのときの最大勝率。停止時の勝率は事前計算したディーラーの敗北確率g[i]で、継続時の勝率はdp[i+1]〜dp[i+D]の平均。精度を保つため、区間和はセグメント木で管理。

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

struct SegTree {
    vector<double> tree;
    int n;
    SegTree(int size) {
        n = 1;
        while (n < size) n *= 2;
        tree.assign(2 * n, 0.0);
    }
    void update(int idx, double val) {
        idx += n;
        tree[idx] = val;
        for (idx /= 2; idx > 0; idx /= 2)
            tree[idx] = tree[2*idx] + tree[2*idx+1];
    }
    double query(int l, int r) {
        l += n; r += n;
        double res = 0.0;
        while (l <= r) {
            if (l % 2 == 1) res += tree[l++];
            if (r % 2 == 0) res += tree[r--];
            l /= 2; r /= 2;
        }
        return res;
    }
};

int main() {
    int N, L, D;
    cin >> N >> L >> D;
    SegTree st_f(max(N + D, L) + 5);
    st_f.update(0, 1.0);

    for (int i = 1; i <= N; ++i) {
        int l = max(0, i - D);
        int r = min(i - 1, L - 1);
        double prob = st_f.query(l, r) / D;
        st_f.update(i, prob);
    }

    double lose_prob = 0.0;
    for (int i = N + 1; i < L + D; ++i) {
        int l = max(0, i - D);
        int r = L - 1;
        lose_prob += st_f.query(l, r) / D;
    }

    vector<double> g(N + 2, 0.0);
    g[0] = lose_prob;
    for (int i = 1; i <= N; ++i) {
        g[i] = g[i-1];
        if (i < L) g[i] += st_f.query(i, i);
    }

    SegTree st_dp(N + D + 5);
    for (int i = N; i >= 0; --i) {
        double stop_win = g[i];
        int l = i + 1, r = min(i + D, N);
        double roll_win = (l <= r) ? st_dp.query(l, r) / D : 0.0;
        double best = max(stop_win, roll_win);
        st_dp.update(i, best);
    }
    printf("%.15f\n", st_dp.query(0, 0));
}

G - Retroactive Range Chmax

配列に対するchmaxクエリ（区間の各要素をxとmax）と、過去のクエリの取り消し、および要素参照クエリを処理せよ。

セグメント木の各ノードにmapを持たせ、キーはchmaxの値、バリューは適用回数。クエリ時はパス上の最大キーを返す。取り消し時は該当キーのカウントを減らし、0になれば削除。

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

struct Node {
    map<int, int> vals;
};

class SegTree {
public:
    vector<Node> tree;
    int n;
    SegTree(vector<int>& arr) {
        n = arr.size() - 1;
        tree.resize(4 * n);
        build(1, 1, n, arr);
    }
    void build(int v, int l, int r, vector<int>& arr) {
        if (l == r) {
            tree[v].vals[arr[l]] = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(2*v, l, mid, arr);
        build(2*v+1, mid+1, r, arr);
    }
    void apply(int v, int l, int r, int ql, int qr, int x, bool add) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            if (add) tree[v].vals[x]++;
            else {
                if (--tree[v].vals[x] == 0)
                    tree[v].vals.erase(x);
            }
            return;
        }
        int mid = (l + r) / 2;
        apply(2*v, l, mid, ql, qr, x, add);
        apply(2*v+1, mid+1, r, ql, qr, x, add);
    }
    int query(int v, int l, int r, int idx) {
        int res = tree[v].vals.empty() ? 0 : tree[v].vals.rbegin()->first;
        if (l == r) return res;
        int mid = (l + r) / 2;
        if (idx <= mid)
            res = max(res, query(2*v, l, mid, idx));
        else
            res = max(res, query(2*v+1, mid+1, r, idx));
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    SegTree st(A);
    int Q;
    cin >> Q;
    vector<tuple<int, int, int, int>> ops(Q + 1);
    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            ops[i] = {t, l, r, x};
            st.apply(1, 1, N, l, r, x, true);
        } else if (t == 2) {
            int j;
            cin >> j;
            auto [_, l, r, x] = ops[j];
            st.apply(1, 1, N, l, r, x, false);
        } else {
            int idx;
            cin >> idx;
            cout << st.query(1, 1, N, idx) << '\n';
        }
    }
}