AtCoder が提供しているABC（AtCoder Beginner Contest）286 のC問題をC++とPythonで解いてみました。ABC286は、2023年1月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Rotate and Palindrome（Difficulty : 565）
問題はリンク先をご覧ください。
ABC286 C問題 Rotate and Palindrome
問題の設定に従い全検索しました。AtCoder Problems による Difficulty は 565 でした。
解答案
問題を解く方針を書きだします。
- N、A、B と文字列 S を読み込む。
- S の後ろに S を加える。これは回転操作の処理を簡素化するためです。
- 文字列 S に対して、以下を繰り返す。ループ変数は i（0 $\leqq$ i $\leqq$ N – 1）
- S[i] から始まる長さ N の文字数に対して、回文して一致していない文字数をカウントする。
- S[i] から始めた場合の、操作の値段を求める。
ループ変数 i に対して、i × A 円の費用が発生します。回文として一致していない文字数分 B 円の費用が発生します。
- 一番安い値段を出力する。
C++ プログラム例（ABC286C）
解答の初期値は、最小値を求めるため、非常に大きな値を設定することがあります。今回は、明らかな解（n/2 * b）があるため、その値を初期値としました。
値段の最小値を解答として出力します。以下が C++ プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n;
cin >> n;
ull a, b;
cin >> a >> b;
string s;
cin >> s;
s = s + s;
ull result = (n / 2) * b;
for (int i = 0; i < n; ++i) {
ull temp_cost = i * a;
for (int j = 0; j < n / 2; ++j) {
if (s[i + j] != s[i + n - 1 - j]) {
temp_cost += b;
}
}
result = min(result, temp_cost);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC286C）
上記の C++ プログラムをそのまま移植しました。
"""AtCoder Beginner Contest 286 C"""
n, a, b = map(int, input().split())
s = input()
s += s
result = n // 2 * b
for i in range(n):
temp_cost = i * a
for j in range(n // 2):
if s[i + j] != s[i + n - 1 - j]:
temp_cost += b
result = min(result, temp_cost)
print(result)このプログラムは、Python（3.8.2）では、TLE（Time Limit Exceeded）判定でした。一方、PyPy3（7.3.0）では、AC 判定となりました。
以下は、Python（3.8.2）で AC 判定を受けているプログラムを参考にしました。まず、スライス記法で S をローテーションします。前のプログラムとの差分の背景色を変更しました。
"""AtCoder Beginner Contest 286 C"""
n, a, b = map(int, input().split())
s = input()
result = n // 2 * b
for i in range(n):
temp_cost = i * a
for j in range(n // 2):
if s[j] != s[n - 1 - j]:
temp_cost += b
result = min(result, temp_cost)
s = s[1:] + s[0]
print(result)このプログラムもまだ Python（3.8.2）で TLE 判定でした。次に一番内側にあるループを関数化しました。引数はすべて渡します。次のプログラムとなります。
"""AtCoder Beginner Contest 286 C"""
def cost_b(s, n, b):
cost = 0
for i in range(n // 2):
if s[i] != s[n - 1 - i]:
cost += b
return cost
n, a, b = map(int, input().split())
s = input()
result = n // 2 * b
for i in range(n):
result = min(result, cost_b(s, n, b) + i * a)
s = s[1:] + s[0]
print(result)このプログラムは、Python（3.8.2）でも AC 判定となりました。参考までに関数引数を渡さず、グローバル変数を参照しても AC 判定でしたが、時間はかかる傾向がありました。
なお、関数に切り出す場合も S をスライス記法でローテーションしないプログラムでは、TLE判定を受けていました。
Python については、以下の傾向があると思われます。ただし、わたしは Python に習熟していないため、誤っているかもしれません。
- リストの添え字の計算は、可能な範囲で簡略化する。
演算毎に範囲チェックをしている可能性があります。 - 内側のループは関数化した方が速い場合がある。関数化する場合、グローバル変数の参照ではなく、引数で渡した方が速い傾向がある。
最後に
問題の設定はやや難しいですが、全探索をする問題でした。
（今の私の実力では、）PyPy で提出したほうが無難かもしれません。もう少し習熟して、Python の力を最初から引き出したいです。
引き続き ABC の問題を紹介していきます。
