問題

個人的にEDPCの壁。やり直すたび、毎回O問題で挫折するんですよね。

既存投稿一覧ページへのリンク

一覧ページ

現在のマスクと位置を受け取り、新しいマスクを返す

sample.py

def update_mask(current_mask, position):
    input(current_mask)
    return current_mask | (1 << position)

if __name__=="__main__":
    # テストケース
    assert update_mask(0b0000, 2) == 0b0100 # 0000 | 0100
    assert update_mask(0b0101, 3) == 0b1101 # 0101 | 1000
    assert update_mask(0b1111, 0) == 0b1111 # 1111 | 0000

1行分の相性データから可能なマッチング位置

sample.py

def calculate_row_matches(row):
    return sum(1 for x in row if x == 1)

if __name__=="__main__":
    # テストケース
    test_row1 = [1, 0, -1, 1]
    test_row2 = [0, 0, 0]
    test_row3 = [1, 1, 1, 2, 0]

    assert calculate_row_matches(test_row1) == 2
    assert calculate_row_matches(test_row2) == 0
    assert calculate_row_matches(test_row3) == 3

相性行列から可能な完全マッチング数

sample.py

# compatibility: 相性を表すn×nの2次元リスト（1なら相性が良い、0なら相性が悪い）
def calculate_matches(compatibility):
    n = len(compatibility)  # nは人数（相性リストのサイズ）
    dp = [0] * (1 << n)  # dp配列を初期化。サイズは2^n（全ての組み合わせを表現するため）
    dp[0] = 1  # 初期状態では誰もペアリングされていない状態を1通りとする
    
    # iは現在ペアリングしようとしている人
    for i in range(n):  
         # 新しいdp配列を初期化（次のステップ用）
        new_dp = [0] * (1 << n) 
        # maskは現在のペアリング状態をビットで表現
        for mask in range(1 << n):  
            # 現在のペアリング状態が不可能ならスキップ
            if not dp[mask]:  
                continue
            # jはi番目の人とペアリングする候補
            for j in range(n):  
                # iとjが相性が良く、jがまだペアリングされていない場合
                if compatibility[i][j] and not (mask & (1 << j)):  
                    # 現在のペアリング状態(mask)を(1<<j)によってペアリング状態に変更
                    new_mask = mask | (1 << j)  
                    # 新しいペアリング状態に現在のペアリングの数を加算
                    new_dp[new_mask] += dp[mask]  
        dp = new_dp  # dpを更新して次のステップに進む
    return dp[-1]  # 全員がペアリングされた状態（maskが全ビット1）の通り数を返す

if __name__=="__main__":
    # テストケース
    test_matrix = [
        [1, 1, 0],
        [1, 1, 1],
        [0, 1, 1]
    ]
    assert calculate_matches(test_matrix) == 3
    # [(0, 1), (1, 0), (2, 2)], [(0, 0), (1, 2), (2, 1)], [(0, 0), (1, 1), (2, 2)]の3つ

雑記.1

2025年2月17日時点、理解がふわっとしているので、要復習
2023年10月にノートにめちゃくちゃ書き込みしながら理解できるようになっていたんだけどなァ・・・

ビット演算を利用して効率的に部分集合を生成

sample.py

def enumerate_subsets(n):
    # ヘッダーを出力
    print("マスク\t部分集合")
    # 0から2^n-1までの数をイテレート
    for mask in range(1 << n):
        # 現在の部分集合を格納するリストを初期化
        subset = []
        # 各ビット位置をチェック
        for i in range(n):
            # マスクの i 番目のビットが1かどうかをチェック
            if mask & (1 << i):
                # ビットが1なら、その位置の要素を部分集合に追加
                subset.append(i)
        # 現在のマスクと対応する部分集合を出力
        print(f"{bin(mask)[2:]:>{n}} : {subset}")

if __name__=="__main__":
    enumerate_subsets(3)

ビットカウント関数

sample.py

# ビットカウント関数
def bit_count(mask):
    count = 0  # カウンタを初期化
    while mask:  # maskが0になるまでループ
        count += mask & 1  # 最下位ビットが1なら、カウントを増やす
        mask >>= 1  # maskを右に1ビットシフト
    return count  # 1のビット数を返す

# ビットカウント関数のテスト
def test_bit_count():
    test_cases = [0b1010, 0b1111, 0b0000, 0b1000001]  # テストケースを定義
    for mask in test_cases:  # 各テストケースに対してループ
        print(f"{bin(mask)}: {bit_count(mask)}ビット")  # 結果を出力

# メイン実行部
if __name__=="__main__":
    test_bit_count()  # テスト関数を実行