Official
C - Rotate and Palindrome Editorial by nok0
この問題を解くために重要な考察として、最初に \(A\) 円払う操作を何回かしてから \(B\) 円払う操作を何回か行うというように操作の順序を決め打っていいというものがあります。また、 \(A\) 円払う操作の回数は \(N\) 回未満であるということも重要です。( \(N\) 回行うと元に戻るため)
この考察を用いると、制約が小さいことから \(A\) 円払う操作の回数を全探索できます。 \(B\) 円払う操作の必要回数の最小値は、回文になるために同じ文字でないといけない組のうち、二つの文字が現時点で一致していないものの個数として求まります。
よってこの問題を \(\mathrm{O}(N^2)\) で解くことが出来ました。
実装例(c++):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long a, b;
string s;
cin >> n >> a >> b >> s;
s += s;
long long ans = 1ll << 60;
for(int i = 0; i < n; i++) {
long long tmp = a * i;
for(int j = 0; j < n / 2; j++) {
int l = i + j;
int r = i + n - 1 - j;
if(s[l] != s[r]) tmp += b;
}
ans = min(ans, tmp);
}
cout << ans << endl;
}
実装例(Python):
n, a, b = map(int, input().split())
s = input()
s += s
ans = 1 << 60
for i in range(n):
tmp = a * i
for j in range(n // 2):
if s[i + j] != s[i + n - 1 - j]:
tmp += b
ans = min(ans, tmp)
print(ans)
posted:
last update: