アドベコン 25 日出題分 感想
出題前
Twitter で LCP という文字列が流れてきたのでこれで原案を作った.
基本的なアイデアは複数の文字列の LCP の長さが隣接の min になるというもの(文字列をいっぱい並べればよさそう,という安直な考え).
そして第一稿,区間 LCP の長さが K 以上になるものの個数を数えさせようと思ったのだが簡単すぎるということで reject.ということで総和にしたのだが,そのままだとただの数列で良いなという気持ちになったので区間長を掛けさせた.まあ,数列だとほぼ既出だし,コピペ改変で通るだろうのでゆきこ以外には投げられないな,とも思った.
もともと解説に書いてある解が$ \Theta(N^{1.5})だと考えていたのだが,最悪ケースがなかなか作れないことからもう一度考え直すと $ \Theta(S)であることに気づいた.一応$ \Theta(N^2)を落とすために制約を少し大きくしたのだけれども,もしかしたら通ってしまっているかもしれない.python3/pypy3 で$ \Theta(S)が通ることは確認したが$ \logがついても通るかどうかは確認していない.
出題後
クリスマスコンの直後かつコドフォの直前だったためか人が少なかったっぽい.
クラーは一度も飛んでこなかった,これは結構嬉しい.問題文も読みやすかっただろうか,問題文の理解を確実にするためにサンプルの説明を充実させてみたのは良かっただろうか.
あとは思ったよりみんな WA しないのだなぁと感じた,想定解のオーダーで解いている人よりも $ \Theta(N\log N)などのオーダーで解いている人の方が多かったように見える.気が向けば $ \Theta(S) 解法も書いてみてほしい(5 倍速くらいにはなると思う).
余談,今回登場した VOICEROID は 4 人でした.探してみてね.