なんとも言えないテクニックまとめ（1）

本題の前に世界で一番どうでも良い報告

この記事以降、ですます調はやめます。
見ず知らずのあなたに敬語を使うことに疑問を持ってしまいました。
敬語好きの方には申し訳ないですが、悪しからず。

この記事について

「これもう2度と使わないだろ」って手法はだいたいその後3回くらい使うものだ。
ペペロンチーノを作るためだけに買った唐辛子が実は浅漬けにも使えたりするのと同じ話かもしれない。
そんなspecificでありながら案外使えるんじゃね？というコードをジャンル関係なしに載せていく。

選択の組み合わせを二進法と対応付けるやつ

名前がブサイクになってしまうのは仕方の無いことだろう。この手法を用いたのがABC 173のC問題である。

行列のマス目が存在し、各マスは黒か白かに塗られている。
行と列を選び、その行、列に含まれるマスを全て赤で塗るという操作を考える。
操作後に黒色のマスがマス残るような行と列の選び方は何通りあるか。

この問題ではの上限が6と定められているため全ての選び方を試し、条件に合う選び方の個数を求めることができる。
その際に、どの行(または列)を選ぶかを二進法の数と対応させて表現するやり方がある。
具体的にコードを見ながら考える。

H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
ans:=0 

for i in range(2**H): #全ての行の選び方を2進数で列挙
    for j in range(2**W): #全ての列の選び方を2進数で列挙
        black=0
        for k in range(H):
            for l in range(W):
                if ((i >> k) & 1) == 0 and ((j >> l) & 1) == 0 and c[k][l] == '#': 
                    black += 1
        if black == K:
            ans += 1

print(ans)

全てのマスを確認し、操作後の黒のマスの個数がとなる行、列の選び方を数えるコードとなっている。
大事なのは以下の部分である。

i >> k & 1 == 0

j >> l & 1 == 0

上のコードは「の桁目が0である」ことを表している。
Pythonにおける">>"はビット演算子であり、"i >> k"は数(10進数)を2進数で表したものをビット右にずらした数を表す。
さらに"&"も論理積のビット演算子であり、"a&b"は「(10進数)を2進数表示して各桁の論理積を計算し、その結果で表される数の10進数表示」を返す。何を言っているんだ。
具体例を出すと以下の通り。

a=10 #2進数では1010
b=9 #2進数では1001

print(a&b) #出力:8

#"1010"と"1001"の桁ごとに論理積を計算すると"1000"となり、それは10進数で8

このような論理から、上の"i >> k & 1 == 0"というコードは実質的に、「の桁目が0である」ことを表す。
そして、「の桁目が0である」とは、すなわち「行列の行目は選択しない」ことを表すのでその行は赤に塗られない。

以上が「選んだか選んで無いかを2進数に対応させるやつ」でした。
手法のまとめをしたかったが、問題解説のようになってしまった。このシリーズは一つの記事につき一つの手法を扱うことになるのかな。

じゃあ、みなさん暖かくして寝るように。
解散！