0Pricing
Competitive Programming Academy · レッスン

先にソートすると解決策が見つかる理由

ソート後の貪欲法と Two Pointers の準備を学びます

「先にソートすると解決策が見つかる理由」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

ソートは準備の一手

ソートだけで問題が解けることはほとんどありませんが、ソートによって本当の仕掛けを準備できます。順序を付けることで、無秩序な配列を活用可能な構造に変えられます。

並べ替えで二つのポインタが使える

データをソートすると、二つのポインタを両端から動かせます。合計が指定値になる組を見つける計算量は、O(n の二乗) から O(n) に下がります。

並べ替えで二分探索が可能になる

ソート済みの配列は、二分探索への入り口です。順序が決まっていれば、値や挿入位置を O(log n) で見つけられます。

from bisect import bisect_left
i = bisect_left(sorted_nums, target)

貪欲法にはソートが必要なことが多い

多くの貪欲法の証明では、最小のものや終了時刻が最も早いものを先に選びます。その基準でソートすれば、正しい選択肢をすぐに選べます。

重複を見つけるためにソートする

ソートすると、等しい要素が隣り合って並びます。そのため、追加メモリなしの一回の走査で重複を検出したり数えたりできます。

for i in range(1, len(a)):
    if a[i] == a[i-1]:
        print("dup", a[i])

区間は開始時刻でソートする

区間のマージやスケジューリングは、開始時刻でソートすることから始まります。すると、左から右への走査で重なりをきれいに処理できます。

intervals.sort(key=lambda iv: iv[0])

ソートで中央値が見える

ソート後の中央の要素が中央値であり、隣り合う要素間の差も明確になります。多くの距離に関する問題は、この性質を利用します。

追加コストを見積もる

ソートには O(n log n) のコストがかかりますが、通常はソートによって可能になる処理に比べれば小さいものです。利用する前に、制限時間に収まることを確認してください。

元のインデックスを失わない

ソートすると位置が入れ替わります。答えに元のインデックスが必要な場合は、値とインデックスの組をソートして、元の位置を復元できるようにしてください。

order = sorted(range(n), key=lambda i: a[i])

問うべきこと：並べ替えが役立つか

行き詰まったら、順序を付けると簡単になるか考えてみてください。そうであれば、まずソートすることで、二つのポインタ、貪欲法、二分探索の方針が見えてくることがよくあります。

まずソートを試す

熟練した解法者は、まずソートを基本的な試行として早い段階で試します。追加するコストが小さく、解法全体が見えることも多いからです。

確認

配列をソートしたものの、後から入力中での各要素の位置が必要になったとします。

まとめ

ソートによって、二つのポインタ、二分探索、貪欲法、重複除去、区間の走査が可能になります。コストを見積もり、必要な場合はインデックスを保持してください。🚀

よくある質問

「先にソートすると解決策が見つかる理由」レッスンは無料ですか？

はい。「先にソートすると解決策が見つかる理由」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「先にソートすると解決策が見つかる理由」で何を学びますか？

ソート後の貪欲法と Two Pointers の準備を学びます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「先にソートすると解決策が見つかる理由」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. sorted() と key 関数
  2. 複数のフィールドでソートする
  3. functools.cmp_to_key によるカスタム順序
  4. 先にソートすると解決策が見つかる理由
← Competitive Programming Academyに戻る