2023-01-15

JOI 二次予選 2023 A - 年齢の差 (AOJ 0747) (5Q, 難易度 3)

シンプルながらも、学べるポイントがたくさんある問題ですね

問題概要

JOI 市には $1$ から $N$ までの番号が付けられた $N$ 人の住民がいて、住民 $i$ ( $1 \le i \le N$ ) の年齢は $A_{i}$ 歳です。

JOI 市の住民の年齢 $A_{1}, A_{2}, \dots, A_{N}$ が与えられます。 $i = 1, 2, \dots, N$ に対して、住民 $i$ と他の住民との年齢の差の最大値を求めるプログラムを作成してください。

制約

$2 \le N \le 250000$
$0 \le A_{i} \le 10^{9}$

解法

ステップ 1：まず 0-indexed にする

JOI の問題文では、与えられる配列の添字が 1 始まりであることがよくあります。今回も $N$ 人の住民の年齢が $A_{1}, A_{2}, \dots, A_{N}$ というように、1 始まりになっています。

しかし C++ や Python をはじめ、多くのプログラミング言語では、配列の先頭の添字は 0 です。そこで多くの場合、問題の添字を 0 始まりになるように読み替えるとよいでしょう。そうすると、次のようになります。

JOI 市には $0$ から $N-1$ までの番号が付けられた $N$ 人の住民がいて、住民 $i$ ( $0 \le i \le N-1$ ) の年齢は $A_{i}$ 歳です。

JOI 市の住民の年齢 $A_{0}, A_{1}, \dots, A_{N-1}$ が与えられます。 $i = 0, 1, \dots, N-1$ に対して、住民 $i$ と他の住民との年齢の差の最大値を求めるプログラムを作成してください。

もとの問題文と変わった部分に注目してみてください。なお、このように、0 始まりの添字を 0-indexed と呼びます。

ステップ 2：問題の意味を把握する

まずは問題の意味を頑張って把握しましょう。もしかしたら、「 $i = 0, 1, \dots, N-1$ に対して、〜してください」という趣旨の問題を初めて解く方も多いかもしれないですね。

一瞬「？」が飛ぶ人も多いかもしれませんが、難しくはありません。次のようにすればよいです。

for (int i = 0; i < N; ++i) {
    // i についての問題を解く

}

まずは、やってみましょう。今回は「 $i$ についての問題」とは、次のような問題です。

$A_{0}$ と $A_{i}$ の差
$A_{1}$ と $A_{i}$ の差
...
$A_{N-1}$ と $A_{i}$ の差

をそれぞれ求めて、その最大値を求めてください

以上を踏まえると、次のようなコードが書けそうです。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 各 i についての問題を解く
    for (int i = 0; i < N; ++i) {
        int res = 0;

        // A[i] と、A{0], A[1], ..., A[N-1] との差の最大値を求める
        for (int j = 0; j < N; ++j) {
            res = max(res, abs(A[i] - A[j]));
        }
        cout << res << endl;
    }
}

この解法で部分点を獲得できます。具体的には 100 点中 55 点を獲得できます。

しかし全体としては TLE (Time Limit Exceeded) という判定になるはずです。プログラムの実行に時間がかかりすぎて、計算実行制限時間である 1 秒以内に処理を終えられないということです。なぜそのようになるかを考えてみましょう。

上のコードを見ると、for 文が 2 重になっています。

1 個目の for 文で $i = 0, 1, \dots, N-1$ について考えていて
それぞれについて 2 個目の for 文で $j = 0, 1, \dots, N-1$ について考えている

といった具合になっています。よって、for 文で扱っている添字 $i, j$ の組として考えられる値は $N \times N = N^{2}$ 通りとなります。

つまり、上記のコードは $N^{2}$ に比例する計算時間を要するということになります。このことを、計算量が $O(N^{2})$ であるといいます。

このように計算時間を $O()$ という記法で表したものを計算量と言います。今後より難しい問題を解いていくためには、計算量について理解を深めていくことが重要です。

なお、コンピュータが 1 秒間に処理できる計算ステップ回数は $10^{9}$ 回程度と言われています。今回の問題では $N \le 250000$ という制約があるため、

$N^{2} \le 62500000000 \simeq 6 \times 10^{10}$

となります。このことから、 $O(N^{2})$ の計算量をもつプログラムは、実行制限時間である 1 秒以内に処理を終えられないことがわかります。

なお、計算量についてより詳しくは次の記事で勉強してみてください。

qiita.com

ステップ 3：探索候補を絞って高速化

そこで、プログラムを高速化しましょう。たとえば、 $A = (3, 5, 6, 9, 11, 15, 17, 21)$ という場合を考えてみます。

このとき、

A[0] = 3 との差が最大の要素は 21 で、差は 21 - 3 = 18
A[1] = 5 との差が最大の要素は 21 で、差は 21 - 5 = 16
A[2] = 6 との差が最大の要素は 21 で、差は 21 - 6 = 15
A[3] = 9 との差が最大の要素は 21 で、差は 21 - 9 = 12
A[4] = 11 との差が最大の要素は 21 で、差は 21 - 11 = 10
A[5] = 15 との差が最大の要素は 3 で、差は 15 - 3 = 12
A[6] = 17 との差が最大の要素は 3 で、差は 17 - 3 = 14
A[7] = 21 との差が最大の要素は 3 で、差は 21 - 3 = 18

というようになっています。気付くことは、A[i] との差が最大になるのは、「A の最大値である 21」と「A の最小値である 3」のどちらかだということです。

このことは一般に言えます。つまり、一般の配列 A に対しても、

ma ← 配列 A の最大値
mi ← 配列 A の最小値

として、A[i] との差の最大値は

max(ma - A[i], A[i] - mi)

と求められます。最初の解法とは異なり、この計算はとても高速に実行できます。

計算量

最後に、この解法の計算量を見積もってみましょう。

ma と mi を求めるのに要する計算量： $O(N)$
各 A[i] に対して、max(ma - A[i], A[i] - mi) を求める計算量： $O(N)$

よって、全体の計算量も $O(N)$ となります。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // A の最小値と最大値を求める
    int mi = A[0], ma = A[0];
    for (int i = 0; i < N; ++i) {
        mi = min(mi, A[i]);
        ma = max(ma, A[i]);
    }

    // 各 i についての問題を解く
    for (int i = 0; i < N; ++i) {
        cout << max(ma - A[i], A[i] - mi) << endl;
    }
}

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

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

JOI 二次予選 2023 A - 年齢の差 (AOJ 0747) (5Q, 難易度 3)

問題概要

制約

解法

ステップ 1：まず 0-indexed にする

ステップ 2：問題の意味を把握する

ステップ 3：探索候補を絞って高速化

計算量

コード