AtCoder が提供しているABC（AtCoder Beginner Contest）322 のD問題をC++とPythonで解いてみました。ABC322は、2023年9月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Polyomino（Difficulty : 1310）
問題はリンク先をご覧ください。
4×4のポリオミノパズルを解きます。実装は重たいです。AtCoder Problems による Difficulty は 1310 でした。
解答案
縦4マス、横4マスと小さいため、全部の場合を調べることができます。以下の場合を考慮します。3つのポリオミノを a、b、c とします。この a、b、c は、空白マス含めて 4×4 マスとして計算します。
- ポリオミノ a、b、c をそれぞれ回転したピース 4 x 4 x 4 通り
- ポリオミノ a の配置場所、後で説明しますが、7 x 7 通りあります。ポリオミノ b、c についても同様です。
ポリオミノを配置する仮想的なグリッドを 10×10 マスとします。この中心の 4×4 マスについて調べます。ポリオミノ a、b、c の左上の座標は、[0-7) x [0-7) に配置します。この左上座標は、中心の 4×4 マス [3, 7) x [3, 7) とグリッドの一部が重なるように選んでいます。
また、ポリオミノ a は回転させないで、固定してよいことが分かります。このため、全検索した場合の通り数は、以下となります。
$$4 \times 4 \times 7 \times 7 \times7 \times7 \times7 \times 7 \doteqdot 1.88 \times 10^6$$
C++ プログラム例（ABC322D）
以下は、プログラムの補足です。
- ポリオミノを回転させる操作を関数 rotete として分けました（4ー11行目）。この関数で行っている変換は、紙に書くことで把握できました。
- 10×10のグリッドを初期化する関数 clear を分けました（13ー20行目）。
- ポリオミノが重複なく詰まっているか確認する関数 is_ok を分けました（22ー34行目）。
- グリッド a、b、c を読み込み、b と c を回転させたピースを計算します。この時点で、’#’ の数が16個でなければ、”No” を出力して終了します（87行目の if 文）。
- 8重ループで全探索します。ここは再帰で書く方法もありますが、慣れている8重ループで書きました。
- ポリオミノ a、b、c を配置して、10×10のグリッドにある重なっているピースの個数を計算します（105-107行目）。
- 重複なく詰まっているかを 10×10 の真ん中 4×4 のグリッドの値がすべて1になっているか確認します。
長くなりましたが、以下が、最終的なC＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
void rotate(int *a, int *b)
{
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
b[i * 4 + j] = a[(3 - j) * 4 + i];
}
}
}
void clear(int p[10][10])
{
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
p[i][j] = 0;
}
}
}
bool is_ok(int p[10][10])
{
bool result = true;
for (int i = 3; i < 7; ++i) {
for (int j = 3; j < 7; ++j) {
if (p[i][j] != 1) {
result = false;
}
}
}
return result;
}
int main()
{
int n_sharp = 0;
int a[4][4];
for (int i = 0; i < 4; ++i) {
string s;
cin >> s;
for (int j = 0; j < 4; ++j) {
if (s[j] == '#') {
a[i][j] = 1;
++n_sharp;
} else {
a[i][j] = 0;
}
}
}
int b[4][4][4];
for (int i = 0; i < 4; ++i) {
string s;
cin >> s;
for (int j = 0; j < 4; ++j) {
if (s[j] == '#') {
b[0][i][j] = 1;
++n_sharp;
} else {
b[0][i][j] = 0;
}
}
}
rotate(&(b[0][0][0]), &(b[1][0][0]));
rotate(&(b[1][0][0]), &(b[2][0][0]));
rotate(&(b[2][0][0]), &(b[3][0][0]));
int c[4][4][4];
for (int i = 0; i < 4; ++i) {
string s;
cin >> s;
for (int j = 0; j < 4; ++j) {
if (s[j] == '#') {
c[0][i][j] = 1;
++n_sharp;
} else {
c[0][i][j] = 0;
}
}
}
rotate(&(c[0][0][0]), &(c[1][0][0]));
rotate(&(c[1][0][0]), &(c[2][0][0]));
rotate(&(c[2][0][0]), &(c[3][0][0]));
if (n_sharp != 4 * 4) {
cout << "No" << endl;
return 0;
}
bool result = false;
int p[10][10];
for (int ix = 0; ix < 7; ++ix) {
for (int iy = 0; iy < 7; ++iy) {
for (int j = 0; j < 4; ++j) {
for (int jx = 0; jx < 7; ++jx) {
for (int jy = 0; jy < 7; ++jy) {
for (int k = 0; k < 4; ++k) {
for (int kx = 0; kx < 7; ++kx) {
for (int ky = 0; ky < 7; ++ky) {
clear(p);
for (int x = 0; x < 4; ++x) {
for (int y = 0; y < 4; ++y) {
p[x + ix][y + iy] += a[x][y];
p[x + jx][y + jy] += b[j][x][y];
p[x + kx][y + ky] += c[k][x][y];
}
}
if (is_ok(p)) {
result = true;
}
}
}
}
}
}
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC322D）
Python 版も基本的な考え方は同じです。
ループの回数はC++と変わりませんが、「Python (CPython 3.11.4)」では、まったく間に合いません。「Python (PyPy 3.10-v7.3.12)」で、ぎりぎりAC判定（制限時間 2000ms に対して、1848ms）となりました。
"""AtCoder Beginner Contest 322 D"""
import sys
def rotate(a, b):
for i in range(4):
for j in range(4):
b[i][j] = a[3 - j][i]
def clear(p):
for i in range(10):
for j in range(10):
p[i][j] = 0
def is_ok(p):
result = True
for i in range(3, 7):
for j in range(3, 7):
if p[i][j] != 1:
result = False
return result
n_sharp = 0
a = [[0 for _ in range(4)] for _ in range(4)]
for i in range(4):
s = input()
for j in range(4):
if s[j] == '#':
a[i][j] = 1
n_sharp += 1
else:
a[i][j] = 0
b = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
for i in range(4):
s = input()
for j in range(4):
if s[j] == '#':
b[0][i][j] = 1
n_sharp += 1
else:
b[0][i][j] = 0
rotate(b[0], b[1])
rotate(b[1], b[2])
rotate(b[2], b[3])
c = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
for i in range(4):
s = input()
for j in range(4):
if s[j] == '#':
c[0][i][j] = 1
n_sharp += 1
else:
c[0][i][j] = 0
rotate(c[0], c[1])
rotate(c[1], c[2])
rotate(c[2], c[3])
if n_sharp != 4 * 4:
print("No")
sys.exit(0)
result = False
p = [[0 for _ in range(10)] for _ in range(10)]
for ix in range(7):
for iy in range(7):
for j in range(4):
for jx in range(7):
for jy in range(7):
for k in range(4):
for kx in range(7):
for ky in range(7):
clear(p)
for x in range(4):
for y in range(4):
p[x + ix][y + iy] += a[x][y]
p[x + jx][y + jy] += b[j][x][y]
p[x + kx][y + ky] += c[k][x][y]
if is_ok(p):
result = True
print("Yes" if result else "No")最後に
実装が重たいグリッドの問題は、ABC307C問題（Difficulty 1307 解説記事はこちら）でも出題されました。
わたしは、緑色としてはアルゴリズムの知識が足りません。実装が重めの問題を解く方が良いと考えて、この問題に取り組みました。コンテスト中には間に合って提出しましたが、外の範囲のチェックが抜けていてひとつのテストケースでWA判定されて、時間切れでした（この対策が、C++ 87行目のif文です）。惜しかったです。
AtCoder 参加者は、実装が重めの全探索は苦手とする傾向があるように思います。わたしが感じる難易度より Difficulty が高くでるように感じます。
また、今回の知識をつかってポリオミノパズルを解いてみたくなりました。
引き続き ABC の問題を紹介していきます。
