F. Challenge NPC III

多起点最短経路と第二最短経路問題。

同じ色の頂点に対してBFSを実行し、各経路の起点を維持します。同じ色の頂点から自身への経路が最短であるため、最終的に第二最短経路がkより小さいかを判定すれば十分です。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> color(50);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        color[--x].push_back(i);
    }

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
    }

    const int inf = 1 << 30;

    for (int i = 0; i < 50; i++) {
        if (color[i].size() <= 1) continue;
        
        vector<vector<int>> dist(n, {inf, inf});
        vector<vector<int>> prev(n, {-1, -1});
        
        queue<int> q;
        for (int u : color[i]) {
            dist[u] = {0, inf};
            prev[u] = {u, -1};
            q.push(u);
        }
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : graph[u]) {
                bool updated = false;
                for (int a : {0, 1}) {
                    for (int b : {0, 1}) {
                        if (prev[u][a] == prev[v][b] || prev[u][a] < 0) continue;
                        if (dist[u][a] + 1 < dist[v][b] && prev[v][b ^ 1] != prev[u][a]) {
                            dist[v][b] = dist[u][a] + 1;
                            prev[v][b] = prev[u][a];
                            updated = true;
                        }
                    }
                }
                if (updated) {
                    q.push(v);
                }
            }
        }
        
        for (int u : color[i]) {
            if (dist[u][1] < k) {
                cout << "NO\n";
                return;
            }
        }
    }
    
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

L. Nailoongs Always Lie

環状木構造における動的計画法問題。

n個の頂点とn個の辺からなるグラフは必ず環を形成するため、これは環状木の森となります。環上の一辺を切断すると、木構造上で2回の動的計画法を実行でき、複数の連結成分における最大値の和を求めます。

頂点uがNailoongである場合、頂点vは必ずNailoongではありません。頂点uがNailoongでない場合、頂点vはNailoongである場合とそうでない場合の両方が考えられます。
dp[u,0/1]をuがNailoongであるかどうかを表す状態として、遷移方程式は以下のようになります：

[dp_{u,1}=\sum_{v \in Sub_u}dp_{v,0} ][dp_{u,0}=\sum_{v \in Sub_u}\max(dp_{v,0},dp_{v,1}) ]辺を切断する際のdp値の処理に注意が必要です。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<int>> forward_graph(n + 1);
    vector<vector<int>> reverse_graph(n + 1);
    
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        forward_graph[i].push_back(x);
        reverse_graph[x].push_back(i);
    }
    
    int mark = 0;
    vector<int> visited(n + 1);
    vector<vector<int>> dp(n + 1);
    
    auto calculate = [&](auto &&self, int u) -> int {
        visited[u] = 1;
        dp[u] = {0, 1};
        
        for (int v : reverse_graph[u]) {
            if (v == mark) {
                dp[v][1] = -1E9;
                continue;
            }
            self(self, v);
            dp[u][1] += dp[v][0];
            dp[u][0] += max(dp[v][1], dp[v][0]);
        }
        
        return max(dp[u][0], dp[u][1]);
    };
    
    auto find_cycle = [&](auto &&self, int u) -> void {
        visited[u] = 1;
        if (forward_graph[u].empty()) return;
        
        if (visited[forward_graph[u][0]]) {
            mark = u;
        } else {
            self(self, forward_graph[u][0]);
        }
    };
    
    int result = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        
        find_cycle(find_cycle, i);
        if (mark == 0) continue;
        
        int temp = calculate(calculate, mark);
        mark = forward_graph[mark][0];
        temp = max(temp, calculate(calculate, mark));
        result += temp;
    }
    
    cout << result << "\n";
    
    return 0;
}

M. Master of Both VII

思考問題。

すべての3 ≤ i ≤ n-1に対する(1,i)のクエリを考え、結果をd_iとします。d_i = 0の場合は直接答えに追加します。

辺(x,y)は、x < i < yのクエリに対して1の貢献をします。

これらの辺は、非端点で交差しない区間を形成するため、2 ≤ i ≤ nの順序でスタックを管理します。

• もしd_i > d_{i-1}ならば、スタックにd_i - d_{i-1}個のi-1をプッシュします。
• もしd_i < d_{i-1}ならば、d_{i-1} - d_i個のスタックトップをポップし、辺(st[top], i)を形成します。

i-1で始まる区間とiで終わる区間が同時に存在しないことが証明できるため、このアプローチの正しさが保証されます。

時間計算量はO(n)です。

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void solve() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> edges;
    
    auto query = [](int l, int r) -> int {
        cout << "? " << l << " " << r << endl;
        int res;
        cin >> res;
        return res;
    };
    
    auto output = [&]() -> void {
        cout << "! ";
        for (auto &[x, y] : edges) {
            cout << x << " " << y << " ";
        }
        cout << endl;
    };
    
    stack<int> st;
    int last = 0;
    
    for (int i = 3; i <= n; i++) {
        int x = 0;
        if (i < n) {
            x = query(1, i);
        }
        
        if (x == 0 && i < n) {
            edges.push_back({1, i});
            while (!st.empty()) {
                edges.push_back({st.top(), i});
                st.pop();
            }
            last = x;
            continue;
        }
        
        if (x > last) {
            for (int j = 0; j < x - last; j++) {
                st.push(i - 1);
            }
        } else if (x < last) {
            for (int j = 0; j < last - x; j++) {
                edges.push_back({st.top(), i});
                st.pop();
            }
        }
        
        last = x;
    }
    
    output();
    
    cin >> n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}