ARC 081 E - Don't Be a Subsequence
問題概要
英小文字から成る文字列Sが与えられる.
Sの部分列でないような最短の文字列を求めよ.
ここでS'がSの部分列とは S'[i] = S[a_i] (1<=i<=|S'|) なる単調増加なa_iが存在するものとする.
解法
まず,S[i,N)で一番最初に出てくる文字j(j='a'〜'z')を後ろから見て行き,c[i][j]とする.
dp[i] := S[i,N) の条件を満たす文字列の最短長さ とすれば,
先頭にjを使って文字列を作る場合は dp[c[i][j]+1]+1 となるから
dp[i] = min_j( dp[c[i][j]+1] + 1) で後ろから遷移していけば求められる.
c[N][j] = N, dp[N] = 1, dp[N+1] = 0 に注意する.
もうその文字がない場合はi=Nとし,それに対応するのがdp[N+1] = 0,
また空文字列に対する答えは'a'としてdp[N] = 1.
dp[i] が求められれば前から dp[i] = dp[c[i][j]+1] + 1であるようなjをaから見て行き,
そのようなjを連結して出力すれば良い.
メモ
文字列に関するDPに不慣れだったのと,逆に辿っていくのに時間がかかった.
