AtCoder が提供しているABC（AtCoder Beginner Contest）361 D問題をC++とPythonで解いてみました。ABC361は、2024年7月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Go Stone Puzzle（Difficulty : 1202）
問題の詳細は、リンク先をご覧ください。
文字列を頂点のグラフと考えて、最短距離をBFSで求めます。AtCoder Problems による Difficulty は 1202 でした。
解答案
文字列 $S$ に2つの空きマス “..” を加えて、操作の結果得られる文字列をグラフの頂点と、操作ができる文字列への変換を辺と考えます。結果的に、グラフの最短経路を求める問題となりました。
C++ プログラム例（ABC361D）
BFSを使います。距離を表す dict には、map を使います。
- map の初期値は0であるため文字列 $S$ と $T$ が一致している場合は、0を出力して、終了します（11ー14行目）。
- 2つの文字列に含まれる ‘B’ の数が異なる場合は、$S$ と $T$ は、一致することはありません。-1 を出力して終了します（16ー29行目）。
- BFSを使って、キューとdictを更新します。空きマスを見つけ、文字を入れ替える操作を辺の移動と考えます。
- 最後に、文字列 $T$ の距離を出力します。初期値の0である場合、到達しないため -1 を出力します。
以下が、C++プログラムです。BFSに関係する定番コードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
string t;
cin >> s >> t;
if (s == t) {
cout << 0 << endl;
return 0;
}
int sb = 0;
int tb = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'B') {
++sb;
}
if (t[i] == 'B') {
++tb;
}
}
if (sb != tb) {
cout << -1 << endl;
return 0;
}
s += "..";
map<string, int> dist;
queue<string> que;
que.push(s);
dist[s] = 0;
while (!que.empty()) {
string now = que.front();
que.pop();
int aki;
for (int i = 0; i <= n; ++i) {
if (now[i] == '.') {
aki = i;
break;
}
}
string next_v;
for (int i = 0; i <= n; ++i) {
if ((i == aki)||(i + 1 == aki)||(i == aki + 1)) {
continue;
}
next_v = now;
swap(next_v[i], next_v[aki]);
swap(next_v[i + 1], next_v[aki + 1]);
if (dist[next_v] == 0) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
t += "..";
if (dist[t] == 0) {
cout << -1 << endl;
} else {
cout << dist[t] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC361D）
Python版も基本的な考え方は同じです。辞書として defaultdict、キューを deque を使いました。
"""AtCoder Beginner Contest 361 D"""
import sys
from collections import defaultdict
from collections import deque
n = int(input())
s = input()
t = input()
if s == t:
print(0)
sys.exit()
if s.count('B') != t.count('B'):
print(-1)
sys.exit()
s += ".."
dist = defaultdict(int)
que = deque()
que.append(s)
dist[s] = 0
while que:
now = que.popleft()
for i in range(n + 1):
if now[i] == '.':
aki = i
break
for i in range(n + 1):
if i == aki or i + 1 == aki or i == aki + 1:
continue
next_v = list(now)
next_v[i], next_v[aki] = next_v[aki], next_v[i]
next_v[i + 1], next_v[aki + 1] = next_v[aki + 1], next_v[i + 1]
next_v = "".join(next_v)
if dist[next_v] == 0:
que.append(next_v)
dist[next_v] = dist[now] + 1
t += ".."
if dist[t] == 0:
print(-1)
else:
print(dist[t])どちらも「AC」と判定されました。
最後に
コンテストでは、ゲームを解くDPのように考えて時間切れでした。グラフの最短経路の問題と気が付けば、コンテスト中に解くことができたと考えています。勉強になりました。
引き続き ABC の問題を紹介していきます。
