AtCoder

ABC275 C問題(Counting Squares)を解く

AtCoder_ABC275_C

AtCoder が提供しているABC(AtCoder Beginner Contest)275 のC問題をC++とPythonで解いてみました。ABC275は、2022年10月29日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Counting Squares(Difficulty : 760)

問題はリンク先をご覧ください。

ABC275 C問題 Counting Squares

正方形を重複なくカウントする必要があります。AtCoder Problems による Difficulty は、760 でした。ABC C問題としては難しいです。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 コンテナで重複を取り除くほうがよい場合もあります。自分の傾向(好み)を把握して、問題を解くと、ミスも減ると考えています。

ABC275 について、引き続き、D問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA