ferinの競プロ帳

競プロについてのメモ

ARC 081 E - Don't Be a Subsequence

問題ページ
arc081.contest.atcoder.jp

解法

まず、dp[i] = (区間[i, s.size())の部分文字列に含まれない最短の文字列の長さ)としたDPを考える。文字cがi番目以降ではじめて現れる位置をnext(i, c)と表記することにすると、このDPはdp[i] = min{dp[next(i, c)+1]} + 1 と書け、後ろから順に求めていくことが出来る。dp[0]が求めるべき答えの文字列の長さとなる。next(i, c)は各文字種の出て来るインデックスを記録してソートしておくことで二分探索を用いて高速に求めることができる。
このDPの復元を行い、辞書順で最小のものを求める。
dp[i] == dp[next(i, c)] + 1 を満たすcの中で、もっとも小さいcを用いる。次に、i = next(i,c)+1としてこれを繰り返し行うことで答えを求められる。

例として、文字の種類をa,b,cの3種類としたものについて考える。
まず、dp[i]を求めていく。後ろから順に文字列を見ていき全ての文字種が現れるごとにdpの値を+1していくことでもこのDPの計算を行うことができる(詳しくは公式の日本語解説を見てください)。次にDPの復元を行う。i=0でdp[i] == dp[next(i, c)] + 1となる文字cは'b'と'c'の2種類で、辞書順最小とするため小さいbを選ぶ。i=next(0,'b')+1=2として同様に計算していく。最後にdp[i]=1のときは、i番目以降に現れない文字のうち最小となる文字を答えとなる文字列に加えればよく下の例ではbとなる。これは二分探索を用いて十分高速に計算できる。
f:id:ferin_tech:20170821051243p:plain