ABC377 B - Avoid Rook Attack

はじめに

10/26開催のABC377のB問題の復習です。

問題文の概要

チェスボードのような$8 \times 8$マスの盤上にあらかじめ置かれているルークに取られないようにコマを配置できる場所を出力する。

自分の回答

最近はB問題なら最初に思いついた方法で強引に解くようになりました。
まず最初に閃いたのは、左上からマスを全部ループさせて、縦横ともにルークがいなければ$+1$する。という方法でした。

ABC377_B

m = []
ans = 0
for _ in range(8):
  m.append(input())

ng_i = []
ng_j = []
for i in range(8):
  for j in range(8):
    if m[i][j] == "#":
      ng_i.append(i) # 横のルークの位置を格納
      ng_j.append(j) # 縦のルークの位置を格納

for i in range(8):
  if i in ng_i: # 横にルークが存在する
    continue

  for j in range(8):
    if j in ng_j: # 縦にルークが存在する
      continue
    else:
      ans += 1

print(ans)

さらに考察

コンテストが終わり、
この問題は縦横でルークが存在しない場所を掛ければ答えになると気づきました。

ABC377_B_2

m = []
for _ in range(8):
   m.append(input())

row_with_sharp = [False] * 8
col_with_sharp = [False] * 8

for i in range(8):
   for j in range(8):
       if m[i][j] == "#":
           row_with_sharp[i] = True
           col_with_sharp[j] = True

available_rows = 8 - sum(row_with_sharp)
available_cols = 8 - sum(col_with_sharp)

print(available_rows * available_cols)

最初に思いついた方の計算量は$O(n^4)$。修正版は$O(n^2)$なので速度面でも早いですね。

おわりに

解法がいろいろあって、楽しい問題でした。
後追いでも思いついたものは必ず実装していきたいと思います。