0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

atcoder練習(2024.11.27)

Posted at

キーワード

問題

問題文

縦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×10
5
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 マスのみです。
答えが 2
32 以上になる場合があることに注意してください。

入力例 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ぐらいの範囲で間違える。おそらくどこかで数え漏れだったり重複とかを考えている。でもアルゴリズム自体は間違ってない気がする。実行の仕様の問題?
  • ゴリ押しではどうにもならないこともあるということですね。
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?