ソートで順序を作る
並べ替えると「近い値」「小さい順」が見えるようになります。元の順序が意味を持つ問題では保存しましょう。
言語：Python / 計算量：O(N log N)
考え方
- sorted(a) は新しいリストを返します。
- a.sort() は a 自体を並べ替えます。
- 同じ値が複数ある場合、何番目の要素かと何種類目かは別です。
具体例
[7,2,5] → [2,5,7]。隣同士の差は3と2。最小の差は2です。
実装
a = sorted([7, 2, 5])
print(min(a[i+1] - a[i] for i in range(len(a)-1)))注意する条件
a = a.sort() と書くと a は None になります。
確認問題
[9,1,5] を昇順にした中央の値は？
解答と理由
5
並べると [1,5,9] です。
実装課題
N と N 個の整数 A が2行。異なる添字の2要素の差の絶対値の最小値。2 ≤ N ≤ 200000、|A_i| ≤ 10^9。
入力:
3
7 2 5
出力:
2参考実装
n = int(input())
a = sorted(map(int, input().split()))
print(min(a[i+1] - a[i] for i in range(n-1)))実戦につなげる補講
一度に全て読まなくて大丈夫です。今日は1節と1問から。
順序を変えてよいか、先に確認する
位置関係が答えに必要なら、無条件にソートしてはいけません。元の時刻順・隣接関係・部分列などを壊す場合があります。順序が不要か、添字を一緒に持てば復元できるかを考えます。
並べ替えは「以降を見る必要がない」を作る
昇順なら、しきい値未満と以上が連続した領域になります。これは二分探索の入口です。最も差が小さい2要素も、同じ列ならソート後の隣り合う要素を調べれば足ります。間に要素がある2点より、途中の隣接差のどれかが大きくなることはありません。
ソート代を忘れない
ソート後の走査がO(N)でも、全体にはソートのO(N log N)が含まれます。a.sort()は元の列を変更し、sorted(a)は新しい列を作ります。Pythonのソートも作業領域を使うので、追加メモリが常にO(1)とは考えません。
段階式の追加演習
1. 使えない条件
入力された順番で隣り合う2人の年齢差を求めたい。年齢順にソートしてよい？
ヒント
「隣」の意味が変わらないか。
解答と理由
不可。入力順の隣接関係が問題の条件なので、ソートすると別の問いになる。
2. 実装：一番近い2値
要素数2以上の整数列aから、異なる添字の2値の差の絶対値の最小を返すnearestを書いて。a=[18,3,12,13]なら1。
ヒント
ソート後の隣接差を調べる。
解答と理由
O(N log N)で並べ、N−1箇所だけ比較する。値が重複していれば0。
def nearest(a):
b = sorted(a)
return min(b[i + 1] - b[i] for i in range(len(b) - 1))3. 1つの列と2つの列の違い
2つの列から1つずつ選ぶとき、両列を混ぜて単純に最小の隣接差を取ってよい？
ヒント
同じ列の要素同士が選ばれていないか。
解答と理由
不可。所属する列のラベルを保持して異なる列同士に限定するなど、元の条件を守る必要がある。
4. 計算量を合算
長さNの列を1回ソートし、その後Q回二分探索する。全体の計算量は？
ヒント
前処理と質問を別々に数える。
解答と理由
O(N log N+Q log N)。質問のたびにソートするとO(QN log N)になってしまう。
公式過去問への橋渡し
ABC212 C / 公式解説
2つの列から選ぶ全組合せは最大400億組。ソート後に比較対象を減らす判断を練習する。
公式問題 / 公式解説見本を閉じて確認
- 何を繰り返しているかを説明できる
- 使える条件と使えない条件を1つずつ言える
- 見本を閉じて実装し、小さい入力で確かめられる