帰着関連2
前回帰着訓練は一気にいくつもの問題のページを作ってしまったが、Scrapboxでそれをやると後で大変だということがわかった ページをたくさん作るのではなく、全部入りの大きなページを作ってから分割していくほうが良いかな
前回はAtCoder Problemsのレコメンデーションを使った
だけど帰着訓練ではACにしないため、リストのトップに残り続けて不便
結局のところ僕は青色の問題を解けば良いようなのでABCなどの青色問題を端から解いていく方が良いのでは
AGCを新しい順にやるかな
文字列対にそれぞれ判定しても間に合わない
各文字列になんらかの処理をしたらそれだけで求まる仕組みが必要
文字列長の総和が10^6で抑えられてる
一致する文字列対とは
短い方の長さをnとした時に、末尾n-1文字が一致して、残り1文字がどちらにも含まれてる
あらかじめ短い順にソートしておき、n-1文字一致したら26文字の配列にフラグを立てておき、その文字が出てきた時点で解をインクリメント
「n-1文字一致」をどうやるか
トライ木に入れていく？
その方針で良いらしいが、ローリングハッシュという手もあるらしい
1ステップで「すべての値が0〜2」になる
最後が2になるのは全部0で片端が2のものだけ
2は隣に0がないと維持されない、一般的に割とすぐ消える
とはいえ消えない時もあるからどうしたものか