https://storage.googleapis.com/icpcsec/2018-regional/problems_all.pdf
'0'と'1'のみで構成された2つのbit列$S,T$が与えられる。$S,T$どちらの部分列でもないようなbit列のうち、最短かつ辞書順最小のものを求めよ。
DPテーブルを $$DP[i][j]={\rm Sのi文字目以降とTのj文字目以降の最小共通非部分列の長さ}$$ とすると、tech008の要領で更新ができる。
もし、$S,T$の最小共通非部分列が0から始まるならば、それは「'0'+"Sにおいて最初に0が現れる点の次の文字以降とTにおいて最初に0が現れる点の次の文字以降の最小共通非部分列"」になる。1から始まる場合も同様であって、2つのうちで短いほうが答えである。このようにしてDPテーブルを更新すると最小共通非部分列の長さがわかるので、最後に構築すればよい。
これを構築するためには、0と1のうち「DP[Sで次に0 or 1が現れる場所の1つ後ろ][Tで次に0 or 1が現れる場所の1つ後ろ]」がより小さい方に飛ぶことを繰り返せばよい。
ジャンプを繰り返すと、大抵の場合に片方の文字列が先に終了する。その場合の処理は結構難しい。
これは僕が解かないといけない問題だった……。