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

相変わらずオムニバスコンテストの応募締め切り間際に空きがあった時にちょうどいい難易度勾配になるようにストックを放出することを生業としています。とはいえ今回で完全にストックが尽きてしまいました……。testerさんを随時募集中ですのでご協力よろしくお願いいたします。現在63問ありまして1問からのご応募大歓迎です。tester初心者の方も、ぜひ練習台にご活用くだだい。

さて今回はB,D問題のwriterですが、E,G,H問題のtesterもしています。8問中5問writer/testerを担当していることになるのでコンテスト中は解く問題が少なくなっちゃいますが、その分開催記に力を入れていこうと思います（？）

E問題は累乗数の全探索前計算問題ですね。競技プログラミングでは色んな全探索が問われますが、「像の疎な関数の像前計算」は結構忘れがちで実装の重い解法を選択してしまう失敗をしてしまいます。

この問題も例外ではなく、tester時は答え（$N$が何乗数か）の素因数分解を計算するまどろっこしい解法で解いてしまいました。ただでさえ実装が遅いので、軽い解き方ができるようにこの辺の典型をもっと身につけていきたいですね。

G問題はLISの計算問題でした。といってもtester時はLISなんて全く気付かず、式変形をゴリ押して区間minBITに帰着させました。

LISはあまり扱った経験がないので今後も考察漏れしやすそうですが、BITを貼って何とかなる問題は自作BITライブラリへの絶大な安心と信頼のおかげで気持ちよく解けるのが良いですね。なおRS対応自体は１回読んだことがある程度だったので、 Viennotの幾何的構成は未履修でした。勉強になりますね。

H問題は平衡二分探索木の応用問題でした。★3までのアルゴリズムしか履修していないので平衡二分探索木は持っておらず、自由加群＋平方分割によるメモリ削減テクで頑張りました。

自由加群は作用の遅延評価についてのみライブラリー化していたので値側の実装は今回初挑戦。無事実装できて良かったです。C++の平方分割、痒いところに手が届いてくれるので助かります。

とはいえこの解法だとPythonで通せないだろうし、平衡二分探索木を実装するのは残り時間的に厳しそうだったので、別解を考える必要がありました。Trie木ならライブラリー化していましたが自分の実装だとメモリが厳しそう、というわけで実装の楽そうな動的セグメント木と動的フェニック木に初挑戦してみました。

unordered_mapを使えばよいという前情報だけは持っていたのですが無事何も見ずに実装できて満足です（アルゴリズムのネタバレをなるべく避けようとしている派）。動的セグメント木ではMLEになってしまいましたが、動的フェニック木ではきちんと通せたので一安心。

結果的に自由加群、動的セグメント木、動的フェニック木の３つのライブラリーを同時に拡充できたので得るものの多いtester作業でした。

それでは参加者の皆様、testerしてくださった＆testerさせてくださった作問陣の方々、皆様ありがとうございました！　なおリアクティブコンも準備中です。お楽しみに！