ABC353E - Yet Another Sigma Problem

本番めっちゃ詰まって困りました。

解法

をソートしておくと、どの文字列も隣の文字列とのLCPの長さが最大になる。
をソートしたあとの列について、隣の文字列とのLCPの長さを順にメモした配列をとしておく。

問題で求められているのはすべての文字列の組み合わせでのLCPの長さの総和なので、前から文字列を走査して、以前に出現した文字列とのLCPの長さの総和を求めればよい。
を用いると、を前から走査して、以前の要素の累積minの総和を取れば、答えを求めることができる。

どうやって累積minの総和を求めるかだが、スタックと累積和のメモ用の配列を用いることができる。
スタックの要素は下から上に向けて狭義単調増加であるようにし、各要素が列にいくつ含まれるかも管理する。

新たなの要素をpushするときには、

1. 初め、の個数をとする。
2. スタックの最上位の要素と比較し、もしのほうが小さいならスタックをpopし、popした要素の個数をの個数として足し込む。
3. 2.をより小さな要素が出るまで繰り返し、最後にの個数と一緒にスタックにpushする。
4. 累積和配列をとその個数を利用して書き換える。

とすることで、累積minとその総和を管理できる。

提出例は以下の通り。
Submission #53355147 - AtCoder Beginner Contest 353

計算量はソートがボトルネックになりそうですが、この場合どうやって計算量表記するんですかね？とか？

その他の解法

前から1文字ずつソートするような感じで、再帰的にLCPの長さと組み合わせの個数を求めることもできます。
これものソートと同じ計算量だと思います。(提出例：Submission #53386949 - AtCoder Beginner Contest 353)

Rolling Hashを用いることもできます。すべての文字列について、長さからまでのハッシュ値を長さごとにメモしておけばよいです。
計算量はだと思います。(提出例：Submission #53392710 - AtCoder Beginner Contest 353)

トライ木を用いるのもすぐ思いつける方法ですが、ライブラリ持ってないし実装するのも面倒くさかったので、本番ではパスしました。
実装が面倒くさかったので、提出例はありません。

おわりに

Rolling Hashの解法を思いつけなかったのはめちゃくちゃ痛かったです。Rolling Hashは選択肢にはあったんですが、各長さのハッシュ値持ったら空間爆発するだろって思っていました。アホです。

とはいえ、実際コンテスト後にRolling Hashの解法書いてみたら、なんとびっくりハッシュ値の型にHashもOrdも実装されてないし、内部的なu64の値も取り出せない始末…
解法の内容的にどれかはできないとダメなのにまさかどれもダメとはたまげました。ライブラリ整備のいい機会になりました。