#1167722 (C++17) No.3585 Make Ends Meet (Easy)

• 問題: No.3585 Make Ends Meet (Easy)
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:15:07
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 5,103 bytes
• コンパイル時間: 1,562 ms
• コンパイル使用メモリ: 235,128 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-10 20:57:31
• 合計ジャッジ時間: 3,651 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 2
other	AC * 48

ソースコード

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

using ll = long long;
using P = pair<int,int>;

int dist_after_removing(int N, const vector<P>& removed_edges) {
    set<P> removed;
    for (auto [u, v] : removed_edges) {
        if (u > v) swap(u, v);
        removed.insert({u, v});
    }

    vector<vector<int>> G(N + 1);
    for (int u = 1; u <= N; u++) {
        for (int v = u + 1; v <= N; v++) {
            if (removed.count({u, v})) continue;
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }

    const int INF = 1e9;
    vector<int> dist(N + 1, INF);
    queue<int> q;
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : G[v]) {
            if (dist[to] > dist[v] + 1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }

    return dist[N];
}

bool validate(int N, ll M, int K, const vector<P>& ans) {
    if ((ll)ans.size() != M) return false;

    set<P> st;
    for (auto [u, v] : ans) {
        if (!(1 <= u && u <= N)) return false;
        if (!(1 <= v && v <= N)) return false;
        if (u == v) return false;
        if (u > v) swap(u, v);
        if (st.count({u, v})) return false;
        st.insert({u, v});
    }

    int d = dist_after_removing(N, ans);
    return d == K;
}

optional<vector<P>> brute(int N, ll M, int K) {
    vector<P> edges;
    for (int u = 1; u <= N; u++) {
        for (int v = u + 1; v <= N; v++) {
            edges.push_back({u, v});
        }
    }

    int E = (int)edges.size();
    if (E > 25) return nullopt;

    for (int mask = 0; mask < (1 << E); mask++) {
        if (__builtin_popcount((unsigned)mask) != M) continue;

        vector<P> removed;
        for (int i = 0; i < E; i++) {
            if (mask >> i & 1) {
                removed.push_back(edges[i]);
            }
        }

        if (dist_after_removing(N, removed) == K) {
            return removed;
        }
    }

    return nullopt;
}

optional<vector<P>> construct(int N, ll M, int K) {
    ll E = 1LL * N * (N - 1) / 2;

    if (K == 1) {
        if (M > E - 1) return nullopt;

        vector<P> removed;
        for (int u = 1; u <= N; u++) {
            for (int v = u + 1; v <= N; v++) {
                if (u == 1 && v == N) continue;
                if ((ll)removed.size() < M) {
                    removed.push_back({u, v});
                }
            }
        }
        return removed;
    }

    ll minM = 1LL * K * (K - 1) / 2 + 1LL * (N - K - 1) * (K - 2);
    ll maxM = E - K;

    if (!(minM <= M && M <= maxM)) return nullopt;

    vector<vector<int>> layers(K + 1);
    layers[0].push_back(1);
    layers[K].push_back(N);

    for (int i = 1; i < K; i++) {
        layers[i].push_back(i + 1);
    }

    for (int v = K + 1; v <= N - 1; v++) {
        layers[1].push_back(v);
    }

    vector<int> layer_id(N + 1, -1);
    for (int i = 0; i <= K; i++) {
        for (int v : layers[i]) {
            layer_id[v] = i;
        }
    }

    set<P> removed;

    for (int u = 1; u <= N; u++) {
        for (int v = u + 1; v <= N; v++) {
            if (abs(layer_id[u] - layer_id[v]) >= 2) {
                removed.insert({u, v});
            }
        }
    }

    vector<int> path;
    path.push_back(1);
    for (int i = 1; i < K; i++) {
        path.push_back(i + 1);
    }
    path.push_back(N);

    set<P> path_edges;
    for (int i = 0; i < K; i++) {
        int u = path[i];
        int v = path[i + 1];
        if (u > v) swap(u, v);
        path_edges.insert({u, v});
    }

    for (int u = 1; u <= N; u++) {
        for (int v = u + 1; v <= N; v++) {
            if ((ll)removed.size() == M) break;
            if (removed.count({u, v})) continue;
            if (path_edges.count({u, v})) continue;
            removed.insert({u, v});
        }
        if ((ll)removed.size() == M) break;
    }

    if ((ll)removed.size() != M) return nullopt;

    vector<P> ans(removed.begin(), removed.end());
    return ans;
}

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

    int N, K;
    ll M;
    cin >> N >> M >> K;

    assert(2 <= N && N <= 100);
    assert(0 <= M && M <= 1LL * N * (N - 1) / 2);
    assert(1 <= K && K <= N - 1);

    optional<vector<P>> ans;

    if (N <= 6) {
        ans = brute(N, M, K);

        // 愚直で見つからなかった場合でも、本解と一致するか確認できる
        // 本来はどちらでもよいが、検証用として construct も呼ぶ
        auto ans2 = construct(N, M, K);

        if (ans.has_value() != ans2.has_value()) {
            cerr << "Mismatch between brute and construct existence!\n";
            assert(false);
        }

        if (ans2.has_value()) {
            assert(validate(N, M, K, *ans2));
        }
    } else {
        ans = construct(N, M, K);
    }

    if (!ans.has_value()) {
        cout << "No\n";
        return 0;
    }

    assert(validate(N, M, K, *ans));

    cout << "Yes\n";
    for (auto [u, v] : *ans) {
        cout << u << ' ' << v << '\n';
    }

    return 0;
}