AtCoder が提供しているABC（AtCoder Beginner Contest）377 C問題をC++とPythonで解いてみました。ABC377は、2024年10月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Avoid Knight Attack（Difficulty : 274）
問題の詳細は、リンク先をご覧ください。
ABC377 C問題 Avoid Knight Attack
ナイトの移動先をsetコンテナに格納します。AtCoder Problems による Difficulty は 274 でした。
解答案
C++ プログラム例（ABC377C）
B問題と比較すると盤面が大きくなっています。
チェスのナイトは8方向にしか動けません。ナイトがいる場所とすべての移動先を set コンテナに格納して、盤面の大きさから引けば、解答が求まります。
自分自身の場所と8方向の移動先を配列 di と dj に格納しています（12、13行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll n;
int m;
cin >> n >> m;
int di[9] = {0, +2, +1, -1, -2, -2, -1, +1, +2};
int dj[9] = {0, +1, +2, +2, +1, -1, -2, -2, -1};
set<pair<int, int>> s;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
for (int j = 0; j < 9; ++j) {
int ni = a + di[j];
int nj = b + dj[j];
if ((0 <= ni) && (ni < n) && (0 <= nj) && (nj < n)) {
s.insert(make_pair(ni, nj));
}
}
}
cout << n * n - s.size() << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC377C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 377 C"""
n, m = map(int, input().split())
di = [0, +2, +1, -1, -2, -2, -1, +1, +2]
dj = [0, +1, +2, +2, +1, -1, -2, -2, -1]
s = set()
for i in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
for j in range(9):
ni = a + di[j]
nj = b + dj[j]
if 0 <= ni < n and 0 <= nj < n:
s.add((ni, nj))
print(n * n - len(s))こちらも「AC」と判定されました。
最後に
コンテナを使ってうまく書くことができました。
引き続き ABC の問題を紹介していきます。
