問題概要

長さ $N$ の文字列 $S$ が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。

先頭の文字を末尾に移動する (コスト $A$ )
文字を 1 つ変更する (コスト $B$ )

回文にするための最小コストを求めよ。

解法

まともに考えると、色んなパターンがありそうで頭がこんがらがってしまう！！！

こういうときは「操作の流れを単純化できないか」を考えるとよかったりする。今回は、操作の流れを次の 2 ステップに分けて考えとうまくいく。

Step 1：先頭の文字を何文字か、末尾に移動する
Step 2：その結果できた文字列に対して、前半の文字を適切に置き換えることで回文に一致するようにする

つまり、一度コスト A の操作をやり切ったあとは、コスト B の操作のみに専念すればよいということだ。

そのように考えて良い理由

文字を置き換えてから、先頭の文字を末尾に移動するという 2 回の操作は、

先に先頭の文字を末尾に移動してから、上述の文字を置き換える操作

に置き換えても結果は等しくなる。よって、任意の操作列は、その最終結果を変更することなく、「先に先頭の文字を末尾に移動する操作をすべてやり切るような操作列」に変形できる。

コスト A の操作回数を固定する

以上の考察で考えやすくなった。あとは、コスト A の操作回数 $i$ を固定して考えよう。各 $i$ についての最小コストをそれぞれ求めて、その最小値をとればよいのだ。

さて、コスト A の操作回数を固定すると、次の問題を解けばよいことになる。

文字列 $T$ ( $S$ の先頭 $i$ 文字を末尾に移動したもの) が与えられる。

$T$ の文字をいくつか変えることで回文にしたい。1 文字変えるごとにコスト $B$ を消費する。最小コストを求めよ。

これは下図のように、左から $i$ 文字目と右から $i$ 文字目が異なっている箇所の個数を数えればよい。これは $O(N)$ の計算量で実行できる。

全体としては、計算量は $O(N^{2})$ となる。

コード

Python

# 入力
N, A, B = map(int, input().split())
S = input()

# 先頭の文字を移す回数を固定して考える
res = 1<<60
for i in range(N):
    # 先頭 i 個を末尾に移す場合の最終コストを求める
    cost = 0
    for j in range(N//2):
        if S[j] != S[N-j-1]:
            cost += B
    res = min(res, cost + A * i)

    # 先頭の文字を末尾に移動
    S = S[1:] + S[0]

print(res)

C++

#include<bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    long long N, A, B;
    string S;
    cin >> N >> A >> B >> S;

    // 先頭の文字を移す回数を固定して考える
    long long res = 1LL<<60;
    for (int i = 0; i < N; ++i) {
        // 先頭 i 個を末尾に移す場合の最終コストを求める
        long long cost = 0;
        for (int j = 0; j < N/2; ++j) {
            if (S[j] != S[N-j-1]) cost += B;
        }
        res = min(res, cost + A * i);

        // 先頭の文字を末尾に移動
        S = S.substr(1) + S[0];
    }
    cout << res << endl;
}