水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ABC096 C - Grid Repainting 2

問題

C: Grid Repainting 2 - AtCoder Beginner Contest 096 | AtCoder

読解

パッと見全探索か、シミュレーションで制約見てもせいぜいO(HW)で、H, Wともに小さいのでそこまで工夫せず全探索でいいなーと判断。

テーブルみたいな問題はx, yの方向を間違えがちなので、ミスをしないように意識する。

方針

実は解説と違う解放だったらしい。

実際に塗ってみて結果をシミュレーションする。 全て . のテーブルを入力と別に持って、入力されたテーブルで # が見つかれば、上下左右見て上下左右に # があれば別に持ったテーブルに # を書き込む。

そして書き込みテーブル結果と入力データが等しいかどうか見て、Yes、Noを判断する。

ポイントとしてはmx, my を使ってif文を書き連ねないことですかね…。自分が技術書典で出したコードを見返していて、これ積極的に使わないとなーと思ったことの1つです(ifネストとか、ifが無数に増えるとかWA出したときにコードが追えなくなるので大変、3分前にコード書いていた自分はすでに別人なのだ…、解釈時間が必要なのは惜しい)

競技では可読性うんぬんの話がされますが、ガチガチに意識しないでいいとはいえ、自分があとから見返してCOOLだったなこれ(早く書けたとか、気付きによって美しくまとめられたとか)とか思えないのも捗らないかなーと思うので、コンテスト中ないしコンテストが終わったあともコードを見返して成長を実感していきたいなと思います。

コード

Submission #2469355 - AtCoder Beginner Contest 096 | AtCoder

h, w = map(int, input().split())
table = [list(input()) for _ in range(h)]
visited = [["." for _ in range(w)] for _ in range(h)]

mx = [0, 1, 0, -1]
my = [1, 0, -1, 0]
for i in range(h):
  for  j in range(w):
    if table[i][j] == "#":
      for k in range(4):
        tx, ty = j + mx[k], i + my[k]
        if 0 <= tx < w and 0 <= ty < h and table[ty][tx] == "#":
          visited[i][j] = visited[ty][tx] = "#"

for i in range(h):
  for  j in range(w):
    if table[i][j] != visited[i][j]:
      print("No")
      exit(0)
print("Yes")

解説どおりのコード

実はシミュレーションしなくても良かった。ほぼ変えなくて済んだので、一応書いて出しておいた。(ブログにはコード略)

Submission #2474624 - AtCoder Beginner Contest 096 | AtCoder

余談

一瞬、探索系かなーと思ったけど、そう複雑に考えなくても解けるなーと気づいて考え直せたのは良かったかな。

元々解説書く気はなかったのですが、解けなかった人もいるらしいので一応書いておきました。