006 - Smallest Subsequence（★5）の解説

何の話かと言うと

上記の問題をネタに「ギリギリ間に合う系」、もしくは、「より一般にはもっと多くの種類で考えてもよさそうなのに、なぜか具体的な少数のものに限定されている」系の話をします。

実行時間の見積もり

PyPy3 での実行時間を調べてみます。

for _ in range(10**9):
  pass

# 902 ms

for _ in range(10**10):
  pass

# 8416 ms

これより、制限時間 2s の問題であれば、 $10^9$ 回のループまではなんとか間に合うことがわかります。

素朴な解法

例えば、4 文字の部分列を作るのであれば、最初の文字は、

・文字列 S の最後の3文字を除いた中で、最も小さい文字

を選びます。

・2文字目は、

・文字列 S の 1 文字目を選んだ場所より後ろで、最後の2文字を除いた中で、最も小さい文字

を選びます。

つまり、検索の末尾を1文字づつ増やしながら、直前に選んだ場所以降で最小の文字を選ぶ操作を繰り返せばOKです。

これを実装するとループの回数はいくらになるでしょう？

全部で K 文字選ぶので、K 回のループがあります。

次に、それぞれのループの中で、文字列 S に対する最小文字の検索をします。最悪ケースで N-K 文字を検索するので、N-K 回のループになります。（最後の K 文字を除く事と、検索の末尾が増えると同時に検索の先頭も後ろに移動する事を考えてください。）

というわけで、全体として、 $K\times (N-K)$ 回のループになります。

計算量の正確な見積もり

$1\le K\le N\le 10^5$ という条件があるので、上記の計算量を大雑把に $10^5 \times 10^5$ と考えると、 $10^{10}$ でアウトになります。

なのですが、厳密に、 $K\times (N-K)$ を計算すると、 $1\le K\le N$ という条件があることから、この値は $K=N/2$ で最大値 $N^2/4$ を取ります。つまり、正確なループ回数は最大で $10^{10}/4 = 10^9 \times 2.5$ に抑えられます。

$10^9$ 回で 900ms という結果を考えると、ギリギリ感はありますが、試してみる価値はありそうです。

atcoder.jp

結果は、最遅ケースで 1778ms、なんとかセーフでした！

より効率的な解法

さきほどの素朴な解法は、次の様な本当の最悪ケースを手で作ると TLE になります。

  N = 10**5
  K = N//2
  S = ['a'] * N

これでもパスできるための効率化は、「アルファベットは26文字」という特殊性を利用して、

・a が選べるかチェック
・b が選べるかチェック
　 $\vdots$
・z が選べるかチェック

という（ある意味愚直な）確認を繰り返します。具体的には、k 文字目を選ぶ際に「直前に選んだ場所以降でアルファベット X が最初に存在する位置 index」を検索して、index が後ろ過ぎなければ（残り m 文字選ぶのであれば、末尾から m-1 文字目までは選べない）これを採用する、ということを繰り返していきます。

・「直前に選んだ場所以降でアルファベット X が最初に存在する位置 index」

については、事前に DP で準備ができます。

  dp = {} # dp['a'][n] # n 文字目以降で最初に a が来る位置
  for o in range(ord('a'), ord('z')+1): # O(26*N)
    tmp = [-1] * (N+2)
    for n in range(N, 0, -1):
      if S[n] == chr(o):
        tmp[n] = n
      else:
        tmp[n] = tmp[n+1]
    dp[chr(o)] = tmp