Livedoorブログからの移動
はてなブログからの移動

code-festival-2017-qualc.contest.atcoder.jp

解き方

  • O(n)の前計算で、s[i:j]が入れ替えて回文になるかどうかを計算できるようにする
  • s[0:i]の最小の分割数でDPを構成する（O(n^2))
  • hash値に対するDPとすることでO(n)に高速化

ハマったところ

  • 前計算→DPの流れまではわかった
  • 前計算について、おそらく累積和のような方法でO(n)にするのだろうという予測はついたが、思いつかなかった
    • 64個以内の要素が01を取る時はhashとbit演算の組み合わせを考えるのは有効？
  • hash値に対するDPが思いつかなかった
    • 今の自分では思いつく気がしない

github.com