Atcoder173反省会(Bit全探索,strからchar変換,etc)
Python使用者です。慣れたらC++の訓練所としても用いたいなぁと思ってます,
Atcoder173所感
- 数え方にまつわる問題が多い?A~Dを解いた。
- C:全探索
- D:中学入試っぽいパズル問題
20分遅れで始めたがギリギリ4問解けた。E,Fが時間内に解ける日は遠そう…
各設問の反省や学習事項
C:Bit全探索
maskを作成してnumpyで行列のAndを*
演算子で取る手法を思いついた。OpenCV脳である。
自分的には初めてBit全探索を行った。正攻法ならitertools
を使うらしい。
Pythonでお手軽にbit全探索を行う方法【itertoolsを使おう!】 | プログラミングの教科書
itertools.product( “候補となるオブジェクトの集合”, “選ぶ回数” )
で書けるため以下のように簡単にできる。
print(list(itertools.product([0,1], repeat=2))) #[(0, 0), (0, 1), (1, 0), (1, 1)]
今回,itertools.product([0,1], repeat=W)
などと書けば簡単にBit演算表が作れていた。
2進数変換を用いたBit全探索
試験中はググる前に自分で書けそうなので自分で書いた。(時間がかかった)
大枠としては以下の通り。
for h in range(2 ** H): for w in range(2 ** W): # 各要素1 or 0 のiteratorリストを作る … #ループさせる関数 …
iterのリストの作り方
hやwが特定の値の時にその値をH桁,W桁の2進数表記リストにしたかった。
hが3,Hが4の時
[0,1,1,1]
のような出力が欲しい。
用いた要素は以下の3つ。
bin()
:2進数表記へ変換する関数。0b~~
のstrで値を出してくる。zfill(n)
:strの先頭をn桁になるまで'0'で埋めてくれる関数- split:
'10010'
みたいなstrを数のリスト[1, 0, 0, 1, 0]
に変換する自作関数
まず,文字列を得るには:
# 7を4桁の2進数にする。binの後ろ二桁を抜き出して桁数に会うように0でfill w0b = bin(7)[2:].zfill(4)
その後,
# splitは予約されていることが多いので関数名は別にするのが良い。 def split(word): return [int(char) for char in word] # we got [0,1,1,1] split(w0b)
余談:Str から Charの変換で沼った
for文で抜き出すか,iterで一個一個読むか? 後で考える。
D
ひらめき問題だったので今のとこ特に書くことなし。
.sort()
は元の関数の順序を変えるので使わない- sortは基本昇順だが
sorted(A, reverse=True)
のように書けば降順になる - 復習:ソートの計算量はNlogN