FFC001
解説は書く気力がないから感想だけ. fastestを取りたかったので後ろから見ていった.
Fを見る.むずい何もわからないので5分くらいで切り上げてに行く.
Eは問題の理解に少し時間がかかる.全域木だね,gcd見ればよさそうだねですぐ解ける.
D.方針はすぐに見えるがDPを合わせるのが難しい.途中でFとmodが違うのに気づくが合わない.こういう時は深呼吸して...も合わないが,突然合ってACする.
C.むずい.いろいろ考えてなぜか木の直径-1をひねり出す.WAが出てやっと葉以外に操作をするだけだと気づく.コーナーケースに気が付いていただけにもったいない.
なんとなくAに行く.ギャグっぽいなと思いつつ分からないのでBに行く.Wavelet Tree作りたいなと思いつつ簡単枠なので適当に実装してAC.
Aをちょっと考えると対称な位置を選ぶのが強そう.よっぱりギャグだった.ヒカルの碁を思い出した.
残り50分ぐらいFに費やす.そもそも期待値DPが苦手すぎるのでやり方を調べたりしていた.これを思い出して銀冠レベルか?と思ったけどさすがに違った.副産物としてこっちの方のとっかかりがつかめたかもしれないので後からじっくり考えたい.
分割数が小さいのが意外だった.Wikipediaに漸近式として, $$\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}}$$ が乗ってた.やば.
面白かったです.次回があるのかわかりませんがふもふも君がWriterのコンテストには積極的に出たいなと思いました.