| 第22回日本情報オリンピック 二次予選 |
|
|
2022年12月13日
情報オリンピック日本委員会
|
解説担当：米田優峻
この小課題では N = 1 であるため，4 人組を作る方法は「全員を選ぶ」しかない． したがって，「A1, B1, C1, D1 の最大値」から「A1, B1, C1, D1 の最小値」を引いた値を出力すれば正解となる．
なお C++ では，最大値は max 関数，最小値は min 関数を用いて計算することができる（この関数を利用するには algorithm をインクルードする必要がある）．たとえば A1, B1, C1, D1 の最大値は，max({A[1], B[1], C[1], D[1]}) で計算することができる．詳しくは以下のソースコードを参照すること．
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[75009], B[75009], C[75009], D[75009];
int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 1; i <= N; i++) cin >> B[i];
for (int i = 1; i <= N; i++) cin >> C[i];
for (int i = 1; i <= N; i++) cin >> D[i];
// 出力
cout << max({ A[1], B[1], C[1], D[1] }) - min({ A[1], B[1], C[1], D[1] }) << endl;
return 0;
}
まずは重要なキーワードを一つ紹介する．全探索とは，あり得るすべてのパターンを調べることによって答えを求める手法である．たとえばパスワードを忘れてしまったけど携帯にログインしたい場合，0000 から 9999 まで一つずつ調べたくなる人もいるが，これは全探索の一種である．また，家から学校までの最短経路も，（計算に時間はかかるが）家から学校までのすべての経路を調べることで求められる．このように，世の中の多くの問題は，原理的には全探索で解くことができる．
今回の「ジョイ四人組」も，全探索で解くことができる問題の一つである．実際，4 人の選び方を N4 通り調べ，この中で最大値と最小値の差が一番小さくなるものを出力すれば，正解となる．
さて，このような解法で実行時間制限には間に合うのだろうか．まず，この小課題の制約は N ≦ 30 であるため，最大ケースの N = 30 のとき，全部で 304 = 810000 通りを調べる必要がある．一方，情報オリンピックのジャッジの計算速度は毎秒数億回程度であるため，実行時間制限の 3 秒には余裕を持って間に合うといえる．（注：家庭用 PC も似たような計算速度になる）
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[75009], B[75009], C[75009], D[75009];
int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 1; i <= N; i++) cin >> B[i];
for (int i = 1; i <= N; i++) cin >> C[i];
for (int i = 1; i <= N; i++) cin >> D[i];
// 全探索
int Answer = 2000000000; // 最初は非常に大きい値にセット
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= N; k++) {
for (int l = 1; l <= N; l++) {
int Maximum = max({ A[i], B[j], C[k], D[l] }); // 4 人の身長の最大値
int Minimum = min({ A[i], B[j], C[k], D[l] }); // 4 人の身長の最小値
Answer = min(Answer, Maximum - Minimum);
}
}
}
}
// 出力
cout << Answer << endl;
return 0;
}
この小課題の制約は N ≦ 2000 と大きいため，残念ながら全探索では間に合わない．実際，20004 は 10 兆を超えるため，絶望的である．だが，ここで特殊な制約「Ai, Bj, Ck, Dl ≦ 10」を上手く活用することができるか，一度立ち止まって考えてみよう．
まず，同じクラスに同じ身長の人が 2 人以上いても無駄なので，1 人しかいないと考えても答えは変わらない．たとえば，1 年 A 組には生徒が 10 人いて，各生徒の身長が 4, 4, 4, 6, 6, 6, 6, 6, 9, 9 であるとしよう．この場合，1 年 A 組には生徒が 3 人いて，各生徒の身長が 4, 6, 9 であるとみなしても全く問題にならない．これは 1 年 B 組・C 組・D 組でも同じことがいえるため，たとえば
というケースの場合，以下のように考えても問題ない．そこで，重複を取り除いたうえで全探索をすると，元々 104$ 通り調べる必要があったところが，3 × 2 × 4 × 2 = 48 通りしか調べる必要がなくなる．
それでは，この解法で小課題 3 が解けるのかを考えてみよう．制約より，各生徒の身長は 1 以上 10 以下なので，重複を取り除いた後は A, B, C, D の要素数が 10 以下になる．したがって，高々 104 = 10000 通りしか全探索をする必要がなく，実行時間制限に間に合うことがわかる．
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector A, B, C, D;
int main() {
// 入力（重複を取り除きやすいように，vector 型を使っていることに注意！）
cin >> N;
A.resize(N, 0); for (int i = 0; i < N; i++) cin >> A[i];
B.resize(N, 0); for (int i = 0; i < N; i++) cin >> B[i];
C.resize(N, 0); for (int i = 0; i < N; i++) cin >> C[i];
D.resize(N, 0); for (int i = 0; i < N; i++) cin >> D[i];
// A の重複を取り除く
sort(A.begin(), A.end());
A.erase(unique(A.begin(), A.end()), A.end());
// B の重複を取り除く
sort(B.begin(), B.end());
B.erase(unique(B.begin(), B.end()), B.end());
// C の重複を取り除く
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
// D の重複を取り除く
sort(D.begin(), D.end());
D.erase(unique(D.begin(), D.end()), D.end());
// 全探索
int Answer = 2000000000; // 最初は非常に大きい値にセット
for (int i = 0; i < (int)A.size(); i++) {
for (int j = 0; j < (int)B.size(); j++) {
for (int k = 0; k < (int)C.size(); k++) {
for (int l = 0; l < (int)D.size(); l++) {
int Maximum = max({ A[i], B[j], C[k], D[l] });
int Minimum = min({ A[i], B[j], C[k], D[l] });
Answer = min(Answer, Maximum - Minimum);
}
}
}
}
// Output
cout << Answer << endl;
return 0;
}
まず，この小課題では身長が 2000 以下と小さいため，身長の最小値を決め打ち全探索することを考える．つまり，次のようなことを考える．
それでは，身長の最小値が x のときの答えは，どうやって求めれば良いのだろうか．実は，各クラスから「身長が x 以上である中で最も身長が低い生徒」を選ぶのが最適である．例として，以下のようなテストケースを考えよう．
たとえば「身長の最小値を 160 にする」と決めた場合，1 年 A 組からは 160 以上で身長が一番低い 166 センチを選ぶのが最適である．同様に，B 組からは 162 センチ，C 組からは 160 センチ，D 組からは 185 センチを選ぶのが最適である．そのため，身長の最大値として考えられる最小の値は，max ( 166, 162, 160, 185 ) = 185 となる．
そして，160 以外の場合についても頑張って調べると，出力すべき答えが 14 であることが分かる．（注：身長の最小値が 186 のときが最適である．このとき，身長の最大値として考えられる最小の値は，max ( 200, 191, 186, 187 ) = 200 となる）
それでは，この解法の計算回数はどれくらいになるのであろうか．自然に実装すると，身長の最小値が x の場合の答えを求めるのに計算量 O(N) かかる．また，身長は 2000 以下であるため，先程の計算量 O(N) の処理を 2000 回行わなければならない．そのため，大まかな計算回数は 2000 × N となるが，N ≦ 2000 であるため，実行時間制限には間に合う．
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[75009], B[75009], C[75009], D[75009];
// 身長の最小値が LIMIT の場合、最大値として考えられる最小の値を返す
int solve(int LIMIT) {
int PA = 2000000000; // A 組の LIMIT 以上の最小値
int PB = 2000000000; // B 組の LIMIT 以上の最小値
int PC = 2000000000; // C 組の LIMIT 以上の最小値
int PD = 2000000000; // D 組の LIMIT 以上の最小値
for (int i = 1; i <= N; i++) {
if (A[i] >= LIMIT) PA = min(PA, A[i]);
if (B[i] >= LIMIT) PB = min(PB, B[i]);
if (C[i] >= LIMIT) PC = min(PC, C[i]);
if (D[i] >= LIMIT) PD = min(PD, D[i]);
}
if (PA == 2000000000 || PB == 2000000000 || PC == 2000000000 || PD == 2000000000) return 2000000000;
return max({ PA, PB, PC,PD });
}
int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 1; i <= N; i++) cin >> B[i];
for (int i = 1; i <= N; i++) cin >> C[i];
for (int i = 1; i <= N; i++) cin >> D[i];
// 決め打ち全探索
int Answer = 2000000000;
for (int i = 1; i <= 2000; i++) {
Answer = min(Answer, solve(i) - i);
}
// 出力
cout << Answer << endl;
return 0;
}
この小課題では，身長としてあり得る範囲が 1 以上 109 以下と一気に広がる．そのため，小課題 4 の解法では計算回数が 109 × N 回必要になってしまい，TLE となってしまう．
しかし，ここで恐れることはない．実は，身長の最小値として 1, 2, …, 10^9 を全部探索する必要はないのである． 具体的には，Ai, Bj, Ck, Dl に現れる 4N 通りを調べれば十分である． たとえば，先程も例に挙げた
というケースの場合，「身長の最小値が 150 であるとき，身長の最大値として考えられる最小の値は？」という質問を考えるのは無駄である（身長が 150 の人は誰一人としていないため）．
すると，計算回数を 4N × N = 4N2 回程度にまで削減することができる． N ≦ 2000 であるため，C++ など計算速度の速い言語であれば，AC を得ることができる．
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[75009], B[75009], C[75009], D[75009];
// 身長の最小値が LIMIT の場合、最大値として考えられる最小の値を返す
int solve(int LIMIT) {
int PA = 2000000000;
int PB = 2000000000;
int PC = 2000000000;
int PD = 2000000000;
for (int i = 1; i <= N; i++) { if (A[i] >= LIMIT) PA = min(PA, A[i]); }
for (int i = 1; i <= N; i++) { if (B[i] >= LIMIT) PB = min(PB, B[i]); }
for (int i = 1; i <= N; i++) { if (C[i] >= LIMIT) PC = min(PC, C[i]); }
for (int i = 1; i <= N; i++) { if (D[i] >= LIMIT) PD = min(PD, D[i]); }
if (PA == 2000000000 || PB == 2000000000 || PC == 2000000000 || PD == 2000000000) return 2000000000;
return max({ PA, PB, PC, PD });
}
int main() {
// 入力
cin >> N;
for (int i = 1; i <= N; i++) cin >> A[i];
for (int i = 1; i <= N; i++) cin >> B[i];
for (int i = 1; i <= N; i++) cin >> C[i];
for (int i = 1; i <= N; i++) cin >> D[i];
// 決め打ち全探索
int Answer = 2000000000;
for (int i = 1; i <= N; i++) Answer = min(Answer, solve(A[i]) - A[i]);
for (int i = 1; i <= N; i++) Answer = min(Answer, solve(B[i]) - B[i]);
for (int i = 1; i <= N; i++) Answer = min(Answer, solve(C[i]) - C[i]);
for (int i = 1; i <= N; i++) Answer = min(Answer, solve(D[i]) - D[i]);
// 出力
cout << Answer << endl;
return 0;
}
まず小課題 5 の解法では，「身長が x 以上の中の最小値」を各クラスについて求める必要があった．そして小課題 5 では，これを全探索によって O(N) かけて求めていた（上の実装例の solve 関数を参照）．
しかし，配列 A, B, C, D を予めソートしておくと，配列の二分探索によってこの値を O(log N) で求めることができる（知らない方はインターネット等で調べてみることを推奨する）．そのため，プログラム全体の計算量が O(N log N) に改善され，ついに満点を得ることができる． （実装例はサンプルソース (C++, Python) を参照．）