AtCoder が提供しているABC（AtCoder Beginner Contest）339 のB問題をC++とPythonで解いてみました。ABC339は、2024年2月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Langton’s Takahashi（Difficulty : 202）
問題はリンク先をご覧ください。
ABC339 B問題 Langton’s Takahashi
問題で示されることを実装します。AtCoder Problems による Difficulty は 202 でした。
解答案
問題で示されている以下の操作をそのままプログラムとして実装します。
https://atcoder.jp/contests/abc339/tasks/abc339_b
- 現在いるマスが白で塗られている場合は、現在いるマスを黒に塗り替え、時計回りに 90∘ 回転し、向いている方向に 1 マス進む。そうでない場合は、現在いるマスを白に塗り替え、反時計回りに 90∘ 回転し、向いている方向に 1 マス進む。
C++ プログラム例（ABC339B）
プログラムを補足します。
- 方向を処理する配列 di、dj を定義しておきます（6、7行目）。この配列の添え字をインクリメントすれば時計周り、デクリメントすれば反時計周りとなります（添え字は4を法とするためデクリメントではなく3を加えています）。
- 現在の文字 s[pos_i][pos_j] によって、以下の処理をします。
- ‘.’ の場合、’#’ に書き換えます。方向をインクリメントします。
- ‘#’ の場合、’.’ に書き換えます。方向をデクリメントします。
- 方向に従い、pos_i と pos_j を更新します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int di[4] = {-1, 0, 1, 0};
int dj[4] = { 0, 1, 0, -1};
int h, w, n;
cin >> h >> w >> n;
vector<string> s;
string t(w, '.');
for (int i = 0; i < h; ++i) {
s.push_back(t);
}
int direction = 0;
int pos_i = 0;
int pos_j = 0;
for (int i = 0; i < n; ++i) {
if (s[pos_i][pos_j] == '.') {
s[pos_i][pos_j] = '#';
++direction;
} else {
s[pos_i][pos_j] = '.';
direction = direction + 3; // 3 = -1 + 4
}
direction %= 4;
pos_i += di[direction] + h;
pos_i %= h;
pos_j += dj[direction] + w;
pos_j %= w;
}
for (int i = 0; i < h; ++i) {
cout << s[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC339B）
Python 版も基本的な考え方は同じです。補足として、Python は文字列の文字を書き換えることができないため、文字列 “.” のリストのリストとしました。以下となります。
"""AtCoder Beginner Contest 339 B"""
di = [-1, 0, 1, 0]
dj = [ 0, 1, 0, -1]
h, w, n = map(int, input().split())
s = [["." for _ in range(w)] for _ in range(h)]
direction = 0
pos_i = 0
pos_j = 0
for i in range(n):
if s[pos_i][pos_j] == '.':
s[pos_i][pos_j] = '#'
direction += 1
else:
s[pos_i][pos_j] = '.'
direction += 3
direction %= 4
pos_i += di[direction] + h
pos_i %= h
pos_j += dj[direction] + w
pos_j %= w
for i in range(h):
print(*s[i], sep="")こちらも「AC」と判定されました。
最後に
問題の名前は、「ラングトンの高橋」となります。この問題で示されている操作は「ラングトンのアリ」として知られています（リンク先は Wikipedia です）。
Wikipedia の記事には、「この単純な規則で驚くほど複雑な動作をする」とあります。勉強になりました。
引き続き ABC の問題を紹介していきます。
