キーワード
問題
問題文
縦Nマス、横NマスのN**2マスからなるマス目があります。
上からi行目(1≤i≤N)、左からj列目(1≤j≤N)のマスをマス(i,j)と呼ぶことにします。
それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。
マス目には合計でM個のコマが置かれており、k番目(1≤k≤M)のコマはマス(ak,bk)に置かれています。
あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。
マス(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≤N≤109
1≤M≤2×105
1≤ak≤N,1≤bk≤N (1≤k≤M)
(ak,bk)≠(al,bl) (1≤k<l≤M)
入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
a1 b1
a2 b2
⋮
aM bM
出力
すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。
入力例 1
8 6
1 4
2 1
3 8
4 5
5 2
8 3
出力例 1
38
すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。
よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスは残りの 38 マスです。
入力例 2
1000000000 1
1 1
出力例 2
999999999999999997
1018 マスのうち、置くことができないマスはマス (1,1),(2,3),(3,2) の 3 マスのみです。
答えが 232 以上になる場合があることに注意してください。
入力例 3
20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15
出力例 3
338
回答
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
l = []
result = []
for i in ab:
l.append((i[0]+2, i[1]+1))
l.append((i[0]+1, i[1]+2))
l.append((i[0]-1, i[1]+2))
l.append((i[0]-2, i[1]+1))
l.append((i[0]-2, i[1]-1))
l.append((i[0]-1, i[1]-2))
l.append((i[0]+1, i[1]-2))
l.append((i[0]+2, i[1]-1))
def get_unique_list(seq):
seen = []
return [x for x in seq if x not in seen and not seen.append(x)]
l = get_unique_list(l)
for i in l:
if 1 <= i[0] <= n and 1 <= i[1] <= n:
result.append(i)
filtered_result = [x for x in result if x not in ab]
k = get_unique_list(ab + filtered_result)
print(n*n - len(k))
参考
備考
- 供養です。一生懸命考えて書いたのにメモリ超過で不正解でした。もうこれしかわかりません。
- tupleが便利なことに気づきました。
- そもそもサンプルの答えでも+-2ぐらいの範囲で間違える。おそらくどこかで数え漏れだったり重複とかを考えている。でもアルゴリズム自体は間違ってない気がする。実行の仕様の問題?
- ゴリ押しではどうにもならないこともあるということですね。