粗大メモ置き場

個人用,たまーに来訪者を意識する雑記メモ

Atcoder173反省会(Bit全探索,strからchar変換,etc)

Python使用者です。慣れたらC++の訓練所としても用いたいなぁと思ってます,

Atcoder173所感

atcoder.jp

  • 数え方にまつわる問題が多い?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