7K12 blog

猫でも分かる何か

ARC154-B New Place (400) diff1027


本質

  • 逆順テク
  • SSS(単純部分列)の判定はtwo-pointers的な累積テクでO(N)
  • 一箇所に集めて分配

詳細


「Sの先頭の文字を任意の箇所に挿入できる⇒Sの後半の文字列がTの部分列」が一致できる条件になる。先頭の文字を一箇所に集めて分配するイメージを持つと先頭の文字しか移動できないので後半が不変という性質になり、それを判定すれば良いので逆順テクを使って処理すれば楽になって嬉しいかもしれないという気持ちになる。SSSの判定はtwo-pointers的な累積処理で判定できてO(N)

感想

逆順テクは考察できていたけど、SSS判定が累積テクでO(N)の知識が曖昧だったかもしれない