ABC286:C - Rotate and Palindromeの解法メモ

この問題の本質

• 回転回数 k を 0..N-1 で全探索し、各 k について回転後の回文条件i と N-1-i の不一致ペア数を数える

• cost = k*A + mismatch*B を計算し、最小となる k を選ぶ

① 「回転回数」を決めると、残りは一意に決まる

• 回転を k 回すると
  → 回転コスト：k * A
• 回転後の文字列を 回文にするための変更回数は、
  対称な位置の不一致ペア数で決まる
  → 変更コスト：mismatch * B
  最小コスト = minₖ ( k*A + 回文にする最小変更コスト )

② DPではなく「全探索」が成立する理由

• 回転は最大でも N 回
• 各回転で回文判定は N/2 比較
• 計算量：O(N^2) → 制約内で十分間に合う

「状態が連続しない」「1回ごとに独立」なのでDPにする意味がない

③ 回転後の文字列を作らないのがコツ

回転後の文字列 T を

T[i] = S[(i+k)%N]

と表すことで、

回文条件

T[i] == T[N-1-i]

は

S[(i+k)%N] == S[(N-1-i+k)%N]

になる。

これは、回転後、線対称になる元の添字を直接比較している。

④ mismatch の数え方

• i = 0 .. N/2-1
• 対称ペア (i, N-1-i) を1回ずつ見る
• 不一致なら mismatch++

解法のプロセス

1. 「最終的に必要なのは回文」だと気づく
2. 操作は「回転」と「文字変更」の2種類
3. 回転回数 k を固定して考える
4. 回転後の文字列を 式で表す
5. 回文にするための最小変更回数を数える
6. k=0..N-1 を全探索して最小値を取る

解答

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    long long A, B;
    cin >> N;
    cin >> A >> B;
    string S;
    cin >> S;
    int mismatch;
    long long ans = (1LL << 60);
    long long cost;
    for (int k = 0; k < N; k++) {
        mismatch = 0;
        for (int i = 0; i < N / 2; i++) {
            int a = (i + k) % N;
            int b = (N - 1 - i + k) % N;
            if (S[a] != S[b]) mismatch++;
        }
        cost = k * A + mismatch * B;
        ans = min(ans, cost);
    }
    cout << ans;
    return 0;
}