コンテストURL: https://yukicoder.me/contests/416

アドベコンは参加も出題も初めてです（そもそも１年前のアドベコンの時点では競プロ自体していなかったため）。難問でも良いとのことでしたので、せっかくならと思いU問題の枠に★5の問題を出させていただきました。

基本的に前から順に、出題当日に解けなかったものは解説を読んででも解くように心掛けて参加しました。初めてのフック長公式、初めての遅延セグメント木（ただし実装時間がなかったのでAtCoderLibrary使用）、初めてのHD分解、初めての分割統治、初めての一次式の乗算のマージテク、初めての多点評価、初めての評価点シフト、本当に多くのことを学ぶことができました。結局S問題は解説を読んでもTLEをなくせずアドベコンはR問題までしかコンテスト期間中には解くことができませんでしたが、コンテスト終了後も頑張り続けて何とかS問題を攻略できました！

S問題を解けた時はとても嬉しかったです。writerさんやtesterさんを始めとして様々な上級者に助言をいただけた上でも結局想定解でTLEをなくすことはできなかったのですが（恐らくAtCoderLibraryやLibraryChecker上位アルゴリズムのような洗練された高速フーリエ変換の実装が必要で、自前の高速フーリエ変換を何度定数倍改善しても到底間に合いませんでした）、自分なりに解法を考えて全くの別解を生み出して解き切った時の爽快感は格別でした。

ちなみにS問題にはK色問題ととても似た思い入れがあります。K色問題は競技プログラミングの勉強を始めるきっかけとなった問題で、従ってK色問題に挑戦した時は競技プログラミングの知識が全くなく、しかも解説を読まずに自力で解くことに決めていたりとS問題に取り組んだ時と条件が全然違いましたが、どちらもタイルの塗り分け問題、どちらも定数倍改善が必須な問題、そしてどちらもものすごく苦戦した問題で、どちらも解くのに１ヶ月掛かりました！　これら２問は永劫忘れることはないでしょうねえ。