けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 106 C - Solutions (水色, 500 点)

面白かった

問題概要

以下の条件を満たすような  N 個の区間 ( i 番目を  \lbrack L_{i}, R_{i} \rbrack とする) を構築したい。

  •  1 \le L_{i} \lt R_{i} \le 10^{9}
  •  L_{1}, \dots, L_{N}, R_{1}, \dots, R_{N} はすべて互いに相異なる整数

これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君はそれぞれ次のようなアルゴリズムを考えた。

このとき、(高橋君法による個数) - (青木君法による個数) がちょうど  M となるような  N 個の区間を構築せよ。

高橋君

  •  R_{i} の値が昇順となるように, 区間を並び替える
  •  i=1,2, \dots ,N について、以下を行う。
    • これまでに選んだどの区間とも交わらないならば、それを選ぶ

青木君

  •  L_{i} の値が昇順となるように, 区間を並び替える
  •  i=1,2, \dots ,N について、以下を行う。
    • これまでに選んだどの区間とも交わらないならば、それを選ぶ

制約

  •  1 \le N \le 2 \times 10^{5}
  •  -N \le M \le N

考えたこと

まず、高橋君の方法は最適解を導く。よって、 M \lt 0 となることはありえない。さらに、

  •  M = N は、高橋君 = N、青木君 = 0 となるしかないが、青木君は最低でも 1 以上にはなるのでありえない
  •  M = N-1 は、高橋君 = N、青木君 = 1 となるしかない (青木君 = 0 はない) が、高橋君 = N であることは「区間がすべて互いに交わらない」ことを意味していて、そのとき青木君も N になるのでダメ

ということがわかる。残りは  M = 0, 1, 2, \dots, N - 2 の場合を考えていこう。

M = 0

M = 0 のときは比較的わかりやすい。下図みたいにしておけば、

  • 高橋君 = N
  • 青木君 = N

となるので OK。

f:id:drken1215:20201025002022p:plain

それ以外

それ以外のときも、下図みたいにしておけば、

  • 高橋君 = N - 1 (最初の長いやつだけダメ)
  • 青木君 = N - M - 1

となるので OK。

f:id:drken1215:20201025002031p:plain

コード

 N = 1, M = 0 の場合に注意。この場合は  M = N - 1 であるが、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);
}