AtCoder Regular Contest 081 E - Don't Be a Subsequence
http://arc081.contest.atcoder.jp/tasks/arc081_c
問題概要
文字列Sが与えられる。Sの部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。
|S| <= 2 * 105
解法
Sに含まれていない文字がある場合にはその中で辞書順最小の1文字を答えればよい。もし26文字すべてがSに含まれているなら、少なくとも2文字は使う必要がある。ここで仮に1文字目に文字αを選択した場合、「文字αが最初に現れるインデックス+1」までジャンプしてまた再帰的に同じ問題を解くことになる。ゆえに「文字αがi文字目以降で最初に現れる場所」を前計算で求めておけば、あとはDPで解くことができる。
形式的には
next(i, α) = i文字目以降で文字αが初めて登場するインデックス
とすると、以下のDPで最短の文字数を求めることができる。
(ただしSのi文字目以降に出てこない文字が存在するとき, dp(i) = 1)
具体的な文字列はdpのminを取るとき文字も一緒に記録しておけば最後に復元できる。
感想
最近たまたま解いていたTDPCの辞書順と同じようなやり方で出来た。部分文字列構築の典型手法と言える?
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { auto S = readln.chomp; auto N = S.length.to!int; auto next = new int[][](26, N); foreach (i; 0..26) fill(next[i], -1); foreach (c; 0..26) { for (int i = N - 1; i >= 0; i--) { if (S[i] - 'a' == c) { next[c][i] = i + 1; } else if (i < N - 1) { next[c][i] = next[c][i+1]; } } } auto mem = new Tuple!(int, int)[](N); fill(mem, tuple(1 << 29, 1 << 29)); Tuple!(int, int) dfs(int n) { if (n == -1) return tuple(0, -1); if (n >= N) return tuple(1, -1); if (mem[n][0] != 1 << 29) return mem[n]; auto ret = tuple(1 << 29, 1 << 29); foreach (i; 0..26) { auto t = dfs(next[i][n]); if (t[0] < ret[0]) ret = tuple(t[0], i); } mem[n] = tuple(ret[0] + 1, ret[1]); return mem[n]; } dfs(0); string ans = ""; for (int i = 0; i != -1;) { if (mem[i][1] == -1) break; char c = (mem[i][1].to!char + 'a').to!char; ans ~= c; i = next[c - 'a'][i]; } ans.writeln; }