Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 286 C問題 Rotate and Palindrome

AtCoder ABC286 ABC C問題 300 pts

問題

atcoder.jp

提出解答

問題の概要

長さ N の英小文字列 S が与えられる.

次の操作を好きな順に合計 0 回以上行うことができる.

  • A 円払う. その後, S の左端の文字を右端に移動させる.
  • B 円払う. その後, S にある 1 文字を好きな英小文字に置き換える.

制約

  • 1 \leq N \leq 5000
  • 1 \leq A,B \leq 10^9
  • S は長さ N の英小文字

解法

長さ N の英小文字列を定義域とする写像 F,G_{i,c} を次のように定義する.

  • F(S) で S の左端の文字を右端に移動させた文字列とする.
  • G_{i,c}(S) で S の i 文字目を c に置き換えた文字列とする.

このとき, F, G_{i,c} に対して, 以下が成り立つ. なお, I で恒等写像とする.

  • \underbrace{F \circ \dots \circ F}_n=I.
  • G_{i, c} \circ F=F \circ G_{i+1, c}. ただし, N+1=1 とする.
  • G_{i,c} \circ G_{i,d}=G_{i,c}
  • G_{i,c} \circ G_{j,d}=G_{j,d} \circ G_{i,c}

よって, 任意の操作たちは 0 以上 (N-1) 以下の整数 k と 1 \leq i_1 \lt \dots i_l \leq N と英小文字 c_1, \dots, c_l を用いて,

G_{i_l, c_l} \circ \dots G_{i_1, c_1} \circ \underbrace{F \circ \dots \circ F}_k

とすることができる.

以降では k=0,1,2 \dots, N-1 それぞれに対して, F を k 回作用させた後, 置き換えのみを行った場合を考える.

このとき, 置き換えの回数を最初にするためには次のようにするしかない.

  • i=1,2, \dots, \left \lfloor \dfrac{N}{2} \right \rfloor に対して, S の左から i 文字目と右から i 文字目が異なるならば, 一方を他方に置き換える.

これによる操作回数の最小値を P_k とするとき, 以下が答えになる.

\displaystyle \min_{k=0,1, \dots, N-1} \left(Ak+BP_k \right)

計算量は O(N^2) 時間である.