AtCoder が提供しているABC（AtCoder Beginner Contest）305 のC問題をC++とPythonで解いてみました。ABC305は、2023年6月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Snuke the Cookie Picker（Difficulty : 159）
問題はリンク先をご覧ください。
ABC305 C問題 Snuke the Cookie Picker
文字列から長方形を特定して、条件を満たす座標を探します。AtCoder Problems による Difficulty は 159 でした。
解答案
まず、長方形を特定します。’#’ がある座標の行の最小値を $a$、最大値を $b$ とします。列の最小値を $c$、最大値を $d$ とします。これにより長方形が決まります。
行（$a \leqq i \leqq b$）と列（$c \leqq j \leqq d$）の範囲で、文字が ‘#’ でない座標が一つだけあるはずです。この座標が回答となります。
ABC269B問題（Difficulty 68）は、この前半部分に相当する問題でした。
C++ プログラム例（ABC305C）
上記の手順をそのまま実装します。配列の添え字は0からカウントしますが、問題のマスの座標は1からカウントしているため注意が必要です（34、35行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
int a, b, c, d;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
a = h + 1;
b = -1;
c = w + 1;
d = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
a = min(i, a);
b = max(i, b);
c = min(j, c);
d = max(j, d);
}
}
}
int result_h, result_w;
for (int i = a; i <= b; ++i) {
for (int j = c; j <= d; ++j) {
if (s[i][j] != '#') {
result_h = i + 1;
result_w = j + 1;
}
}
}
cout << result_h << " " << result_w << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC305C）
同じロジックですが、Python は複数の変数に複数の値を代入することができるため、全体的にすっきりと書けています（5、6、10、11行目）。回答もタプルとして代入しました（16行目）。
"""AtCoder Beginner Contest 305 C"""
h, w = map(int, input().split())
s = [input() for i in range(h)]
a, b = h + 1, -1
c, d = w + 1, -1
for i in range(h):
for j in range(w):
if s[i][j] == '#':
a, b = min(i, a), max(i, b)
c, d = min(j, c), max(j, d)
for i in range(a, b + 1):
for j in range(c, d + 1):
if s[i][j] != '#':
result = (i + 1, j + 1)
print(*result)こちらも「AC」と判定されました。
最後に
このような問題は、特定のアルゴリズムは必要ありません。一方、頭の中を整理しない状態でプログラムを書いても、かえって時間がかかるかもしれません。2つの段階を明確に分けることも間違えにくい工夫だと考えています。
引き続き ABC の問題を紹介していきます。
