AtCoder が提供しているABC（AtCoder Beginner Contest）357 C問題をC++とPythonで解いてみました。ABC357は、2024年6月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sierpinski carpet（Difficulty : 371）
問題の詳細は、リンク先をご覧ください。
再帰関数を使ってお絵かきします。AtCoder Problems による Difficulty は 371 でした。
解答案
問題文のカーペットの定義が再帰的に書かれています。具体的には、レベル $K$ のカーペットは、レベル $(K-1)$ のカーペットから成っています。またレベル0のカーペットは自明（黒いマス1個）な形をしています。
再帰関数を使って問題を解きます。
C++ プログラム例（ABC357C）
再帰関数 rec で、レベル $N$ のカーペットを埋めていきます。計算を簡素化するために、rec の引数には、$N$ ではなく、$3^N$ を与えます。また、左上の座標 $(i, j)$ も与えます。
- $3^N \times 3^N$ の大きさのカーペット s を用意します。模様は初期値 ‘.’ で埋めておきます。
- 再帰関数 rec は、カーペットの一辺の大きさと左上の座標を受け取ります。
- $3^N=1$ であれば、与えられた座標を ‘#’ にします。
- 全体を $3 \times 3$ の9個のカーペットに分割し、真ん中は処理しません。そのまま ‘.’ で埋められたままとなります（16ー18行目）。
- 残りの8個に対して、$3^{N-1} \times 3^{N-1}$ のカーペットを埋めるように rec を再帰的に呼び出します（19行目）。
以下が、C++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<string> s;
void rec(int n3, int i, int j)
{
if (n3 == 1) {
s[i][j] = '#';
return;
}
int t = n3 / 3;
for (int ti = 0; ti < 3; ++ti) {
for (int tj = 0; tj < 3; ++tj) {
if ((ti == 1)&&(tj == 1)) {
continue;
}
rec(t, i + t * ti, j + t * tj);
}
}
}
int main()
{
int n;
cin >> n;
int n3 = 1;
for (int i = 0; i < n; ++i) {
n3 *= 3;
}
s.resize(n3);
string t;
for (int i = 0; i < n3; ++i) {
t += '.';
}
for (int i = 0; i < n3; ++i) {
s[i] = t;
}
rec(n3, 0, 0);
for (int i = 0; i < s.size(); ++i) {
cout << s[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC357C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 357 C"""
def rec(n3, i, j):
global s
if n3 == 1:
s[i][j] = '#'
return
t = n3 // 3
for ti in range(3):
for tj in range(3):
if ti == 1 and tj == 1:
continue
rec(t, i + t * ti, j + t * tj)
n = int(input())
n3 = 3 ** n
s = [['.' for _ in range(n3)] for _ in range(n3)]
rec(n3, 0, 0)
for i in range(n3):
print(*s[i], sep='')こちらも「AC」と判定されました。
最後に
再帰関数について、ブログを書き始めた2年前と比較すると、すんなりと書けるようになってきました。今回は、問題の定義が再帰的に書かれていたため、うまく再帰関数として表現することができました。
引き続き ABC の問題を紹介していきます。
