トップページ -> AOJの解答例 -> ITP2_11の解答例

ITP2_11の解答例(Python)

ITP2_11に続きビット演算に関する問題です．ビット演算子を使います．以下のサイトでPythonのビット演算子について詳しく説明されています．
【外部サイト】Pythonのビット演算子

1. ITP2_11_A: Enumeration of Subsets I

n番目のフラグが立っているビットとの論理積を考えました．


# ITP2_11_A
# 0からn−1をそれぞれ2進数の00...0001、00...0010、00...0100、...、10...0000とし、存在する要素のビットごとの論理和を取ったものをその部分集合の整数値とします。

n = int(input())

# 0 から n-1 までのフラグのみが立っているビットの集合Sを用意する
S = []
for i in range(n):
    S.append(1<<i)
    
for i in range(2**n):
    print(f"{i}:",end="")
    for j in range(len(S)):
        if S[j] & i: # S[j] は j番目のフラグが立っているビット
            print(f" {j}",end="") # 前に空白を入れる
            
    print() # 改行

2. ITP2_11_B: Bit Operation II

集合の中から与えられた位置のフラグがすべて立っているようなビット列を列挙します． ITP2_10_Dで作ったbit_allと同じ操作でiとTを比べています．


# ITP2_11_B 
n = int(input())

# 0 から n-1 までのフラグのみが立っているビットの集合Sを用意する
S = []
for i in range(n):
    S.append(1<<i)
    
bit_flag = list(map(int,input().split(" ")))[1:]

# フラグの立っている位置が指定されれば整数で管理できる
T = 0
for b in bit_flag:
    T += 2**b

for i in range(2**n):
    if (i & T) == T: # ITP2_10_D でやったbit_allと同じ判定法
        # すべて含まれていた場合は ITP2_11_A と同じ
        print(f"{i}:",end="")
        for j in range(len(S)):
            if S[j] & i: # S[k] は k番目のフラグが立っているビット
                print(f" {j}",end="") # 前に空白を入れる
        print()
            
        continue

ビット列として操作しましたが，どこのビットが立っているのかを一度setに直して把握するやり方が以下です．効率は悪いですがこちらの方が直感的に分かりやすい単純なやり方です．


    # ITP2_11_B 単純にやる場合
# 0からn−1をそれぞれ2進数の00...0001、00...0010、00...0100、...、10...0000とし、存在する要素のビットごとの論理和を取ったものをその部分集合の整数値とします。

n = int(input())

# 0 から n-1 までのフラグのみが立っているビットの集合Sを用意する
S = []
for i in range(n):
    S.append(1<<i)
    
T  = list(map(int,input().split(" ")))[1:]

for i in range(2**n):
    subset = []
    for j in range(len(S)):
        if S[j] & i: # S[j] は j番目のフラグが立っているビット
            subset.append(j)
    
    # 部分集合かどうかを調べる
    if set(T) <= set(subset):
        print(f"{i}:",end="")
        if subset:
            print(" ",end="")
            print(*subset,end="")
        print()

3. ITP2_11_C: Enumeration of Subsets III

集合の中から与えられた位置のフラグのみが立っているようなビット列を列挙します．(すべてが立っている必要はない) ITP2_10_Dで作ったbit_anyと同じ操作でiとTを比べています．Bとは逆の包含関係です．時間制限に引っかかりますが，ビットの考え方に親しみがなく包含関係がイマイチよくわからない場合は以下の書き方を経由すると少し考えが整理できるかもしれません．


# ITP2_11_C 単純にやる場合 これだと時間切れ
# 0からn−1をそれぞれ2進数の00...0001、00...0010、00...0100、...、10...0000とし、存在する要素のビットごとの論理和を取ったものをその部分集合の整数値とします。

n = int(input())

# 0 から n-1 までのフラグのみが立っているビットの集合Sを用意する
S = []
for i in range(n):
    S.append(1<<i)
    
T = list(map(int,input().split(" ")))[1:]

for i in range(2**n):
    subset = []
    for j in range(len(S)):
        if S[j] & i: # S[j] は j番目のフラグが立っているビット
            subset.append(j)
    
    # 部分集合かどうかを調べる 前回と逆の包含関係を調べる
    if set(T) >= set(subset):
        print(f"{i}:",end="")
        if subset:
            print(" ",end="")
            print(*subset,end="")
        print()
        
        if len(subset) == len(T):
            break

ビット列のまま管理する場合


# ITP2_11_C
n = int(input())

# 0 から n-1 までのフラグのみが立っているビットの集合Sを用意する
S = []
for i in range(n):
    S.append(1<<i)
    
bit_flag = list(map(int,input().split(" ")))[1:]

# フラグの立っている位置が指定されれば整数で管理できる
T = 0
for b in bit_flag:
    T += 2**b

for i in range(T+1): # T 以上の数字がTの部分集合になることはない
    # 前回と逆の包含関係を調べるので mask と flag を入れ替える
    if (T & i) == i: # ITP2_10_D でやったbit_allと同じ判定法
        # すべて含まれていた場合は ITP2_11_A と同じ
        print(f"{i}:",end="")
        for j in range(len(S)):
            if S[j] & i: # S[k] は k番目のフラグが立っているビット
                print(f" {j}",end="") # 前に空白を入れる
        print()
            
        continue

4. ITP2_10_D: Bit Mask

Aで求めた部分集合に関して要素の数がkのものだけを列挙する問題です．単純にAと同じように部分集合のリストを作ってから要素の数がkと一致する物だけを出力するようにしました．


# ITP2_11_D
n,m = map(int,input().split(" "))

# 0 から n-1 までのフラグのみが立っているビットの集合Tを用意する
T = []
for i in range(n):
    T.append(1<<i)
    
# Tの部分集合のリストを作る
subsets = []
for i in range(1,2**n):
    subset = []
    for j in range(len(T)):
        if T[j] & i: # T[j] は j番目のフラグが立っているビット
            subset.append(j)
        
    subsets.append(subset)
    
cnt = 1
for subset in subsets:
    # 部分集合の長さがmと一致すれば出力
    if len(subset) == m:
        print(f"{cnt}: ",end="")
        print(*subset)
        
    cnt += 1

<- 前へ戻る【目次に戻る】