A. 버스 문제 (3)

주어진 s_i, t_i 값들의 최소와 최대를 각각 L, R로 정의합니다. p < min(s_i)인 경우, 우리는 항상 R까지 이동하게 됩니다. 이후에는 s_i > t_i인 구간만 남게 됩니다.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 5;
int n, q, m, mn, mx;
long long w[MAXN], f[MAXN], d[MAXN], a[MAXN], b[MAXN], p[MAXN], z[MAXN];

void solve() {
    iota(d + 1, d + m + 1, 1);
    for (int i = 1; i <= n; ++i) d[a[i]] = min(d[a[i]], b[i]);
    long long s = 0, h = m;
    for (int i = m; i >= 1; --i) {
        s = min(s, max(0LL, mx - w[h]));
        f[i] = s;
        h = min(h, d[i]);
        if (h < i) s += 2 * (w[i] - w[i - 1]);
    }
    for (int i = 1; i <= q; ++i) {
        z[i] = min(z[i], f[p[i]] + mx - mn + abs(w[p[i]] - mn));
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> mn;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        w[++m] = a[i], w[++m] = b[i];
        mx = max({mx, a[i], b[i]});
        mn = min({mn, a[i], b[i]});
    }
    for (int i = 1; i <= q; ++i) cin >> p[i], w[++m] = p[i], z[i] = 3 * mn;
    sort(w + 1, w + m + 1);
    m = unique(w + 1, w + m + 1) - w - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(w + 1, w + m + 1, a[i]) - w, b[i] = lower_bound(w + 1, w + m + 1, b[i]) - w;
    for (int i = 1; i <= q; ++i) p[i] = lower_bound(w + 1, w + m + 1, p[i]) - w;
    solve();
    reverse(w + 1, w + m + 1);
    mn = mn + 1 - mn;
    mx = mn + 1 - mx;
    swap(mn, mx);
    for (int i = 1; i <= m; ++i) w[i] = mn + 1 - w[i];
    for (int i = 1; i <= n; ++i) a[i] = m + 1 - a[i], b[i] = m + 1 - b[i];
    for (int i = 1; i <= q; ++i) p[i] = m + 1 - p[i];
    solve();
    for (int i = 1; i <= q; ++i) cout << z[i] << " \n"[i == q];
    return 0;
}

B. 토끼 미로 (2.5)

DAG 상에서 p_u, f_u, g_u, F_u, G_u를 각각 정의하여 간선을 통해 전달되는 확률과 기댓값을 계산합니다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

long long ksm(long long a, long long b = MOD - 2) {
    long long s = 1;
    for (; b; a = a * a % MOD, b >>= 1) if (b & 1) s = s * a % MOD;
    return s;
}

vector<int> G[105][2];
int n, m, S, T, p[105], f1[105], f2[105], g1[105], g2[105];
long long a[505][505];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> S >> T;
    for (int i = 1, u, v, w; i <= m; ++i) {
        cin >> u >> v >> w;
        G[u][w].push_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        f1[i] = i;
        f2[i] = i;
        g1[i] = i;
        g2[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        if (i == T) {
            a[p[i]][p[i]] = a[p[i]][n + 1] = 1;
            continue;
        }
        int d = G[i][0].size() + G[i][1].size();
        a[p[i]][p[i]] = -d;
        for (int x : G[i][1]) {
            ++a[p[i]][p[x]];
            ++a[f1[i]][f1[x]];
            ++a[f2[i]][f2[x]];
            ++a[g1[i]][g1[x]];
            ++a[g2[i]][g2[x]];
        }
        for (int x : G[i][0]) {
            ++a[f2[i]][f2[x]];
            ++a[g2[i]][g2[x]];
        }
    }
    for (int i = 1; i <= n * 2; ++i) for (int j = 1; j <= n * 2 + 1; ++j) a[i][j] = (a[i][j] + MOD) % MOD;
    for (int i = 1; i <= n * 2; ++i) {
        for (int j = i; j <= n * 2; ++j) if (a[j][i]) { swap(a[i], a[j]); break; }
        long long z = ksm(a[i][i]);
        for (int j = i; j <= n * 2 + 1; ++j) a[i][j] = a[i][j] * z % MOD;
        for (int j = 1; j <= n * 2; ++j) if (i != j) {
            z = MOD - a[j][i];
            for (int k = i; k <= n * 2 + 1; ++k) a[j][k] = (a[j][k] + a[i][k] * z) % MOD;
        }
    }
    long long x = (a[f1[S]][n * 2 + 1] + a[f2[S]][n * 2 + 1]) % MOD;
    long long y = (a[g1[S]][n * 2 + 1] + a[g2[S]][n * 2 + 1]) % MOD;
    cout << x << " " << (y + (MOD - x) * x) % MOD << "\n";
    return 0;
}