#1171951 (C++14) No.3585 Make Ends Meet (Easy)

• 問題: No.3585 Make Ends Meet (Easy)
• ユーザー: startcpp
• 提出日時: 2026-07-18 18:30:50
• 言語: C++14 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,186 bytes
• コンパイル時間: 424 ms
• コンパイル使用メモリ: 83,608 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-18 18:30:54
• 合計ジャッジ時間: 2,980 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 28 WA * 20

ソースコード

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m, K;
	cin >> n >> m >> K;
	m = n * (n - 1) / 2 - m;

	if (m < K || m > (K - 1) + (n - K + 1) * (n - K) / 2) {
		cout << "No" << endl;
		return 0;
	}

	vector<vector<bool>> used(n, vector<bool>(n));
	for (int i = 0; i < K - 1; i++) {
		used[i][i + 1] = true;
	}

	for (int i = K - 1; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (m > 0) {
				used[i][j] = true;
				m--;
			}
		}
	}

	cout << "Yes" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (!used[i][j]) {
				cout << i + 1 << " " << j + 1 << endl;
			}
		}
	}
	return 0;
}

// 考察
//
// M 辺を「残す」という形で考察を進める。（割と終盤まで誤読したので…）
// つまり、事前に M <- N(N-1)/2 - Mという変換をする。
//
// (1) K が小さい方から考える
// (2) K に対するグラフ表現を試みる
// (1) : K = 1 は 1--N があれば何でもいい。1 <= M <= N(N-1)/2 で可能。
//       K = 2 は K辺以上はいる。1--Nは削除。K <= M <= N(N-1)/2 - 1で可能。
//       K = 3 は 削除辺が単体では決まらないから難しめ。
//
// (2) 階層0,1,...,Kを考える。階層0は頂点1だけ。それ以外は1頂点以上。階層Kに頂点Nを含める。
//     隣り合う階層（階層iとi+1）と同じ階層の頂点間だけ辺を張ってよい。
//     階層0->1->…->Kをつなぐパスを1つ以上つくる。
//     これで最短距離がちょうどKのケースを過不足なく表現できていそう。
//
//     達成可能なMの最小値はKで自明。達成可能なMの最大値は何になるか。
//     たぶん階層0～K-1は1頂点で、階層KにN-K頂点あるケースが最大になると思う。
//     以下を証明したらよさそう。
//
//     隣り合う2階層が「a頂点, b頂点」の最大ケース。c = a + b とおき c は固定する。
//     a, b >= 1 のもとで、a = 1 が最適であることを示せばOK。
//     辺の数の最大値は、
//     ab + a(a-1)/2 + b(b-1)/2 = a(c-a) + a(a-1)/2 + (c-a)(c-a-1)/2
//     = ac - a^2 + (a^2 - a + c^2 - ac - c - ac + a^2 + a) / 2
//     = ac - a^2 + a^2 - ac + (c^2 - c) / 2
//     = (c^2 - c) / 2 = c(c - 1) / 2
//     なんとaが消去された。考えてみれば当たり前で、これはc頂点の完全グラフに等しい。
//
//     もう一つ足りない考察に気がついた。全体で何辺使うか？の最適化。
//     階層iでC_i頂点使っているとすると、f(n) = n(n-1)/2として、
//     score(C) = f(C_0 + C_1) + f(C_1 + C_2) + ... + f(C_{K-1} + C_K)
//     が最大の辺の数になる。C_1 ～ C_{K-1} のうちいずれかが2以上のとき、
//     score(C)を悪化させずに C_1 ～ C_{K-1} をすべて1のケースに帰着させることができそう。
//     C_i >= 2 を満たす最大のi (1 <= i <= K-1) をとる。
//     C_iを1減らし、C_{i-1}を1増やすとき、score(C)の変化量はどうなるか。
//     before: f(C_{i - 1} + C_{i}) + f(C_{i} + C_{i + 1})
//      after: f(C_{i - 1} + C_{i}) + f(C_{i} + C_{i + 1} - 1)
//     のようになり、それ以外のところは影響しない。f(n)はnが非負なら単調増加なので、
//     score(C)は減少する。これを繰り返すと、帰着可能。
//     「階層i-1,i間の頂点数が変わらない」かつ「階層i,i+1間の頂点数が減る」から、
//      全体としては減るという解釈ができる。
//
// つまり、頂点1,2,…,K+1を階層0,1,...,Kに配置してパスで結んで、
// 頂点K～Nの間でN-K+1頂点のなかで0辺～完全グラフのいずれかを適当に作ればOK。
// 達成可能な M は K <= M <= (K-1) + (N-K+1)(N-K)/2 になる。
//
// この問題は、最短距離がKであることのグラフ表現という典型テクを適用したのち、
// マトロイドっぽいやつ（交換しても悪化しない的なやつ）を適用するタイプの問題に見えた。
// ちょうどMにするというのはオマケで、最大値の考察が肝だと思った。