初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #3 ( ビット全探索編 )

問題解説 競技プログラミング 精選100問

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今日は第３回目のビット全探索！！

全探索：ビット全探索

全探索：ビット全探索の分野は全部で５問あるので、紹介したいと思います！

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja
最初はビット全探索が全くわからず、とりあえず

for i in range(2**n):
  for j in range(n):
    if (i>>j) & 1:
      #実行したいコードを書いていく

程度しか理解できていませんでした。
その結果悩みながら2時間ほどで書いたコードがこちら〜

n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))
num = []
for i in range(2**n):
    ans = 0
    for j in range(n):
        if (i>>j) & 1:
            ans += a[j]
    num.append(ans)

for i in range(m):
    if b[i] in set(num):
        print("yes")
    else:
        print("no")

上記のコードでもAC出来ますが、フォロワーさんから
「itertoolsを使うと便利！」と教えていただき、勉強しました。

itertoolsの中にあるproductを使用すると、
(product[〇〇], repeat = n)で〇〇をn回並べる順列を作成することができます。
それを用いてAC結果がこちら〜

from itertools import product
n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))
ans = []
for i in list(product([0,1], repeat = n)):
    num = 0
    for j in range(n):
        if i[j] == 1:
            num += a[j]
    ans.append(num)
ans = set(ans)
for i in range(m):
    if b[i] in ans:
        print("yes")
    else:
        print("no")

11. C - Switches

https://atcoder.jp/contests/abc128/tasks/abc128_c

これはまじで難しかった。
以降も３問紹介しますが個人的にはこれが１番難しかったです。
まず問題見て意味が分からなくないですか？自分は読解力が苦手なので理解に苦しみました...

方針としては、productでON, OFFのいずれかを設定し、そのもとでM個の電球を１つずつ試していき条件を満たしていなければFalseにしてBool判定をしていくという感じです。

from itertools import product
n,m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for tpl in product([0,1], repeat = n):
    bl = True
    for i in range(m):
        x = [tpl[j-1] for j in ks[i][1:]]
        x = sum(x)
        if x%2 != p[i]:
            bl = False
    if bl:
        ans += 1
print(ans)

12. D - 派閥

https://atcoder.jp/contests/abc002/tasks/abc002_4

これもかなり手強かったです。部分和をproductで生成した後、知り合いのリストの中に全てのパターンがあるかどうかをallで判定して実装。

もう一度時間がたった時に復習してみます！

from itertools import combinations
n,m = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(m)]
ans = 1
for i in range(n):
    for j in combinations(range(n),i+1):
        if all([x+1, y+1] in xy for x, y in combinations(j,2)):
            ans = i+1
print(ans)

13. E - おせんべい

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e

これは何も見ずに、調べずに解けた問題でした！

行の部分和をproductで生成し、0のときはひっくり返さず、1の時はひっくり返す。
その後、列を１列ずつ見ていき、0の方が多かったらそのまま、1の方が多かったからひっ繰り返すという動作をして、最大値を取る方針で解きました。

計算量はO(RC2^R)です。

AC出来てとても嬉しかったです！！

from itertools import product
r,c = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(r)]
ans = 0
for bit in product([0,1], repeat = r):
    num = 0 # ある部分和に対する全体での０の数をカウント
    for i in range(c):
        cnt = 0 # 列ごとの０の数をカウント
        for j in range(r):
            if bit[j] == 0 and a[j][i] == 0:
                cnt += 1
            elif bit[j] == 1 and a[j][i] == 1:
                cnt += 1
        num += max(cnt, r-cnt)
    ans = max(ans, num)
print(ans)

14. B - Buildings are Colorful!

https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

本日最後の問題です！！
これはビット全探索最後の問題ということもあり、震えながら解いていましたが、無事にAC出来ました！！

方針としては、ビルの高さを変えるか、変えないかをproductで全探索して、変わる場合には最大値を更新して元のビルの高さとの差を出力値に加えるというものです。

これも無事に解けてよかったです！

from itertools import product
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**12
for bit in product([0,1], repeat = n-1):
    cnt = 0 # 高さを更新した時の値
    h = a[0] # その地点での高さの最大値
    view = 0 # 見える数
    for i in range(n-1):
        if bit[i] == 0: # a[i+1]の高さを変更しない
            if h < a[i+1]:
                h = a[i+1]
                view += 1
                cnt += h - a[i+1]
        elif bit[i] == 1: # a[i+1]が１番高くなるように変更する
            if h < a[i+1]:
                h = a[i+1]
                cnt += h - a[i+1]
            else:
                h += 1
                cnt += h - a[i+1]
            view += 1 #絶対に見える
    if view + 1 >= k: # a[0]はいつも見えているので+1する
        ans = min(ans, cnt)
print(ans)

最後に

ビット全探索はかなり苦手意識がありましたが、だいぶ解けるようになった気がします！
毎回質問したら、丁寧に教えてくださっているフォロワーさんには感謝しかないです！！
これからも精進して頑張っていきたいと思います！！
読んで下さってありがとうございました〜〜