Typical DP Contest

Updated: 2013-09-01

Source codes

Solutions

断らない限り全て $0$-indexed とする。

G - 辞書順

$L = \lvert S \rvert$ とする。 $S$ の最初の文字として空文字を挿入し、全部で $L + 1$ 文字とする。

$DP[i] = i$ 文字目を先頭に必ず使って $S$ の部分文字列を作る方法の総数。
$pos[i][j] = i + 1$ 文字目以降で初めて文字 $j$ が現れる位置。ただしそういうものがない場合は $-1$ とする。

まず $pos$ を計算する。初期状態 $pos[L][j] = -1$ for $j = 0, \dots, 25$ とする。 $i = L-1, \dots, 0$ に対し、 $pos[i][j] = pos[i + 1][j]$ とし、その後 $pos[i][S[i]] = i + 1$ と上書きする。これで $pos$ は計算が完了する。

次に $DP$ を計算する。初期状態は $DP[L] = 1$ である。 $i = L - 1, \dots, 0$ に対し、 \[ DP[i] = 1 + \sum _ {0 \leq j < 26, pos[i][j] \geq 0} DP[pos[i][j]]. \] とする。これで計算が完了する。

問題の答えだが、今回の実装では空文字列が辞書順最初の文字列となるので、まず $K$ をインクリメントしておく。 $DP[0] < K$ ならば答えは Eel である。そうでないならば $i = 0$ とし、 string ans = "" として、次に使う文字を決定する。つまりまず K--; とする(今見ている文字は使う)。ここで $K = 0$ ならそこで終了。次に $j = 0, \dots, 25$ に対し $K > DP[pos[i][j]]$ ならば $K \gets K - DP[pos[i][j]]$ とする。そうでないならば文字 $j$ を使用するので $i \gets pos[i][j]$, $ans \gets ans + j$ とする。これを繰り返す。これで答えがでる。