ABC129_D(Lamp)

問題

• AtCoder Beginner Contest 129- D

考えたこと

• なので 意外と愚直でいけるかも
• 壁の位置を記録しておいて, 明かりをおく点で二分探索すると壁と壁の間の数がわかる
  • 縦と横、両方やれば 縦 + 横 - 1 がその点の明かりの強さとなる
  • 一度見た明かりと同じ列にいる場合, 既に通っているので計算不要？でも実装が複雑なので一旦保留
• 壁を自前ではやしたほうがわかりやすそうなので, 壁は自前で生やすこととする

実装

import bisect
 
h, w = [int(x) for x in input().split()]
 
maze = list()
 
h_wall = {n: [0, h+1] for n in range(1, w+1)}
w_wall = {n: [0, w+1] for n in range(1, h+1)}
 
# 周りを壁(1)で囲む
for y in range(h+2):
    if y == 0 or y == h+1:
        maze.append([1 for x in range(w+2)])
    else:
        line = [1]
        for x, c in enumerate(input(), 1):
            if c == "#":
                line.append(1)
                bisect.insort(w_wall[y], x)
                bisect.insort(h_wall[x], y)
            else:
                line.append(0)
        line.append(1)
        maze.append(line)
 
max_ans = 0
 
for y in range(1, h+1):
    for x in range(1, w+1):
        if maze[y][x] == 0:
            x_idx = bisect.bisect(w_wall[y], x)
            y_idx = bisect.bisect(h_wall[x], y)
 
            ans = (w_wall[y][x_idx] - w_wall[y][x_idx-1] -1) + \
                (h_wall[x][y_idx] - h_wall[x][y_idx-1] -1) - 1
            max_ans = max(max_ans, ans)
 
print(max_ans)

結果

• Pythonだと TLE
• PyPy3 だと 一応 AC
  • PythonでACしている人は結構トリッキー？な作りをしているように見えるので一旦ここまでで良しとする
  • いずれは numpy の使い方を覚える必要がありそう