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

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

JOIG 2024 B - ダンス (4Q, 難易度 4)

JOI AtCoder AOJ JOI難易度4 JOIG NoviSteps4Q ソート 【問題集】ソート 考察テク:最大値や最小値に着目する Greedy Greedy:交換しても悪化しない Greedy:端から順に決まっていく 探索順序を工夫して解く 数列 制約条件:ある値<=K グルーピングの最適化 グルーピング 最適化問題 Yes/No判定問題

ちゃんと証明しようとすると、結構大変！

問題概要

2N 人の生徒がいて、生徒 i の身長は A_{i} である。

これらの生徒を 2 人ずつ N 組に分けて、どの組も身長差が D 以下となるようにしたい。

そのようなことが可能かどうかを判定せよ。

制約

  • 1 \le N \le 100
  • 0 \le D \le 100
  • 1 \le A_{i} \le 100

考えたこと

このようなとっかかりの難しい問題では、「まず最小値に着目する」とよいことが多いです。

今回は、まず「身長が最小の生徒と誰を組ませるべきか」を考えてみましょう。考えやすくするために、生徒の身長を適宜ソートして

A_{1} \le A_{2} \le \dots \le A_{2N}

を満たすとします。今考えていることは、 A_{1} とペアを組ませるべきは誰か？　となります。直感的には、 A_{2} と組ませるのが良さそうに感じるでしょう。そうすれば、 A_{1} はペアを組む相手との身長差を最小にできます。

ここで気になることは、 A_{1} のために A_{2} を使ったが、他の場面でも A_{2} を使いたくなることってないんだろうか？？？ということです。もし、そのような場面があるのだとしたら、 A_{1} と A_{2} を組ませるのが良いという結論が嘘だということです。

......実は、今回は、 A_{1} のために A_{2} を割り当ててしまってよいということが証明できます！！！！！　

今回の問題程度の複雑さであれば、わざわざ証明しなくても「きっとそうに違いない」と確信が持てれば、その解法を提出してみてもよいえしょう。しかし、より高難易度の問題に挑む際には、証明の考え方を身につけておくことはとても重要です。

A_{1} のために A_{2} を割り当てて良いことの証明

それでは、 A_{1} のために A_{2} を割り当てると考えて問題ないことを証明してみましょう！

もし、条件を満たす組分けが存在して、

  • A_{1} と A_{p} （ p \neq 1）
  • A_{2} と A_{q}（ q \neq 1）

がペアになっているとしましょう。このとき、実は

  • A_{1} と A_{2}
  • A_{p} と A_{q}

というように組み替えをしても条件を満たします。つまり、 A_{1} と A_{2} は必ず組むことにしてもよいということが言えるわけです。

まず、 A_{2} \le A_{p} ですから、

A_{2} - A_{1} \le A_{p} - A_{1} \le D

となります。さらに、

  • p \lt q の場合：
    • A_{q} - A_{p} \le A_{q} - A_{2} \le D（ A_{2} \le A_{p} より）
  • p \gt q の場合：
    • A_{p} - A_{q} \le A_{p} - A_{1} \le D（ A_{1} \le A_{q} より）

となり、いずれも |A_{p} - A_{q}| \le D を満たします。以上より、示せました。

もとの問題に戻り

ここまでの議論から、 A_{1} と A_{2} は必ず組むとしてよいことが分かりました。

そうすると、残りの A_{3}, A_{4}, \dots, A_{2N} を組分けする問題へと帰着されます。そして、また同様の議論によって、 A_{3} と A_{4} は必ず組むとしてよいことが言えます。

以上の手続きを繰り返すことで、結局次のことが言えます。

A_{1} \le A_{2} \le \dots \le A_{2N} となるように並び替えたとする。このとき、

  • A_{2} - A_{1} \le D
  • A_{4} - A_{3} \le D
  • A_{6} - A_{5} \le D
  • \dots
  • A_{2N} - A_{2N-1} \le D

をすべて満たすならば "Yes"、そうでなければ "No" である。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, D;
    cin >> N >> D;
    vector<int> A(N*2);
    for (int i = 0; i < N*2; i++) cin >> A[i];

    sort(A.begin(), A.end());
    bool res = true;
    for (int i = 0; i < N*2; i += 2) {
        if (A[i+1] - A[i] > D) res = false;
    }
    cout << (res ? "Yes" : "No") << endl;
}