ABC249 C - Just K
キーワード
ビット全探索
ビット演算
シフト演算
キーワードについて解説していきます
シフト演算
見やすさ重視でバイナリ表記で出力していますが、下記コードは右シフトの演算です
例：0010 >> 0001 = 00001, 1000 >> 0010 = 0010
演算子の右側にある１が見えなくなるまでずらしていき、
同じ分だけ、左側もずらされる
for i in range(1,4): for j in range(3): print(bin(i>>j)) >>> 0b1 # 0b1 >> 0b0 0b0 # 0b1 >> 0b1 0b0 # 0b1 >> 0b10 0b10 # 0b10 >> 0b0 0b1 # 0b10 >> 0b1 0b0 # 0b10 >> 0b10 0b11 # 0b11 >> 0b0 0b1 # 0b11 >> 0b1 0b0 # 0b11 >> 0b10
ビット演算 ( &のみ )
&演算子は、お互い１の時のみ１を返します
例：0001 & 0001 = 0001, 1010 & 1010 = 1010, 0101 & 1001 = 0001
※ and（論理演算子）で＆（ビット演算子）となり別物
print(bin(7&3)) # 0b111 & 0b11 >>> 0b11
ビット全探索
３つのうち、２パターンの合計は2＾3(1<<3) = 8通り
２パターンとはバイナリの０と１、つまり選ぶ( 1 )か選ばない( 0 )か
これを使って、Ｎ個の文字列から好きな個数を選択するための全通りが行える
for i in range(1<<3): for j in range(3): print(bin(i>>j & 1)) >>> 0b0 0b0 0b0 0b1 0b0 0b0 0b0 0b1 0b0 0b1 0b1 0b0 0b0 0b0 0b1 0b1 0b0 0b1 0b0 0b1 0b1 0b1 0b1 0b1
解答
キーワードに関する説明は省くとして、
アルファベットの配列(a = 0 を起点とする,)に、選択した文字列に含まれる単語をカウントしていく
配列の要素つまりカウント数が==Kとなっている数が一番多い時をansに記憶しておく
N, K = map(int, input().split()) S = [input() for _ in range(N)] ans = 0 for i in range(1<<N): alph = [0]*26 cnt = 0 for j in range(N): if i>>j & 1: for k in S[j]: alph[ord(k)-ord('a')] += 1 for j in range(26): if alph[j] == K: cnt += 1 ans = max(ans, cnt) print(ans)
参考
bit 全探索 - けんちょんの競プロ精進記録
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita
