ARC 106 | C - Solutions

問題

https://atcoder.jp/contests/arc106/tasks/arc106_c

考えたこと

区間スケジューリングを高橋君と青木君は解いている。高橋君は最適解で青木君は最適ではない。

高橋君の値 - 青木君の値 = M 

N個の区間に対して上記を満たすMが存在するか確認し、存在するならばその区間を出力する問題である。

Mを場合分けして考える。

M < 0の場合

M < 0ということは青木君のほうが最適に問題を解けるということなのでありえない。

M = 0の場合

高橋君と青木君がどちらも最適に答えを出している。高橋君と青木君が同じ区間を選ぶようにするには以下のように区間がそれぞれ離れていればいい。

M > 0の場合

まずM=1の場合を考える。青木君は高橋君より区間を1つ落としているので以下のように区間を作りNに応じたXの値を決めればいい。

ただし、N=1のときはM=0にしかならないので成り立たない。N=2のときも以下のようになりM=0にしかならないので成り立たない。

また、M=Nのときは青木君が0区間となるのでこれもありえない。

また、以下のようにN-Mの差分は2以上必要なので1以下のときもありえない。
(別の考え方として、N-M==1ということは高橋君はN個区間を取れるので青木君もN個区間がとれM=1にはならない)

整理すると、

N <= 2のときはありえない。
M - N < 2のときはありえない。
N > 2のときは区間を作れる。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  int n, m;
  cin >> n >> m;
  if (m < 0) {
    cout << -1 << endl;
    return 0;
  }
  if (m == 0) {
    for (int i = 1; i <= n; i++) {
      cout << (i * 2 - 1) << " " << (i * 2) << endl;
    }
    return 0;
  }
  if (n <= 2) {
    cout << -1 << endl;
    return 0;
  }
  if (n - m < 2) {
    cout << -1 << endl;
    return 0;
  }
  int x = m + 1;
  // Xを覆っている1区間を出す
  cout << 1 << " " << 2 + 2 * x << endl;
  // 覆われているX個の区間を出す
  for (int i = 1; i <= x; i++) {
    cout << (i * 2) << " " << (i * 2 + 1) << endl;
  }
  // それ以降の区間を出す
  int base = 2 + 2 * x + 1;
  for (int i = 0; i < n - x - 1; i++) {
    cout << (base + i * 2) << " " << (base + i * 2 + 1) << endl;
  }
}

参考

• 解説: https://atcoder.jp/contests/arc106/editorial/242