面白かった
問題概要
以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。
- はすべて互いに相異なる整数
これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君はそれぞれ次のようなアルゴリズムを考えた。
このとき、(高橋君法による個数) - (青木君法による個数) がちょうど となるような 個の区間を構築せよ。
高橋君
- の値が昇順となるように, 区間を並び替える
- について、以下を行う。
- これまでに選んだどの区間とも交わらないならば、それを選ぶ
青木君
- の値が昇順となるように, 区間を並び替える
- について、以下を行う。
- これまでに選んだどの区間とも交わらないならば、それを選ぶ
制約
考えたこと
まず、高橋君の方法は最適解を導く。よって、 となることはありえない。さらに、
- は、高橋君 = N、青木君 = 0 となるしかないが、青木君は最低でも 1 以上にはなるのでありえない
- は、高橋君 = N、青木君 = 1 となるしかない (青木君 = 0 はない) が、高橋君 = N であることは「区間がすべて互いに交わらない」ことを意味していて、そのとき青木君も N になるのでダメ
ということがわかる。残りは の場合を考えていこう。
M = 0
M = 0 のときは比較的わかりやすい。下図みたいにしておけば、
- 高橋君 = N
- 青木君 = N
となるので OK。
それ以外
それ以外のときも、下図みたいにしておけば、
- 高橋君 = N - 1 (最初の長いやつだけダメ)
- 青木君 = N - M - 1
となるので OK。
コード
の場合に注意。この場合は であるが、Yes となる。
#include <bits/stdc++.h> using namespace std; void solve(long long N, long long M) { if (M == 0) { long long cur = 1; for (int i = 0; i < N; ++i) cout << cur++ << " " << cur++ << endl; return; } if (M < 0 || M >= N - 1) { cout << -1 << endl; return; } const long long GETA = 500000000; cout << 1 << " " << GETA << endl; long long cur = 2; for (int i = 0; i < M+1; ++i) cout << cur++ << " " << cur++ << endl; cur = GETA + 1; for (int i = 0; i < N-M-2; ++i) cout << cur++ << " " << cur++ << endl; } int main() { long long N, M; cin >> N >> M; solve(N, M); }