Xmas Contest 2019 J: Sub-Post Correspondence Problem

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_j

問題概要

文字列 が与えられるので，ある () に対して が の連続とは限らない部分列となるようにできるか判定せよ (一応，同じ添え字は 回まで)．

解法

カード 枚での解 () があれば YES でなければ NO です．なぜなら， が の部分列ならば， が の部分列であるか が の部分列であるかだからです ( と の境界に対応する場所は と の高々一方にしか入ってこないので)．

のときの判定は， の文字を 文字ずつ， の中に貪欲にとっていけば線型時間でできます．

統計情報

正解者：siotouto さん (0:13:54) はじめ 95 チーム

コメント

ギャグ枠です． はフェイクです．

Post の対応問題は決定不能な問題の中でもパズルっぽい見た目ということで人気があります (?)．問題設定を少し変えた亜種は結構研究されているらしく，決定不能と決定可能の間が見えてくるのが面白いですね．