CODE FESTIVAL 2017 qual C D: Yet Another Palindrome Partitioning
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が思いつかなかった
- 今の自分では思いつく気がしない
CODE FESTIVAL 2017 qual C C: Inserting 'x'
code-festival-2017-qualc.contest.atcoder.jp
解き方
- 両端から調査していく(
x
が片方に見つかったらx
をもう一方に足す)
ハマったところ
- 最初、奇数回出現する文字があるかないかで場合分けなど不要に複雑にしていた
CODE FESTIVAL 2017 qual C B: Similar Arrays
code-festival-2017-qualc.contest.atcoder.jp
解き方
a_m...a_n
と似ていて、積が偶数である数列b_m...b_n
としてあり得る数列の個数を、m=n, n-1, ..., 1
の順序で考える|a_i - b_i| <= 1
より、b_i
として考えられる数字は3つ