読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

RUPC 2016 day3 F: Kitsuchiri

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=F

解法

S=rev(S) が成り立てば左右対称である。等価判定はハッシュを使うと楽。

[L,R] に x を加算するというのは、

  • hash(S) に x*(bL+bL+1+...+bR) を足す
  • hash(rev(S)) に x*(bL'+bL'+1+...+bR') を足す

ということ。なお L'=N-1-R, R'=N-1-L。

加算が簡単にできるので hash(S) と hash(rev(S)) を変数として持っておけば簡単に更新ができる。

これは Rolling Hash を以下の式で求めた場合の話なので、ハッシュの計算法が異なれば式は変わってくる。

$$ hash(S) = \sum_{i=0}^{N-1} S[i] b^i $$

RUPC 2016 day3 F: Kitsuchiri

多分想定解は違う気がする。