0Pricing
Competitive Programming Academy · レッスン

小さな集合としてのビットマスク

部分集合を整数で表現します

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

整数を集合として使う

1つの整数で集合全体を表せます。ビットiが1なら要素iが含まれるという意味です。これにより、部分集合を小さく高速な1つの値にまとめられます。🎒

空集合と全集合

数値0は空集合を表し、最下位のnビットがすべてオンの値は、すべての要素が存在することを表します。

empty = 0
full = (1 << 4) - 1  # 0b1111, four elements

要素を追加する

要素iを集合に追加するには、そのビットをORで加えます。これはビットをセットする操作とまったく同じで、1つの要素との和集合として解釈できます。

s = 0
s |= (1 << 2)  # add element 2

要素を削除する

要素iを削除するには、反転したビットとのANDを取ります。その要素だけが集合から削除され、他の要素はそのまま残ります。これは1つの要素との差を取る差集合の操作です。

s &= ~(1 << 2)  # remove element 2

所属を確認する

要素iのビットとANDを取ることで、その要素が含まれているか確認できます。結果が0以外なら、その要素は集合のメンバーです。

if s & (1 << 2):
    print('2 is in the set')

和集合と共通部分

2つのマスクをORすると和集合になり、ANDすると共通部分になります。集合全体の操作を、それぞれ1つの機械命令で実行できます。

union = a | b
inter = a & b

集合の大きさはポップカウント

ビットマスクの要素数は、セットビットの数そのものです。bit_countを使えば、サイズをすぐに取得できます。

size = mask.bit_count()

すべての部分集合をループする

n個の要素について、0から2のn乗-1までの整数を使うと、すべての部分集合を列挙できます。1つの単純なrangeループですべてを扱えます。

for mask in range(1 << n):
    pass  # mask is one subset

部分マスクを高速に走査する

指定したマスクの部分集合だけを訪れるには、定番のsubmaskループを使います。各部分集合を降順にたどれます。

sub = mask
while sub:
    sub = (sub - 1) & mask

ここでビットマスクDPを使う

ビットマスクは多くのDP問題で状態を表します。たとえば巡回セールスマン問題では、訪問済みのノードをマスクで管理します。

nを小さく保つ

部分集合が2のn乗個あるため、この方法が実用的なのは通常20程度までの小さなnに限られます。それを超えると個数が急増します。⚠️

確認問題

最後に、集合をマスクで表す方法についての問題です。

復習: ビットマスク集合

集合を1つの整数に格納し、マスクで要素を追加・削除し、すべての部分集合をループできます。これにより、高速なビットマスクDPが可能になります。🎉

よくある質問

「小さな集合としてのビットマスク」レッスンは無料ですか？

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

「小さな集合としてのビットマスク」で何を学びますか？

部分集合を整数で表現します ブラウザで直接実行するハンズオンコードで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. AND、OR、XOR、シフト
  2. ビットの Set、Clear、Toggle
  3. ビット数と最下位の Set Bit
  4. 小さな集合としてのビットマスク
← Competitive Programming Academyに戻る