yukicoder contest 417

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 417 Eまで。
B Q秒後増えているか見るのが基本。そこまででZeroやOverflowがおきないかチェック。
C mod X+Yで分類。Aの人数-Bの人数でソート
D 不等式の評価。イコールのない不等号を評価するとき、-epsするのを忘れてWA。
E DP

— titia (@titia_til) February 9, 2024

No.2626 Similar But Different Name

　解説AC。

　ローリングハッシュ（など）を使えば大文字小文字の違いを区別しない場合の一致できるかは判定できる。問題は、大文字小文字が異なる箇所が1文字以上K文字以下という方。bisetか？　と思ったが、あまり時間に余裕がなさそうで止まってしまった。

　FFTを使うとは思いつかなかったが、言われてみると典型っぽいので、この手法は覚えておきたい。SとSより短いTに対して、Sの全ての連続部分列とTを比較するときにFFTは使える。

　ただ、FFTを使うとしても、使い方がすぐには思いつかなかった。色々な解法ツイートを見て、大文字=1、小文字＝-1とするのが分かりやすく感じ、その方法でACした。