コンテンツにスキップ

ABC482 B - Blank Bingo

サイト
AtCoder
コンテスト
ABC482
問題
B - Blank Bingo
難易度
65

5×55 \times 5 のマス目があり、いくつかのマスに印が付いています(o が印あり、. が印なし)。縦・横・斜めのいずれか一列の 55 マスすべてに印が付いた状態(ビンゴ)にするために、追加で付ける印の個数の最小値を求める問題です。

ある一列でビンゴにするには、その列で印が付いていないマスすべてに印を付ける必要があり、それで十分です。なので、各列について . の個数を数え、その最小値が答えです。

調べる列は、横 55 本・縦 55 本・斜め 22 本の計 1212 本です。

Python
S = [input() for i in range(5)]
l = S.copy()
for i in range(5):
l.append("".join(S[j][i] for j in range(5)))
l.append("".join(S[j][j] for j in range(5)))
l.append("".join(S[j][4 - j] for j in range(5)))
print(min(i.count(".") for i in l))

l に 1212 本の列を文字列として集めています。横の列は SiS_i そのもの、縦の列は各行の ii 文字目をつなげたもの、斜めの列は (j,j)(j, j) と (j,4−j)(j, 4 - j) のマスをつなげたものです(0 始まり)。