2024 YCPC 解 by SorahISA

• Contest Link
• Scoreboard

Problem A. Trip Counting I Medium

Problem Setter: hank55663

補圖上數

$C_3$。

原圖上三個點如果有

$k$ 條邊

$⟹$ 補圖上有

$3-k$ 條邊。

• 有
  $A_0=(\genfrac{}{}{0ex}{}{n}{3})$ 個點 tuple 至少有
  $0$ 條邊（任三點）；
• 有
  $A_1=m\cdot (n-2)$ 個點 tuple 至少有
  $1$ 條邊（每條邊都往外找任意一個點）；
• 有
  $A_2=\sum _{i=1}^n(\genfrac{}{}{0ex}{}{\text{deg}(i)}{2})$ 個點 tuple 至少有
  $2$ 條邊；
• 有
  $A_3=\mathrm{\#}{C}_3$ 個點 tuple 是
  $C_3$。

答案就是

$3!\cdot (A_0-3A_1+3A_2-A_3)$。

https://github.com/OmeletWithoutEgg/ckiseki/blob/master/codes/Graph/CountCycles.cpp

TC：

$\mathcal{O}(m\log m)$。

Problem B. Trip Counting II Hard

Problem Setter: hank55663

數

$C_4$。

https://github.com/OmeletWithoutEgg/ckiseki/blob/master/codes/Graph/CountCycles.cpp

TC：

$\mathcal{O}(m\log m)$。

Problem C. Trip Counting III Easy Medium

Problem Setter: hank55663

數

$C_5$。

注意

$n$ 跟

$m$ 很小，亂做就好。看起來大家都沒有通過閱讀測驗。

我的做法是枚舉三條相鄰邊

$(a,b),(b,c),(c,d)$ 然後計算

$a$ 跟

$d$ 共同鄰居扣掉

$b$ 跟

$c$ 的數量。

TC：

$\mathcal{O}(m^3)$。

Code

void solve() {
    int N, M; cin >> N >> M;

    vector<pii> edges(M);
    vector<bitset<maxn>> adj_mat(N+1);
    for (auto &[u, v] : edges) {
        cin >> u >> v;
        adj_mat[u][v] = adj_mat[v][u] = 1;
    }

    vector cap(N+1, vector<int>(N+1, 0));
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) cap[i][j] = (adj_mat[i] & adj_mat[j]).count();

    ll ans = 0;
    for (int i = 0; i < M; ++i) for (int j = 0; j < M; ++j) for (int k = 0; k < M; ++k) {
        if (i == j or i == k or j == k) continue;
        auto [i1, i2] = edges[i];
        auto [j1, j2] = edges[j];
        auto [k1, k2] = edges[k];
        if (i1 == j1) swap(i1, i2);
        if (i2 == j2) swap(j1, j2);
        if (i1 == j2) swap(i1, i2), swap(j1, j2);
        if (j1 == k1) swap(j1, j2);
        if (j2 == k2) swap(k1, k2);
        if (i2 == j1 and j2 == k1 and i1 != k2) {
            ans += cap[i1][k2] - adj_mat[i2][k2] - adj_mat[i1][k1];
        }
    }
    cout << ans << "\n";
}

Problem D. Rearrangement Easy

Problem Setter: henotrix

經典 greedy 題，每個 column 由小排到大就是最佳解。

證明可以用 exchange argument 證。

Code

void solve() {
    int N, M; cin >> N >> M;

    vector arr(M, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) cin >> arr[j][i];
    }
    for (int j = 0; j < M; ++j) sort(ALL(arr[j]));

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j+1 < M; ++j) {
            ans += abs(arr[j][i] - arr[j+1][i]);
        }
    }
    cout << ans << "\n";
}

Problem E. Elimination Game Easy

Problem Setter: henotrix

觀察一下應該就能發現只要不是

$a=0$ 或

$b=0$ 就能讓任何數字留下來。

$a=0$ 就只可能留最大的，vice versa。

Code

void solve() {
    int N, A, B, X; cin >> N >> A >> B >> X;

    if (A == N-1 and X != 1) cout << "No" << "\n";
    else if (B == N-1 and X != N) cout << "No" << "\n";
    else cout << "Yes" << "\n";
}

Problem F. Destroying Monsters Easy Medium

Problem Setter: henotrix

經典 greedy，把 gun 依照左界排序。

Code

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> X(n);
    for (auto &x: X) cin >> x;
    vector<pair<int,int>> G(m);
    for (auto &[l,r]: G) cin >> l >> r;
    sort(ALL(X));
    sort(ALL(G), [&](auto a, auto b) {
        return a.first < b.first;
    });
    bool can = true;
    int ans = 0;
    for (int i = 0, j = 0; i < n; ) {
        int mx = -1;
        while (j < m and G[j].first <= X[i]) {
            mx = max(mx, G[j].second);
            j++;
        }
        if (mx < X[i]) {
            can = false;
            break;
        }
        ans++;
        while (i < n and X[i] <= mx)
            i++;
    }
    if (not can) ans = -1;
    cout << ans << endl;
}

Problem G. Graph Coloring Problem Easy Medium

Problem Setter: henotrix

看限制可以大概感覺的出來要把邊由小到大加進去離線回答詢問。

只要一個 DSU 來維護最大連通塊大小就好了。

Code

struct Qry {
    int id, k, ans;
};

struct Edge {
    int u, v, w;
};

struct DSU {
    vector<int> ary;
    int mx = 1;
    DSU(int n): ary(n, -1) {}
    int find(int x) { return ary[x] < 0 ? x : ary[x] = find(ary[x]); }
    bool merge(int u, int v) {
        debug(u, v);
        u = find(u), v = find(v);
        if (u == v) return false;
        if (-ary[u] < -ary[v]) swap(u, v);
        ary[u] += ary[v];
        mx = max(mx,  -ary[u]);
        debug(mx);
        ary[v] = u;
        return true;
    }
    int mxsz() {
        return mx;
    }
};

signed main() {
    fast;

    int n, m, Q;
    cin >> n >> m >> Q;
    vector<Edge> edges(m);
    for (auto &[u,v,w]: edges) {
        cin >> u >> v >> w;
        u--; v--;
    }

    vector<Qry> qry(Q);
    for (int q = 0; q < Q; q++) {
        qry[q].id = q;
        cin >> qry[q].k;
    }

    sort(ALL(qry), [&](auto& x, auto& y) {
        return x.k < y.k;
    });

    sort(ALL(edges), [&](auto& x, auto& y) {
        return x.w < y.w;
    });

    DSU dsu(n);
    for (int q = 0, e = 0; q < Q; q++) {
        while (e < m and edges[e].w <= qry[q].k) {
            dsu.merge(edges[e].u, edges[e].v);
            e++;
        }
        debug(qry[q].id, dsu.mxsz());
        qry[q].ans = dsu.mxsz();
    }

    sort(ALL(qry), [&](auto& x, auto& y) {
        return x.id < y.id;
    });

    for (auto q: qry)
        cout << q.ans << '\n';

    return 0;
}

Problem H. Points Separation Medium

Problem Setter: henotrix

找

$(q{x}_i,q{y}_i)$ 跟凸包最短距離，然後答案就是中垂線。

最短距離要嘛是戳在一條邊上，要嘛是戳在一個點上。

範圍很小，

$\mathcal{O}(nq)$ 都可以過，你知道怎麼算點到直線距離（或是你有模板又沒有抄爛）的話應該就能 AC 了。

Problem I. LIS Decrement Medium

Problem Setter: henotrix

經典最小割題。

Code

/// 此處省略 Dinic 模板

signed main() {
    int n, ans = 0;
    cin >> n;
    
    vector<int> arr(n+2), dp(n+2), weight(n+2);
    for(int i=1;i<=n;i++)
        cin >> arr[i];
    arr[0] = 0, arr[n+1] = n+1;
    for(int i=1;i<=n;i++)
        cin >> weight[i], ans += weight[i];
    weight[0] = weight[n+1] = 2e9;
    arr[n+1] = n+1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<i;j++)
            if(arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j]+1);

    Dinic dinic;
    dinic.init(2*(n+2));

    for(int i=0;i<=n+1;i++)
        dinic.add_edge(2*i, 2*i+1, weight[i]);

    for(int i=0;i<=n+1;i++)
        for(int j=0;j<i;j++)
            if(dp[i] == dp[j]+1 and arr[j] < arr[i])
                dinic.add_edge(2*j+1, 2*i, 2e9);

    auto rrr = ans-dinic.max_flow(0, (n+1)*2+1);

    cout << rrr <<'\n';

    return 0;
}

Problem J. Randomized String Matching Algorithm Medium Hard

Problem Setter: henotrix

把式子推一推就會發現你要處理每個位移的匹配位置數量，這是經典卷積題。

對每個字元分開做，把

$S$ 跟

$T$ 都當成一個只有

$0$ 跟

$1$ 的陣列，然後做

$S\ast \text{reverse}(T)$ 就好。

https://tioj.ck.tp.edu.tw/problems/1035

Code

/// 此處省略 NTT 模板（快速數論變換）
/// fpow(base, exp = MOD-2) 是快速冪 base^exp mod MOD

void solve() {
    string S, T; cin >> S >> T;
    int K; cin >> K;
    int N = ssize(S), M = ssize(T);
    int N_pow2 = (2 << __lg(N+1));

    vector<int> match(N-M+1, 0);
    for (char c = 'a'; c <= 'h'; ++c) {
        vector<int> a(N_pow2, 0), b(N_pow2, 0);
        for (int i = 0; i < N; ++i) a[i] = (S[i] == c);
        for (int i = 0; i < M; ++i) b[i] = (T[M-i-1] == c);

        NTT ntt;
        ntt(a, N_pow2, false);
        ntt(b, N_pow2, false);
        for (int i = 0; i < N_pow2; ++i) a[i] = (a[i] * b[i]) % MOD;
        ntt(a, N_pow2, true);

        for (int j = M-1; j <= N-1; ++j) match[j-(M-1)] += a[j];
    }

    int ans = 1;
    for (int i = 0; i <= N-M; ++i) {
        if (match[i] == M) continue;
        ans = ans * (1 - fpow(match[i], K) * fpow(fpow(M, K)) % MOD + MOD) % MOD;
    }
    cout << ans << "\n";
}

Problem K. King's Challenge Hard

Problem Setter: truckski

要算

$n!/(n-k)!$ 去掉結尾

$0$ 的末五位數。

先嘗試將答案表示為

$2^a\cdot 5^b\cdot c$ 的形式。

定義

$f_d(x)$ 代表

$d^{f_d(x)}\mid x!$ 但

$d^{f_d(x)+1}\nmid x!$。這可以在

$\mathcal{O}({\log }_{d}x)$ 時間求出。

可得

$a=f_2(n)-f_2(n-k)$ 以及

$b=f_5(n)-f_5(n-k)$。

注意到

${\left(\prod _{\begin{array}{c}1\le x\le p-1\\ x\mathrm{\perp }p\end{array}}x\right)}^{2}modp=1$，因為每個數字可以跟他的 inverse 對上。這就代表說對任意

$x\in \mathbb{N}$，

$[x,x+2\cdot {10}^5)$ 跟

${10}^5$ 互質的整數乘起來

$mod100000$ 都是

$1$。

要計算

$c$ 就可以透過預處理

$[1,2\cdot {10}^5]$ 前綴跟

${10}^5$ 互質整數乘積來

$\mathcal{O}(1)$ 求得。

Problem L. The Bag of Forgotten Coins Easy

Problem Setter: truckski

不能取相鄰數字的最大和，經典 DP。

用

$\text{dp}[i][0/1]$ 代表要不要取最後一個的總和最大值。

Code

void solve() {
    ll N; cin >> N;

    vector<ll> v(N);
    for (ll &x : v) cin >> x, x = max<ll>(x, 0);

    vector<ll> dp = v;
    for (int i = 1; i < N; ++i) {
        dp[i] = max(dp[i-1], (i >= 2 ? dp[i-2] : 0) + v[i]);
    }
    cout << *max_element(ALL(dp)) << "\n";
}

Problem M. The Tale of Professor Alya and the H-Index Water

Problem Setter: truckski

int H = 0;
for (int i = 1; i <= n; ++i) {
    if (c[i] >= i) ++H;
}