0Pricing
Competitive Programming Academy · レッスン

Meet in the Middle

探索を分割して指数を半分にします

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

全探索では遅すぎる場合

Nが40前後になる問題では、2^N個の部分集合をすべて試すのは現実的ではありません。ミート・イン・ザ・ミドルを使えば、この規模の問題を解決できます。🤝

基本となる考え方

入力を2つの半分に分けます。それぞれを全探索で解き、2つの部分的な結果を巧みに組み合わせます。

指数を半分にする

サイズN/2の半分を2つ処理するコストは、それぞれ2^(N/2)であり、全体を2^Nで処理するより小さくなります。この平方根規模の削減により、2^40を扱いやすい2^20にできます。

典型例：部分和問題

いくつかの部分集合の和が目標値Tになるかを判定します。Nが40前後の部分和問題は、ミート・イン・ザ・ミドルの教科書的な問題です。

左半分を列挙する

左半分のすべての部分集合の和を列挙して保存します。N/2個の要素なら、和の個数は2^(N/2)個だけです。

from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []

右半分を列挙する

右半分についても同じ処理を行い、すべての部分集合の和を列挙します。これで扱いやすいリストが2つできます。

検索で組み合わせる

右側の各和rについて、T - rと等しい左側の和を探します。集合やソート済みリストを使えば、この確認を高速に行えます。

need = T - r
found = need in left_set

マッチングの2つの方法

完全一致する目標値にはハッシュセットを使います。個数を数えたり最も近い和を探したりする場合は、片方をソートして二分探索します。

計算時間

全体の計算量は、およそ2^(N/2)に、検索またはソートのための対数係数を掛けたものです。この計算量だからこそ、Nが40前後でも処理できます。

メモリとのトレードオフ

片方の半分を丸ごと保存するため、メモリ使用量は2^(N/2)まで増えます。制限内に収めるため、必要なものだけを保存してください。

ほかに活躍する場面

部分和問題以外にも、上限付きの部分集合の最大化、ペアの個数え上げ、離散対数風の問題に使えます。きれいに分割できる問題で力を発揮します。

確認

N個の要素を持つ部分集合問題にミート・イン・ザ・ミドルを適用します。おおよその計算時間はどれくらいでしょうか。

まとめ

2つの半分に分け、それぞれを全探索してから、左側と右側の和を組み合わせます。少しのメモリを使う代わりに、大幅な高速化を得られました。🚀

よくある質問

「Meet in the Middle」レッスンは無料ですか？

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

「Meet in the Middle」で何を学びますか？

探索を分割して指数を半分にします ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「Meet in the Middle」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. ゲームの勝ち状態と負け状態
  2. Nim と Grundy 数
  3. Meet in the Middle
  4. 高速デバッグ: ストレステストと切り分け
← Competitive Programming Academyに戻る