0Pricing
Competitive Programming Academy · レッスン

探索空間を賢く絞り込む

1 つの変数を固定して残りを探索します

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

探索を小さくして答えを保つ

全探索では、あと少しだけ実行時間が足りないことがあります。その場合は、正しい答えを失わずに探索する範囲を縮小します。🙂

1 つの変数を固定する

強力な方法の 1 つは、1 つの変数をループで固定し、残りをより高速に解くことです。全体を一度に探索する代わりに、小さな探索を何度も行います。

N 二乗から N log N へ

最初の要素を固定し、相手の要素を二分探索またはハッシュで探します。これにより、O(n 二乗) の走査を、おおよそ O(n log n) にできます。

for a in arr:
    if (target - a) in seen:
        return True
    seen.add(a)

不可能な分岐を枝刈りする

探索中に、現在の最良解を上回れない経路があれば、そこで早く打ち切ります。探索しない分岐にはコストがかかりません。

ソートして打ち切りを可能にする

最初にソートしておくと、ループを早い段階でbreakできることがよくあります。値がしきい値を超えたら、残りは役に立たないと判断できます。

対称性を利用する

2 つの要素を入れ替えても結果が同じなら、1 つの順序だけを探索します。各ケースを一度だけ数えれば、処理量を半分以下にできることがあります。

ミート・イン・ザ・ミドル

要素を 2 つの半分に分け、それぞれを列挙してから組み合わせます。これにより、2^n の探索を、およそ 2^(n/2) の処理量まで減らせます。

繰り返す処理をキャッシュする

同じ部分問題が再び現れたら、結果を保存して再利用します。メモ化によって、探索中の繰り返しの分岐を丸ごと取り除けます。

分岐する前に上界を求める

各分岐について楽観的な上界を計算します。そこでの最良の場合でさえ負けるなら、その分岐を完全に飛ばして時間を節約します。

正しさを保つ

すべての削減は安全でなければなりません。本当に勝てない経路だけを枝刈りします。単純な全探索と比較して、答えを失っていないことを確認してください。

絞り込んでから探索する

全探索ではあと少しのところで遅い場合に、これらの方法を使います。変数を固定する、枝刈りする、分割することで、探索が制限時間に収まることがよくあります。

確認問題

2^n 個の部分集合をすべて列挙するのは遅すぎますが、要素を 2 つの半分に分けることはできます。

まとめ

変数を固定し、望みのない分岐を枝刈りし、対称性を利用するか、ミート・イン・ザ・ミドルを使って探索を絞り込みます。すべての削減が安全であることを確認してください。🚀

よくある質問

「探索空間を賢く絞り込む」レッスンは無料ですか？

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

「探索空間を賢く絞り込む」で何を学びますか？

1 つの変数を固定して残りを探索します ブラウザで直接実行するハンズオンコードで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. 全探索も有効な戦略
  2. itertools で列挙する
  3. ビットマスクによる部分集合列挙
  4. 探索空間を賢く絞り込む
← Competitive Programming Academyに戻る