Typical DP Contest

Updated:

Typical DP Contest

Source codes

Solutions

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

A - コンテスト

ポイント

B - ゲーム

ポイント

C - トーナメント

ポイント

D - サイコロ

ポイント

E - 数

ポイント

F - 準急

ポイント

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$ とする。これを繰り返す。これで答えがでる。

ポイント

$10^{18} + 10$ 以上の数は無限大として取り扱う。

H - ナップザック

ポイント

I - イウィ

ポイント

J - ボール

ポイント

K - ターゲット

ポイント

L - 猫

ポイント

M - 家

ポイント

N - 木

ポイント

O - 文字列

ポイント

P - うなぎ

ポイント

Q - 連結

ポイント

R - グラフ

ポイント

S - マス目

ポイント

T - フィボナッチ

だめぽ先生による完璧な解説が以下にある。

ポイント

線形漸化式に随伴する行列の特性多項式がアプリオリに得られることがポイントとなっている。これがわからないと解答に永遠にたどり着けないであろう。最も厳しいタイプの典型問題だと言える。

Others