AtCoder が提供しているABC（AtCoder Beginner Contest）345 のD問題をC++で解いてみました。ABC345は、2024年3月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Tiling（Difficulty : 1419）
問題はリンク先をご覧ください。
左上から再帰的にタイルを詰めていきます。AtCoder Problems による Difficulty は 1419 でした。
解答案
タイルを読み込んだ順に $1$ から $N$ までの番号を付けます。
以下の操作を再帰的に行います。
- $H$行$W$列のマス目の左上から調べていき、空いている場合にタイルを置きます。タイルは、番号が少ない方から、縦置きまたは横置きとして置けるか調べます。
- タイルが置けたら、そのタイルを使用済みとして、次のタイルを探して置きます（再帰的に関数を呼び出します）。
- マス目がすべて埋まれば、true（タイルを詰めることに成功）を返します。
- マス目をすべて埋めることができなければ、false を返して、使ったタイルを未使用に戻します。
- タイルが置けなければ、次のタイルについて調べます。
- タイルが置けたら、そのタイルを使用済みとして、次のタイルを探して置きます（再帰的に関数を呼び出します）。
C++ プログラム例（ABC345D）
上記の考察をもとに再帰関数 rec を実装しました。プログラムは少し長いですが、以下に示します。
#include <bits/stdc++.h>
using namespace std;
int tile[10][10];
int n;
int h, w;
vector<int> a;
vector<int> b;
vector<bool> used;
void copy_tile(int dst[10][10], int src[10][10])
{
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
dst[i][j] = src[i][j];
}
}
}
bool rec(int now[10][10])
{
int t[10][10];
copy_tile(t, now);
int s_h = -1;
int s_w = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if ((t[i][j] == 0)&&(s_h == -1)) {
s_h = i;
s_w = j;
}
}
}
if (s_h == -1) {
return true;
}
for (int i = 1; i <= n; ++i) {
if (!used[i]) {
bool is_ok = true;
if ((s_h + a[i] - 1 < h)&&(s_w + b[i] - 1 < w)) {
for (int ih = 0; ih < a[i]; ++ih) {
for (int iw = 0; iw < b[i]; ++iw) {
if (t[s_h + ih][s_w + iw] != 0) {
is_ok = false;
} else {
t[s_h + ih][s_w + iw] = i;
}
}
}
if (is_ok) {
used[i] = true;
if (rec(t)) {
return true;
}
used[i] = false;
copy_tile(t, now);
}
}
if (a[i] == b[i]) {
continue;
}
is_ok = true;
if ((s_h + b[i] - 1 < h)&&(s_w + a[i] - 1 < w)) {
for (int ih = 0; ih < b[i]; ++ih) {
for (int iw = 0; iw < a[i]; ++iw) {
if (t[s_h + ih][s_w + iw] != 0) {
is_ok = false;
} else {
t[s_h + ih][s_w + iw] = i;
}
}
}
if (is_ok) {
used[i] = true;
if (rec(t)) {
return true;
}
used[i] = false;
copy_tile(t, now);
}
}
}
}
return false;
}
int main()
{
cin >> n >> h >> w;
a.resize(n + 1);
b.resize(n + 1);
used.assign(n + 1, false);
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
}
if (rec(tile)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python プログラムの紹介を省略します。
最後に
ABC307C問題（解説記事）、ABC322D問題（解説記事）に続き、実装重めの問題でした。なかなか時間内に解くことができません。
引き続き ABC の問題を紹介していきます。
