Quiz
https://atcoder.jp/contests/arc055/tasks/arc055_c
Submit
https://atcoder.jp/contests/arc055/submissions/4992693
解法
- editorialの通り
ACまでに踏んだステップ
- 部分点 20点を狙う
- |S| > 2000 のときはすぐ終了してテストをすぐ終わらせる
- a, c の探索もナイーブに実装する
- 部分点が通るまでやる
- 通ったら、高速化
- ローリングハッシュの二分探索？よくわからん
- Z Algorithm いけそう
- sにZ Algorithmをして配列を持っておく (a用)
- sを反転した文字列t
- tにZ Algorithmをして配列を持っておく (c用)
- AC
学び
- 部分点から満点までの距離は意外と近い
- 部分点と満点では解法が違うことがあるが、部分的な入れ替えで済むことが多く、無駄にはならない
- 大学受験の数学に似ている
- Z algorithmは導入しやすい
