問題リンク: https://codeforces.com/contest/2125

A. Difficult Contest

解法

「NTT」と「FFT」はどちらも部分列として T が後ろに来る必要がある。したがって、まず F と N 以外の文字をすべて出力し、その後で F と N を出力すればよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;

        string ans;
        for (char c : s) {
            if (c != 'F' && c != 'N') ans += c;
        }
        for (char c : s) {
            if (c == 'F' || c == 'N') ans += c;
        }
        cout << ans << '\n';
    }
    return 0;
}

B. Left and Down

解法

a と b の既約比を考える。その分子と分母がともに k 以下なら 1 回の操作で済む。そうでなければ (1,0) と (0,1) を選べばよく、最大コストは 2 である。

メモ: 最初から long long を使い、必要に応じて int に変更するか考えるのは良い習慣である。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long a, b, k;
        cin >> a >> b >> k;

        if (a == b) {
            cout << 1 << '\n';
            continue;
        }

        long long g = gcd(a, b);
        if (a / g <= k && b / g <= k) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
    }
    return 0;
}

C. Count Good Numbers

解法

明らかに 1 桁の素数は 2, 3, 5, 7 だけである。したがって、これらの部分集合を列挙して包除原理を使えばよい。

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 count_not_divisible(int64 x) {
    vector<int> primes = {2, 3, 5, 7};
    int64 res = 0;
    for (int mask = 0; mask < (1 << 4); ++mask) {
        int64 prod = 1;
        int bits = 0;
        for (int i = 0; i < 4; ++i) {
            if (mask & (1 << i)) {
                ++bits;
                prod *= primes[i];
            }
        }
        if (bits % 2 == 0) {
            res += x / prod;
        } else {
            res -= x / prod;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int64 l, r;
        cin >> l >> r;
        cout << count_not_divisible(r) - count_not_divisible(l - 1) << '\n';
    }
    return 0;
}

D. Segments Covering

解法

線形 DP と累積積を使う。各セグメントを右端 r の vector に格納し、l, p, q の 3 つの情報を持たせる。次に (1 - p/q) の mod 上での累積積を計算する。左から右へ走査し、点 i の vector が空でなければ、確率 gl を先に計算し、dp[i] += dp[l-1] * pre[i] * inv(pre[l-1]) * inv(1-gl) * gl とする（各セグメントで覆われ、その区間内に他のセグメントが現れないと仮定）。mod の扱いに注意する。

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int64 MOD = 998244353;

int64 mod_pow(int64 base, int64 exp) {
    int64 res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

int64 mod_inv(int64 x) {
    return mod_pow(x, MOD - 2);
}

struct Segment {
    int l;
    int64 p, q;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<Segment>> byRight(m + 2);
    for (int i = 0; i < n; ++i) {
        int l, r;
        int64 p, q;
        cin >> l >> r >> p >> q;
        byRight[r].push_back({l, p, q});
    }

    vector<int64> pref(m + 2, 0);
    pref[0] = 1;
    for (int i = 1; i <= m; ++i) {
        pref[i] = pref[i - 1];
        for (const auto& seg : byRight[i]) {
            int64 prob = seg.p * mod_inv(seg.q) % MOD;
            pref[i] = pref[i] * ((1 - prob + MOD) % MOD) % MOD;
        }
    }

    vector<int64> dp(m + 2, 0);
    dp[0] = 1;
    for (int i = 1; i <= m; ++i) {
        for (const auto& seg : byRight[i]) {
            int64 prob = seg.p * mod_inv(seg.q) % MOD;
            int64 ratio = pref[i] * mod_inv(pref[seg.l - 1]) % MOD;
            int64 noOther = ratio * mod_inv((1 - prob + MOD) % MOD) % MOD;
            dp[i] = (dp[i] + dp[seg.l - 1] * noOther % MOD * prob) % MOD;
        }
    }

    cout << dp[m] << '\n';
    return 0;
}