AtCoder Regular Contest 081 E - Don't Be a Subsequence

http://arc081.contest.atcoder.jp/tasks/arc081_c

問題概要

文字列Sが与えられる。Sの部分列ではないような文字列のうち、最も短いものを求めよ。答えが複数ある場合には辞書順で最小のものを答えること。文字列はいずれも英小文字のみからなるものとする。

|S| <= 2 * 10⁵

解法

Sに含まれていない文字がある場合にはその中で辞書順最小の1文字を答えればよい。もし26文字すべてがSに含まれているなら、少なくとも2文字は使う必要がある。ここで仮に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;
}