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つ
DDCC2017 Qual D: 石
ddcc2017-qual.contest.atcoder.jp
解き方
- 南北、東西に対称となる4点それぞれについて場合分け
- 以下の2パターンのどちらかが答えとなる
- 東西方向に揃える→南北・東西両方に揃える→0個になるまで取り除いていく（最大となるように）
- 南北方向に揃える→南北・東西両方に揃える→0個になるまで取り除いていく（最大となるように）
ハマったところ
- 場合分けの抜け漏れが多かった
- 4点が1ペアになることがわかっていたのだからそれを単位として考えるべきだったのだろう
