結果 o o - -

提出 url

A

両端から1文字ずつ付き合わせていって4パターンで分岐。

1. ’*’ と ‘*’ なら OK
2. ’*’ と ‘[a-z]’ なら OK
3. ‘[a-z]’ と ‘*’ なら OK
4. ‘[a-z]’ と ‘[a-z]’ なら一致していれば OK そうでないなら NO

文字列長が奇数なら真ん中を省く。

B

貪欲にTiの小さいものから処理する。

実際にシミュレーションしてペナルティを計算する。

あとは階上どうしの掛け算をする。剰余の分配法則的なものはあまり知らないけど

ll bs = 1;
for (ll i = 1; i <= 10000; i++)
{
  bs = (bs * i) % mod;
  pw[i] = bs;
}

これで問題なかった。

C

最初のワーシャルフロイドはOKだけど、クエリ毎に打つことはできなくて けどO(V^2)でテーブル更新可能だった。解説スライドでたしかにという感じだった。気づかなかった。

無駄にワーシャルフロイドと更新部分のループをSIMDで描いたら200msくらい早くなった。

この記事にもあるように intrinsicsはSSE2まで使えるぽい。例にならってSSE4.1の_mm_min_epi32の代わりをインラインアセンブラで書いた。 AtCoder環境はどのバージョンのSIMDまでサポートしてるんだろう。

D

実際の値はいらないけどに大小比較をする場合は log が使えることを知った。

あと log(a*b)=log(a)+log(b) log(a/b)=log(a)-log(b) とか久しぶりだった。

BITの更新をするときに変位を足すのではなくて任意の値にしたい場合は負の加算でリセットすることでなんとかなることを知った。