Pythonで競プロに挑む日誌 vol.25 ~Pythonの罠：リスト編~

どうも. こないだ初めて ABC の C 問題を時間内に解けて狂喜乱舞していたのですが, フタを開けてみたらレート下がってました...けどいいんです. 私にとっては大きな一歩でした. めげずに今週の AGC をがんばります.

現在の目標

• 2018年内に茶色になる←イマココ. 現レート 364
• ABC の A, B 問題を全部解く
• 2018年度内に緑色を取得する
• ABC の C 問題を全部解く
• (水色になったら, APG4b で C++ にも手を出す)

今日のおはなし

結論

Python のリストをラクしてつくると痛い目に遭う.

解いた問題

B - Minesweeper

考え方はあってると思うんだけど通らない

1. 入力から四角形の配列を作り, 周囲を "." でパディングする. これを lst と呼ぶ.
2. ↑と同じサイズで, 要素がすべて 0 の配列（リスト）を用意する. これを lst2 と呼ぶ.
3. lst のパディングされてない要素を中心とした 3x3 の窓で探索する. 中心が "." の場合, 周囲 8 マスのうち何個 "#" が含まれるか数える. 数えた "#" の個数を lst2 の同じ場所の要素に割り当てる. 中心が "#" の場合は, lst2 の同じ場所の要素を "#" とする.
4. lst のパディングされてない部分に対して, 3 を繰り返す.

WA.py

# coding: utf-8
H, W = map(int, input().split())

# 一回り大きい並びになるように、"." をパディングする
lst = ["."*(W+2)] + ["." + input() + "." for _ in range(H)] + ["."*(W+2)]
# print(lst)

# lst と同じ形で、要素が全部 0 のリスト
lst2 = [[0]*(W+2)] * (H+2)  # ←この作り方, 要注意

# パディングの内側を3x3の窓で、「. の周囲に # があるか」探索する
for i in range(1, H+1):
    for j in range(1, W+1):
        cnt = 0
        if lst[i][j] == ".":
            cnt += lst[i-1][j-1:j+2].count("#")
            cnt += lst[i][j-1:j+2].count("#")
            cnt += lst[i+1][j-1:j+2].count("#")
            lst2[i][j] = str(cnt)
        else:
            lst2[i][j] = "#"

for i in range(1, H+1):
    print("".join(lst2[i][1:W+1]))

考え方自体は割とすぐ浮かんだのですが, そこからが長かった...2日くらいなんで通らないかわからず悩みました.

lst2 が原因だった

AC.py

# coding: utf-8
H, W = map(int, input().split())

# 一回り大きい並びになるように、"." をパディングする
lst = ["."*(W+2)] + ["." + input() + "." for _ in range(H)] + ["."*(W+2)]
# print(lst)

# lst と同じ形で、要素が全部 0 のリスト(★)
lst2 = []
for _ in range(H+2):
    lst2.append([0 for _ in range(W+2)])

# パディングの内側を3x3の窓で、「. の周囲に # があるか」探索する
for i in range(1, H+1):
    for j in range(1, W+1):
        cnt = 0
        if lst[i][j] == ".":
            cnt += lst[i-1][j-1:j+2].count("#")
            cnt += lst[i][j-1:j+2].count("#")
            cnt += lst[i+1][j-1:j+2].count("#")
            lst2[i][j] = str(cnt)
        else:
            lst2[i][j] = "#"

for i in range(1, H+1):
    print("".join(lst2[i][1:W+1]))

http://delta114514.hatenablog.jp/entry/2018/01/02/233002 に書いてある通り, 単純な掛け算でリストを作成すると, どこか一つの要素に変更を加えると, ほかの要素もすべて同じ変更が反映されてしまうとのことでした.

この方法で作ったリストは, 各要素が各々独立したデータではないんですね. リストの各要素が一か所のデータを参照しているだけなので, リストの要素をいじると参照先が変わってしまう, ということのようです. 有名な話らしいし, Python あるあるのようですが, 知れてよかったです.

むすび

ハマって初めて知る罠が, そこにはある