AtCoder が提供しているABC（AtCoder Beginner Contest）275 のC問題をC++とPythonで解いてみました。ABC275は、2022年10月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Counting Squares（Difficulty : 760）
問題はリンク先をご覧ください。
正方形を重複なくカウントする必要があります。AtCoder Problems による Difficulty は、760 でした。ABC275 に限れば、D問題と Difficulty が逆転していました。
解答案
問題を解く方針を書きだします。
- 二次元平面を読む。
- 正方形の左上を見つける（左上の定義は後述）。
- 正方形の右上を全検索で見つける。
- 正方形の左下と右下に ‘#’ があれば、見つけた正方形の数を増やす。
- 見つけた正方形の数を出力する。
問題の入力例1で考えてみましょう。問題文では、座標を1から開始しています。この解説では、座標は0から開始することにします。また座標は (縦, 横) とします。
##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........ここには、二つの正方形があります。
- (0, 0), (0, 1), (1, 0), (1, 1)
- (3, 7), (5, 8), (4, 5), (6, 6)
‘#’ を見つけたら、それを左上と仮定します。その座標を $(i, j)$、$0 \leqq i, j \leqq 8$ とします。それを起点に右上に ‘#’ がないか確認します。探す座標は、以下となります。
$$(i + k, j + m), \;0 \leqq k \leqq 8, \; 1 \leqq m \leqq 8$$
0 以上の k に対して調べていますが、負の値から始めると重複が発生します。この例では、(4, 5) から始めたときに (3, 7) を右上と認識します。その結果、(3, 7) から始めたときに (5, 8) を右上と認識する正方形と重複します。
この問題では、真横もしくは右下がりの辺を上辺とします。この定義であれば、正方形の左上→右上が特定できれば、それは一意となるため重複は発生しません。逆に言えば、上辺が真横もしくは右下がりになるように k と m の範囲を定めています。
残りの2点は、左下 (i + m, j – k) と右下 (i + k + m, j + m – k) となります。左上 (i, j) →左下、右上 (i + k, j + m) →右下 に対して、座標は、(元座標 + m, 元座標 – k) となるからです。
残りは、範囲外のアクセスが発生しないように条件を追加します。
C++ プログラム例（ABC275C）
左上の座標で2重ループ（ループ変数 i, j）を使います。左上を特定してから右上を全検索で探すためさらに2重ループ（ループ変数 k, m）を使います。合わせて4重ループとなりますが、$0 \leqq$ ループ変数 $< 9$ であるため、計算時間は間に合います。
以下が C++ のプログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<string> s(9);
for (int i = 0; i < 9; ++i) {
cin >> s[i];
}
int result = 0;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (s[i][j] == '#') {
for (int k = 0; k < 9; ++k) {
for (int m = 1; m < 9; ++m) {
if ((i + k >= 9)||(j + m >= 9)) {
continue;
}
if (s[i + k][j + m] == '#') {
if ((i + k + m >= 9)
||(j - k < 0)) {
continue;
}
if ((s[i + m][j - k] == '#')
&&(s[i + k + m][j + m - k] == '#')) {
++result;
}
}
}
}
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC275C）
C++ 版を素直に書き換えて、Python 版としました。このため、Python らしい書き方ではないかもしれません。
"""AtCoder Beginner Contest 275 C"""
s = [input() for i in range(9)]
result = 0
for i in range(9):
for j in range(9):
if s[i][j] == "#":
for k in range(9):
for m in range(1, 9):
if i + k >= 9 or j + m >= 9:
continue
if s[i + k][j + m] == "#":
if i + k + m >= 9 or j - k < 0:
continue
if s[i + m][j - k] == "#" and \
s[i + k + m][j + m - k] == "#":
result += 1
print(result)こちらも「AC」と判定されました。
最後に
解法は、以下に分けられるようです。
- 見つけた正方形を set コンテナに登録して重複を除く
- 重複が発生しないようにカウントする
今回は、後者で解きました。問題によっては、set コンテナで重複を取り除くほうがよい場合もあります。自分の傾向（好み）を把握して、問題を解くと、ミスも減ると考えています。
引き続き ABC の問題を紹介していきます。
