結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー marc2825
提出日時 2026-05-30 08:28:26
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 2,986 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 245 ms
コンパイル使用メモリ 96,232 KB
実行使用メモリ 84,480 KB
最終ジャッジ日時 2026-07-10 20:56:41
合計ジャッジ時間 5,588 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 未定義変数 data を参照していた箇所を修正
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])

    # 完全グラフの辺の数と、残すべき辺の数
    E_total = N * (N - 1) // 2
    E_target = E_total - M

    # K本の辺がなければ、距離Kのパスは作れない
    if E_target < K:
        print("No")
        return

    # K = 1 の場合の特別処理
    if K == 1:
        E_max = E_total
        if E_target > E_max:
            print("No")
            return
        
        print("Yes")
        kept_edges = set()
        kept_edges.add((1, N))
        
        edges_needed = E_target - 1
        for u in range(1, N + 1):
            for v in range(u + 1, N + 1):
                if (u, v) == (1, N):
                    continue
                if edges_needed > 0:
                    kept_edges.add((u, v))
                    edges_needed -= 1
                    
        # 削除された辺を出力
        for u in range(1, N + 1):
            for v in range(u + 1, N + 1):
                if (u, v) not in kept_edges:
                    print(f"{u} {v}")
        return

    # K >= 2 の場合
    # パスに属さない「余剰な頂点」をすべて頂点1からの距離1のグループ（Layer 1）に配置した場合が、
    # ショートカットを作らずに最も多くの辺を持てる最大のグラフ(MaxG)となる。
    S = N - K
    E_max = S * (S - 1) // 2 + 2 * S + K - 2
    
    if E_target > E_max:
        print("No")
        return

    print("Yes")
    kept_edges = set()
    
    # 1. 必須となる距離Kの骨格パスを構築する
    kept_edges.add((1, 2))
    for i in range(2, K + 1):
        u = i if i == 2 else N - K + i - 1
        v = N - K + i
        kept_edges.add((u, v))
        
    # 2. 追加しても最短距離Kを崩さない「オプションの辺」をリストアップ
    optional_edges = []
    # Layer 1 内部の辺
    for u in range(2, N - K + 2):
        for v in range(u + 1, N - K + 2):
            optional_edges.append((u, v))
            
    # 頂点1(Layer 0) と Layer 1 の辺
    for u in range(3, N - K + 2):
        optional_edges.append((1, u))
        
    # Layer 1 と Layer 2 の辺
    for u in range(3, N - K + 2):
        optional_edges.append((u, N - K + 2))
        
    # 3. 目標の辺数(E_target)になるまでオプションの辺を追加する
    edges_needed = E_target - K
    for i in range(edges_needed):
        kept_edges.add(optional_edges[i])
        
    # 4. 全ての組み合わせのうち、残さなかった辺（＝削除する辺）を出力する
    for u in range(1, N + 1):
        for v in range(u + 1, N + 1):
            if (u, v) not in kept_edges:
                print(f"{u} {v}")

if __name__ == '__main__':
    solve()
0