ABC377参加記録 by Python

リアルタイムに解けた問題

A - Rearranging ABC

問題文

長さ$3$の英大文字からなる文字列$S$が与えられます。
$S$の各文字を並び替えることで$S$を文字列ABCと一致させることができるか判定してください。

制約

• $S$は英大文字からなる長さ$3$の文字列

アルゴリズム

文字列がABCを含むかをチェックするだけ

ソースコード

S = input()

if 'A' in S and 'B' in S and 'C' in S:
  print('Yes')
else:
  print('No')

B - Avoid Rook Attack

問題文

縦8マス、横8マスの64マスからなるマス目があります。上から$i$行目($1 \leq i \leq 8$)、左から$j$列目($1 \leq j \leq 8$)のマスをマス($i,j$)と呼ぶことにします。

それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。マスの状態は長さ8の文字列からなる長さ8の列($S_{1},S_{2},S_{3},...,S_{8}$)で表されます。マス($i,j$)($1 \leq i \leq 8, 1 \leq j \leq 8$)は、$S_{i}$の$j$文字目が.のとき空マスで、#のときコマが置かれています。

あなたは、既に置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。

マス($i,j$)に置かれているコマは、次のどちらかの条件を満たすコマを取ることができます。

• $i$行目のマスに置かれている
• $j$列目のマスに置かれている

たとえば、マス($4,4$)に置かれているコマは、以下の図（本記事では省略）コマを取ることができます。
あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

• $S_{i}$は.,#からなる長さ8の文字列($1 \leq i \leq 8$)

アルゴリズム

まず行ごとに、#を含むかチェックし、含まれている場合はrow_numを-1する。各行をチェックする中で、列を一つづつ確認し、#であれば、check_colの該当箇所を0にする。
すべての処理が終わったら、row_numとcheck_colの1の個数の積を出力。

ソースコード

S = [list(input()) for _ in range(8)]

row_num = 8

check_col = [1] * 8

for s in S:
  if '#' in s:
    row_num -= 1
    for i in range(8):
      if s[i] == '#':
        if check_col[i] == 1:
          check_col[i] = 0
          
print(row_num * check_col.count(1))

C - Avoid Knight Attack

問題文

縦$N$マス、横$N$マスの$N^{2}$ますからなるマス目があります。上から$i$行目$(1 \leq i \leq N)$、左から$j$列目$(1 \leq j \leq N)$のマスをマス$(i,j)$と呼ぶことにします。

それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。マス目には合計で$M$個のコマが置かれており、$k$番目$(1 \leq k \leq M)$のコマはマス$(a_{k},b_{k})$に置かれています。

あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。

マス$(i,j)$に置かれているコマは、次のどれかの条件を満たすコマを取ることができます。

• マス$(i+2,j+1)$に置かれている
• マス$(i+1,j+2)$に置かれている
• マス$(i-1,j+2)$に置かれている
• マス$(i-2,j+1)$に置かれている
• マス$(i-2,j-1)$に置かれている
• マス$(i-1,j-2)$に置かれている
• マス$(i+1,j-2)$に置かれている
• マス$(i+2,j-1)$に置かれている

ただし、存在しないマスについての条件は常に満たされないものとします。

たとえば、マス$(4,4)$に置かれているコマは、以下の図（この記事では省略）で青く示されたマスに置かれているコマを取ることができます。

あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

• $1 \leq N \leq 10^{9}$
• $1 \leq M \leq 2 * 10^{5}$
• $1 \leq a_{k} \leq N, 1 \leq b_{k} \leq N(1 \leq k \leq M)$
• $(a_{k},b_{k} \neq (a_{l},b_{l})(1 \leq k < l \leq M)$

アルゴリズム

置けない場所を表す変数invalid_positionsを集合で定義。
get_posにコマの移動先を表す配列を格納。
ループを回し、各試行のなかで、get_posをもとにループを回す。
コマの置かれる場所と移動できる場所の座標がinvalid_positionsに格納される。
最後に、マスの総数からinvalid_positionsの個数を引き、その結果を出力。

ソースコード

N, M = map(int, input().split())

invalid_positions = set()

get_pos = [[2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1]]

for _ in range(M):
    i, j = map(int, input().split())
    i -= 1
    j -= 1
    invalid_positions.add((i, j))
    for di, dj in get_pos:
        ni, nj = i + di, j + dj
        if 0 <= ni < N and 0 <= nj < N:
            invalid_positions.add((ni, nj))

result = N * N - len(invalid_positions)
print(result)