AtCoder が提供しているABC（AtCoder Beginner Contest）320 のC問題をC++とPythonで解いてみました。ABC320は、2023年9月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Slot Strategy 2 (Easy)（Difficulty : 851）
問題はリンク先をご覧ください。
ABC320 C問題 Slot Strategy 2 (Easy)
スロットの動作を模擬します。AtCoder Problems による Difficulty は 851 でした。
解答案
C++ プログラム例（ABC320C）
スロットの3つリールを止める時間を前から、$i,\;i + j,\;i + j + k$ とします。リール1周を超えて回すのは意味がないため、$i,\;j,\,k$ の範囲は以下となります。
- $0 \leqq i < m$
- $1 \leqq j \leqq m$
- $1 \leqq k \leqq m$
ボタンを同時に押せないため、$j$ や $k$ は0になりません。
ボタンを押すタイミングが決まりました。どのリールから止めるかを next_permutation を使って順列全探索しました（29行目）。
止めるリールと時間が決まったので、すべてのリールの数字が同じか確認します。すべて同じであれば、$i + j + k$ の値が最小か比較して変数 result に格納します。（23－28行目）。
計算量は、最大でも $100^3 \times 6 = 6 \times 10^6$ となり十分に間に合います。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int m;
cin >> m;
vector<string> s(3);
cin >> s[0] >> s[1] >> s[2];
vector<int> p(3);
p[0] = 0;
p[1] = 1;
p[2] = 2;
int result = INF;
for (int i = 0; i < m; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= m; ++k) {
do {
char c0, c1, c2;
c0 = s[p[0]][i];
c1 = s[p[1]][(i + j) % m];
c2 = s[p[2]][(i + j + k) % m];
if ((c0 == c1)&&(c1 == c2)) {
result = min(result, i + j + k);
}
} while (next_permutation(p.begin(), p.end()));
}
}
}
if (result < INF) {
cout << result << endl;
} else {
cout << -1 << endl;
}
return 0;
}参考
実際のコンテストでは、上記プログラムで $j$ と $k$ の範囲を $m$ 未満として提出してしまいました。その結果、WA判定を一度もらいました（正しくは、$m$ 以下）。
- 3つのリールは、最大でも3周までしか回らない。
- それぞれのリールを止める時間が異なり、数字が一致していれば、最小値を求める候補になる。
計算量は $300^3 ＝2.7 \times 10^7$ となります。少し大きくなりますが、プログラムがシンプルとなり間違えにくくなります。以下が、この考え方で書いたプログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int m;
cin >> m;
vector<string> s(3);
cin >> s[0] >> s[1] >> s[2];
int result = INF;
for (int i = 0; i < 3 * m; ++i) {
for (int j = 0; j < 3 * m; ++j) {
for (int k = 0; k < 3 * m; ++k) {
if ((i == j)||(j == k)||(k == i)) {
continue;
}
char c0, c1, c2;
c0 = s[0][i % m];
c1 = s[1][j % m];
c2 = s[2][k % m];
if ((c0 == c1)&&(c1 == c2)) {
result = min(result, max(i, max(j, k)));
}
}
}
}
if (result < INF) {
cout << result << endl;
} else {
cout << -1 << endl;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC320C）
最初に紹介した C++ のプログラムを Python に移植しました。プログラムでの補足は、以下となります。
- 順列の生成に itertools.permutations を使いました（12行目）。
- リールの数がすべて一致しているかで chained-comparison と呼ばれる書き方をしました（16行目）。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 300 C"""
import itertools
INF = 10 ** 9
m = int(input())
s = [input() for _ in range(3)]
result = INF
for i in range(m):
for j in range(1, m + 1):
for k in range(1, m + 1):
for p in list(itertools.permutations([0, 1, 2])):
c0 = s[p[0]][i]
c1 = s[p[1]][(i + j) % m]
c2 = s[p[2]][(i + j + k) % m]
if c0 == c1 == c2:
result = min(result, i + j + k)
print(result if result < INF else -1)最後に
この問題は、特別なアルゴリズムは必要ではなく、全探索するだけです。一方、この問題の Difficulty は 851 でした。AtCoder の参加者の傾向がでているのかもしれません。
引き続き ABC の問題を紹介していきます。
