AtCoder が提供しているABC（AtCoder Beginner Contest）269 のD問題をC++とPythonで解いてみました。ABC269は、2022年9月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Do use hexagon grid（Difficulty : 612）
問題はリンク先をご覧ください。
ABC269 D問題 Do use hexagon grid
連結している島の個数をカウントする問題です。いろいろな解き方がありますが、DFS（深さ優先探索:Depth-First-Search）を使います。AtCoder Problems による Difficulty は、612 でした。
解答案
問題を解く方針を書きだします。
- マス全体を表現できる２次元配列を用意して、値 ０ で初期化する。
- 黒く塗るマスに対して、該当する２次元配列の要素を １ にする。
- ２次元配列の要素について
- 値 ０ なら、次の要素を調べる。
- 値 １ なら、連結成分の個数を増やして、その要素の値を ０ にする。そのマスの近傍を調べて値 １ なら、再帰的にこの操作を繰り返す。
- 連結成分の個数を解答として出力する。
赤字で記した処理は、再帰的に該当するだけ調べて、該当しなくなったら戻る操作となります。これを深さ優先探索（Depth-First Search）と呼びます。DFS と記す場合もあります。
プログラム例を見た方が、分かりやすいかもしれません。以下は、C++ のプログラム例です。マス全体は、$-1000 \leqq x \leqq 1000$ と $-1000 \leqq y \leqq 1000$ で表現できますが、配列は 0 から始まるため、添え字に 1000 を加えています。
C++ プログラム例（ABC269D）
#include <bits/stdc++.h>
using namespace std;
#define OFFSET 1000
#define MAX_INDEX (OFFSET * 2 + 1)
int f[MAX_INDEX][MAX_INDEX];
int diff_x[6] = {-1, -1, 0, 0, 1, 1};
int diff_y[6] = {-1, 0, -1, 1, 0, 1};
void dfs(int x, int y)
{
f[x][y] = 0;
for (int i = 0; i < 6; ++i) {
if (((0 <= diff_x[i] + x)&&(diff_x[i] + x < MAX_INDEX))
&& ((0 <= diff_y[i] + y)&&(diff_y[i] + y < MAX_INDEX))
&& ((f[diff_x[i] + x][diff_y[i] + y] == 1))) {
dfs(diff_x[i] + x, diff_y[i] + y);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
f[x + OFFSET][y + OFFSET] = 1;
}
int result = 0;
for (int x = 0; x < MAX_INDEX; ++x) {
for (int y = 0; y < MAX_INDEX; ++y) {
if (f[x][y] == 1) {
++result;
dfs(x, y);
}
}
}
cout << result << endl;
return 0;
}六角形のマスの近傍を表現するために、diff_x と diff_y という差分を表現する配列を用意しました。配列の外にアクセスしないように上下限チェックしている条件文の式は長いですが、本質的には、f[diff_x[i] + x][diff_y[i] + y] の値が 1 であるマスに対して、再帰的に関数 dfs を呼び出しています。dfs は連結しているマスをすべて 0 に変更して、呼び出し元に戻ります。
再帰を使うアルゴリズムは、難しく感じる方も少なくないと思います。プログラムを読みながら、なんども頭の中で動かすと、慣れてくると思います。
AtCoder は、問題ページから解答プログラムを提出できます。このプログラムは、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC269D）
Python でも書いてみました。基本的には、C++ をそのまま Python に落とし込みました。まず、以下を試してみましょう。
"""AtCoder Beginner Contest 269 D"""
OFFSET = 1000
MAX_INDEX = OFFSET * 2 + 1
f = [[0 for j in range(MAX_INDEX)] for i in range(MAX_INDEX)]
diff_x = [-1, -1, 0, 0, 1, 1]
diff_y = [-1, 0, -1, 1, 0, 1]
def dfs(x, y):
f[x][y] = 0
for i in range(6):
if 0 <= diff_x[i] + x and diff_x[i] + x < MAX_INDEX and \
0 <= diff_y[i] + y and diff_y[i] + y < MAX_INDEX and \
f[diff_x[i] + x][diff_y[i] + y] == 1:
dfs(diff_x[i] + x, diff_y[i] + y)
n = int(input())
for i in range(n):
x, y = map(int, input().split())
f[x + OFFSET][y + OFFSET] = 1
result = 0
for x in range(MAX_INDEX):
for y in range(MAX_INDEX):
if f[x][y] == 1:
result += 1
dfs(x, y)
print(result)C++ と比較すると、採点に時間がかかっていることが分かります。残念ながら AtCoder が用意した67のテストケースに対して、2つのテストケースに対して、RE（Runtime Error）と判定されてしまいました。なお、言語を「Python(3.8.2)」ではなく「PyPy3(7.3.0)」に設定すると、このプログラムでも、「AC」判定がでます。
なぜ、このプログラムはRE判定になったのでしょうか。Python3 は、関数の再帰呼び出しの回数の上限を設定しています。一般的には、1000 が設定されている環境が多いようです。
この問題のマス全体の大きさは、2001 × 2001 の大きさがあるため、連結しているマスが大きいと関数の再帰呼び出しの回数は、1000を超える場合があります。RE 判定を受けたテストケースはこのような場合だと考えられます。
次の Python プログラムは、関数の再帰呼び出し回数の上限を増やしました（2行目と4行目の処理です）。
"""AtCoder Beginner Contest 269 D"""
import sys
sys.setrecursionlimit(10000)
OFFSET = 1000
MAX_INDEX = OFFSET * 2 + 1
f = [[0 for j in range(MAX_INDEX)] for i in range(MAX_INDEX)]
diff_x = [-1, -1, 0, 0, 1, 1]
diff_y = [-1, 0, -1, 1, 0, 1]
def dfs(x, y):
f[x][y] = 0
for i in range(6):
if 0 <= diff_x[i] + x and diff_x[i] + x < MAX_INDEX and \
0 <= diff_y[i] + y and diff_y[i] + y < MAX_INDEX and \
f[diff_x[i] + x][diff_y[i] + y] == 1:
dfs(diff_x[i] + x, diff_y[i] + y)
n = int(input())
for i in range(n):
x, y = map(int, input().split())
f[x + OFFSET][y + OFFSET] = 1
result = 0
for x in range(MAX_INDEX):
for y in range(MAX_INDEX):
if f[x][y] == 1:
result += 1
dfs(x, y)
print(result)このプログラムは、言語を「Python(3.8.2)」もしくは「PyPy3(7.3.0)」として実行して「AC」と判定されました。
言語による実行時間は以下となりました。実行時間は多少ばらつきます。
| 言語 | 実行時間 |
| C++(GCC 9.2.1) | 19ms |
| Python(3.8.2) | 642ms |
| PyPy3(7.3.0) | 152ms |
競技プログラミングでは、実行時間で有利なため、C++ を選ぶ人が多いようです。AtCoder で、Python を使う人は、言語として PyPy を選ぶ人が多いようです。
最後に
ABC の A問題からC問題については紹介していく予定でしたが、D問題でも典型的な問題は紹介していきます。私の経験ですが、島の数をカウントする問題は、DFS を理解するきっかけになりました。
ただし、D問題は、C問題と比較してかなり難しくなる印象です。その人なりに理解できる範囲でコンテストを楽しめばよいと考えています。
引き続き ABC の問題を紹介していきます。
