ABC307 C問題（Ideal Sheet）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）307 のC問題をC++で解いてみました。ABC307は、2023年6月24日21:00に実施されました。

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

C問題 Ideal Sheet（Difficulty : 1307）
解答案
- C++ プログラム例（ABC307C）
最後に

C問題 Ideal Sheet（Difficulty : 1307）

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

ABC307 C問題 Ideal Sheet

実装が非常に重たい問題でした。AtCoder Problems による Difficulty は 1307 でした。

解答案

シート A、B、X は大きくても 10×10 です。そのため全探索で間に合います。何を固定して、何を動かすかの方針を明確にします。

大きく分けて2つの考え方のプログラムを紹介します。

C++ プログラム例（ABC307C）

解法1　X を固定する。A と B を動かす。

30×30 のマスの（10, 10）を左上としてシート X を貼り付けます。シート A と、シート B を場所を変えながら貼り付けます。貼り付けの範囲は、左上の座標で（0～19, 0～19）とします。

以下の手順で判定します。

シート A とシート B を貼り付けます（20×20×20×20通り）。
シート X と一致するか確認する（30×30通り）。
- （10, 10）を左上としてシート X の範囲で一致しているか確認する。一致していなければこの組み合わせは該当しない。
- シート X の範囲外に ’＃’ があれば、この組み合わせは該当しない。
ひとつでも該当する組み合わせがあれば、”Yes” を、それ以外の場合は、”No” を出力する。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int ha, wa;
	cin >> ha >> wa;
	vector<string> a(ha);
	for (int i = 0; i < ha; ++i) {
		cin >> a[i];
	}

	int hb, wb;
	cin >> hb >> wb;
	vector<string> b(hb);
	for (int i = 0; i < hb; ++i) {
		cin >> b[i];
	}

	int hx, wx;
	cin >> hx >> wx;
	vector<string> x(hx);
	for (int i = 0; i < hx; ++i) {
		cin >> x[i];
	}

	bool result = false;
	vector<vector<char>> s(30, vector<char>(30));
	for (int ia = 0; ia < 20; ++ia) {
		for (int ja = 0; ja < 20; ++ja) {
			for (int ib = 0; ib < 20; ++ib) {
				for (int jb = 0; jb < 20; ++jb) {

					for (int i = 0; i < 30; ++i) {
						for (int j = 0; j < 30; ++j) {
							s[i][j] = '.';
						}
					}

					for (int i = 0; i < ha; ++i) {
						for (int j = 0; j < wa; ++j) {
							if (a[i][j] == '#') {
								s[ia + i][ja + j] = '#';
							}
						}
					}
					for (int i = 0; i < hb; ++i) {
						for (int j = 0; j < wb; ++j) {
							if (b[i][j] == '#') {
								s[ib + i][jb + j] = '#';
							}
						}
					}

					bool this_result = true;
					for (int i = 0; i < 30; ++i) {
						for (int j = 0; j < 30; ++j) {
							if ((10 <= i)&&(i < 10 + hx)
							  &&(10 <= j)&&(j < 10 + wx)) {
								if (s[i][j] != x[i - 10][j - 10]) {
									this_result = false;
								}
							} else {
								if (s[i][j] == '#') {
									this_result = false;
								}
							}
						}
					}
					if (this_result) {
						result = true;
					}
				}
			}
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

ループ回数は、一番多いところで、20×20×20×20×30×30=1.44×10⁸となります。AtCoderのジャッジを2回試して、341msと343msでした。

解法2　A を固定して、B を動かす。黒マスの範囲で X と比較する。

解法1より少ない計算量の解法を紹介します。

基本的な考えは、50×50 のマスの（20, 20）を左上としてシート A を貼り付けます。一方、シートB を左上の座標で（0～39, 0～39）の範囲で貼り付けます。

以下の手順で判定します。

シート A を固定して、シート B を貼り付けます（40×40通り）。
これがシート X と一致しているか確認する（関数 is_ok として実装）。
- X の黒いマスの範囲を最初に求めておく（70ー79行目）。
- シート A ＆ B の黒いマスの範囲を求める（21－30行目）。
- 黒いマスの大きさが一致していなければ該当しない（32ー35行目）。
- 黒いマスの範囲の文字が一致していれば該当する（39ー46行目）。

以下が、この解法の C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int ha, wa;
vector<string> a;
int hb, wb;
vector<string> b;
int hx, wx;
vector<string> x;
int min_hx = 11;
int max_hx = -1;
int min_wx = 11;
int max_wx = -1;

bool is_ok(vector<string> s)
{
	int min_hs = 51;
	int max_hs = -1;
	int min_ws = 51;
	int max_ws = -1;
	for (int i = 0; i < 50; ++i) {
		for (int j = 0; j < 50; ++j) {
			if (s[i][j] == '#') {
				min_hs = min(min_hs, i);
				max_hs = max(max_hs, i);
				min_ws = min(min_ws, j);
				max_ws = max(max_ws, j);
			}
		}
	}

	if ((max_hs - min_hs != max_hx - min_hx)
	 || (max_ws - min_ws != max_wx - min_wx)) {
		return false;
	}
	int size_h = max_hs - min_hs;
	int size_w = max_ws - min_ws;

	bool result = true;
	for (int i = 0; i <= size_h; ++i) {
		for (int j = 0; j <= size_w; ++j) {
			if (s[min_hs + i][min_ws + j] != x[min_hx + i][min_wx + j]) {
				result = false;
			}
		}
	}

	return result;
}

int main()
{
	cin >> ha >> wa;
	a.resize(ha);
	for (int i = 0; i < ha; ++i) {
		cin >> a[i];
	}

	cin >> hb >> wb;
	b.resize(hb);
	for (int i = 0; i < hb; ++i) {
		cin >> b[i];
	}

	cin >> hx >> wx;
	x.resize(hx);
	for (int i = 0; i < hx; ++i) {
		cin >> x[i];
	}
	for (int i = 0; i < hx; ++i) {
		for (int j = 0; j < wx; ++j) {
			if (x[i][j] == '#') {
				min_hx = min(min_hx, i);
				max_hx = max(max_hx, i);
				min_wx = min(min_wx, j);
				max_wx = max(max_wx, j);
			}
		}
	}

	string t = "";
	for (int i = 0; i < 50; ++i) {
		t += '.';
	}
	vector<string> t_ab;
	for (int i = 0; i < 50; ++i) {
		t_ab.push_back(t);
	}
	for (int i = 0; i < ha; ++i) {
		for (int j = 0; j < wa; ++j) {
			t_ab[20 + i][20 + j] = a[i][j];
		}
	}

	bool result = false;
	for (int i = 0; i < 40; ++i) {
		for (int j = 0; j < 40; ++j) {
			vector<string> ab;
			ab = t_ab;

			for (int k = 0; k < hb; ++k) {
				for (int m = 0; m < wb; ++m) {
					if (b[k][m] == '#') {
						ab[i + k][j + m] = '#';
					}
				}
			}
			if (is_ok(ab)) {
				result = true;
			}
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

ループ回数は、一番多いところで、40×40×50×50=4×10⁶となります。AtCoderのジャッジを2回試して、23msと23msでした。

どちらも AC（Accepted＝正しいプログラム）と判定されました。

今回は、Python プログラムの紹介は省略します。

最後に

ABC C問題が水色Difficultyになったのは、2019年2月24日に実施されたABC119以来でした。今回の問題は、難易度が高いアルゴリズムを使うわけではなかったです。ABC の参加者は、アルゴリズム中心の対策をしている人が多いのかもしれません。

わたしは、D問題を先に解いて、E問題を中途半端に手を付けたあとにC問題に取り掛かりましたが、時間切れでした（提出すらできませんでした）。わたしの経歴では、アルゴリズムが難しい問題より実装が重たい問題の方が解ける可能性が高いため、作戦ミスだったかもしれません。

引き続き ABC の問題を紹介していきます。

ABC307 C問題（Ideal Sheet）を解く

C問題 Ideal Sheet（Difficulty : 1307）