AGC 033 A - Darker and Darker を python で
最初に言いたい・・・これ難しすぎない？？？？ python がどれだけ遅い言語かを思い知る結果となった・・・
悔しくて悔しくて，リファクタリングをしてやっと通った・・・ （30回出した・・・すまんかった）
考え方や解説をする気はないので，こちらを参照してください．
まず，愚直に実装すると，次の2つ
1つ目はマスを順に黒くしていき，全部のマス目が黒になれば探索は終わるという話
初期の黒から距離1のマスを全部埋めるのを1回目
初期の黒から距離2のマスを全部埋めるのを2回目
・・・
初期の黒から距離nのマスを全部埋めるのをn回目
として，n を出力すればよい
queue を使う必要はないので，list でやってしまった．
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)
cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
next_blacks = []
for black in blacks:
for cand in cands:
i = black[0] + cand[0]
j = black[1] + cand[1]
if i >= 0 and i < H and j >= 0 and j < W:
if L[i][j] == ".":
L[i][j] = "#"
next_blacks.append([i, j])
black_count += len(next_blacks)
blacks = next_blacks
result += 1
print(result)
これだと，4/15AC
2つ目は解説通りに探索すると，こっちかなという感じ
すべてのマス目の黒からの距離を計算し，それの最大値を出す
from collections import deque
H, W = list(map(int, input().split()))
all_count = H * W
L = [input() for i in range(H)]
reached = [[-1]*W for i in range(H)]
q = deque()
for i in range(H):
for j in range(W):
if L[i][j] == "#":
reached[i][j] = 0
q.append((i, j))
cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
i, j = q.popleft()
for ch, cw in cands:
nh, nw = i + ch, j + cw
if nh < 0 or nh >= H or nw < 0 or nw >= W:
continue
if reached[nh][nw] == -1:
reached[nh][nw] = reached[i][j] + 1
q.append((nh, nw))
elif reached[nh][nw] > reached[i][j]:
reached[nh][nw] = reached[i][j] + 1
result = max([max(reached[i]) for i in range(H)])
print(result)
こっちは3/15AC
うん・・・まあ，到底間に合わないのだ・・・ 山ほど試したが，試したことを書くと大変そうなので，抜粋
15/15 AC となったコードと工夫点
- name == "main" の使用
- 代入式の削減と比較式の削減
- 黒マスのカウントの廃止
- for 文の廃止
name == "main" の方が速いのは知られていると思うので，触れない（正確な理由を知らないし）
代入式の削減と比較式の削減について
if reached[nh][nw] == -1: は基本遅い．今回は訪れたかどうかの True or False で十分 reached[nh][nw] = reached[i][j] + 1 も True を代入して終わり
黒マスのカウントの廃止
黒マスをカウントしなくても，重複なしで queue に値をいれてけば，q が空になって自然に終わる
for 文の廃止
最初からこれをやれば良かったのでは？と思うくらい速くなった． for 文で 4方向回すのをやめて地道に書いた．python の for が遅いのは知っていたが，ここまでとは・・・
これらを実装すると
from collections import deque
import copy
def main():
H, W = list(map(int, input().split()))
L = [[j=="#" for j in input()] for i in range(H)]
q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
result = 0
while True:
nq = deque()
while q:
i, j = q.popleft()
if i > 0 and not L[i-1][j]:
L[i-1][j] = True
nq.append((i-1, j))
if j > 0 and not L[i][j-1]:
L[i][j-1] = True
nq.append((i, j-1))
if i < H-1 and not L[i+1][j]:
L[i+1][j] = True
nq.append((i+1, j))
if j < W-1 and not L[i][j+1]:
L[i][j+1] = True
nq.append((i, j+1))
if nq:
q = copy.copy(nq)
else:
break
result += 1
print(result)
if __name__ == "__main__":
main()
13/15 AC となったコードと工夫点
これも結構工夫したので，通らなくてすごい悲しかった・・・
- name == "main" の使用
- 代入式の削減と比較式の削減
- 4方向を見た際の重複の廃止
- 2次元配列がダメかな？と思ったので1次元配列に
各マスに対して4方向見ていくため，見るべき箇所には基本的に重複箇所が生まれる． そこで，見るべき箇所をユニークにして，比較箇所を削減
2次元配列だとメモリ配置の計算で（ちょっとだけだと思うけども）損するかなと思ったので 1次元で処理
これらを実装すると
def main():
H, W = list(map(int, input().split()))
all_count = H * W
L = [j == "#" for i in range(H) for j in input()]
blacks = [i for i in range(all_count) if L[i]]
black_count = len(blacks)
cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
next_steps = [black+cand for black in blacks for cand in cands_H]
next_steps.extend([black-1 for black in blacks if black%W != 0])
next_steps.extend([black+1 for black in blacks if black%W != W-1])
next_steps = set(next_steps)
blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
for i in blacks:
L[i] = True
black_count += len(blacks)
result += 1
print(result)
if __name__ == "__main__":
main()
正直言うと，15/15 よりも 13/15 のコードの方がずっと好きである．
必要なところは内包表記で処理で来ていて，コードの見直しがしやすいし if 文が縦につながるのは嫌いなので． この2つのコードの速度差は 100 ms もないと思われる． （numpy による一斉代入や内包表記での True 代入も試したが，変化せずむしろ落ちたような？） こういう問題が出たら，ちゃんと時間を見て 他の言語で通した方が良いんだろうなあと強く感じた． （ほかの方の回答も結構見たので，numpy の関数で高速化できるらしいというのは見た）
一応，python を主戦場にしつつ，cpp, java はもうちょっと練習してかないと駄目かなあと思った． python や c に比較すると，cpp, java の言語全体のイメージがわからんから書かないんですよね・・・
明日の ABC ? は出たいけど時間をさけそうにないなあ・・・灰色のまんま
