【競プロ典型 90 問】006 - Smallest Subsequence

米田氏が企画した「競プロ典型90問」を解いていきます。

ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。競プロ初心者なのでどうか温かい目で見守ってください。

なお、本記事中のPythonコードはブラウザ上で実行可能です。よろしければ遊んでいってください。

問題

kyopro_educational_90/006.jpg at main · E869120/kyopro_educational_90

やってみよう！

テストデータ・テスト関数定義　↓

# 縮小表示 test_data = [ { "in":[7, 3, 'atcoder'], "out": "acd" },{ "in":[14, 5, 'kittyonyourlap'], "out": "inlap" } ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

下のmain0関数を完成させて「Run」ボタンをクリックしよう！

def main0(N, K, S): pass test_all(main0)

自由欄

try(1st.)

愚直に解いてみます。

def main(N, K, S): # index:1~Kにansを作る文字のNでのインデックスを格納する idx = [-1] for k in range(1, K+1): char = "~" for i in range(idx[k-1] + 1, N - (K-k)): if S[i] < char: char = S[i] w_i = i idx.append(w_i) return "".join([S[i] for i in idx[1:]]) test_all(main);

結果

一個だけTLE…！
提出 #32635326 - 競プロ典型 90 問

try(2nd.)

速度改善に資するかは微妙ですが、内側のループの代わりにminとindexで次の文字を探してみます。

def main(N, K, S): # index:1~Kにansを作る文字のNでのインデックスを格納する idx = [-1] chars = list() for k in range(1, K+1): begin = idx[k-1] + 1 end = N - (K-k) char = min(S[begin:end]) i = S.index(char, begin, end) chars.append(char) idx.append(i) return "".join(chars) test_all(main);

結果

お、AC！やったー
提出 #32651671 - 競プロ典型 90 問

解説・想定コード

一応、解説も見てみます。
すると先程の達成感もつかの間、私の実装では本来TLEとのこと…。とほほ。

kyopro_educational_90/006.jpg at main · E869120/kyopro_educational_90

想定コード

kyopro_educational_90/006.cpp at main · E869120/kyopro_educational_90

ちょっと解説が何言ってるのか分からないのでコードを見ます。
Pythonで書き換えたのが以下。

def main(N, K, S): '''想定コード(下記URL)参照 https://github.com/E869120/kyopro_educational_90/blob/main/sol/006.cpp ''' # 前処理 nex = [[N]*26] for i in range(N-1, -1, -1): a = nex[-1].copy() a[ord(S[i])-ord("a")] = i nex.append(a) nex = nex[::-1] # 一文字ずつ貪欲に決める ans = [] curr_pos = 0 for i in range(K): for j in range(26): nex_pos = nex[curr_pos][j] if N - nex_pos >= K-i: ans.append(j) curr_pos = nex_pos + 1 break return "".join([chr(ord("a")+c) for c in ans]) test_all(main)

結果

提出 #32641757 - 競プロ典型 90 問

は、早い！
上の自力コードでは最大1005msだったものが、120msにまで短縮されました！！

解説の理解

コード全体を見るとようやく理解できました。これ思いつく人、天才かよ。

というより、どうやら頻出のパターンのようです。

この配列は極めて汎用性が高いので、実にさまざまな問題で活用できます！！！

いっそライブラリ化しても良いように思います。
競プロ典型 90 問 006 - Smallest Subsequence（★5） - けんちょんの競プロ精進記録

とは言え、初見ではなかなか分かりづらいので、以下順を追ってみていきます。

各index以降で各文字が最初に登場するindexを格納する配列

やはり言葉だとなんのこっちゃ、となりますので例のkittyonyourlapで確認します。

N, K, S = test_data[1]["in"] N, K, S nex = [[N]*26] for i in range(N-1, -1, -1): a = nex[-1].copy() a[ord(S[i])-ord("a")] = i nex.append(a) nex = nex[::-1]

nex配列を見てみましょう。

# 縮小表示 import string import pandas as pd pd.options.display.max_columns = 30 import jinja2 # DataFrame.styleを扱うのに必要。pyodideでは明示的にimportしなければならない df = pd.DataFrame( nex, index=[f'S[{i:}]: {c}' for i, c in enumerate(S)]+[""], columns=list(string.ascii_lowercase)) df.style.set_table_attributes('class="dataframe"').set_td_classes(pd.DataFrame( [[None]*i+["updated"]+[None]*(25-i) for i in [ord(c)-ord("a") for c in S]]+[[None]*26], index=df.index, columns=df.columns) ).set_table_styles( [{ 'selector': '.updated', 'props': [ ('color', 'red'), ('font-weight', 'bold') ] }] )

最終的にnexのサイズはN+1になりますが、nex[N]は作成時(の最初の1回)のみ参照されます。
Sの後ろから見て、nexの下の行から埋めていきます。

S[13]: pなので、nex[13]のpの位置(13)に13を入れます(偶然Sのインデックスと文字のインデックスが一致して分かりづらいです)。他の値はnex[14]と同じです。
続けてS[12]を見るとaなので、nex[12]のaの位置(0)に12を入れます。

・・・ということを繰り返すと、『各index以降で各文字が最初に登場するindexを格納する配列』が出来上がります。

貪欲法

今回の場合では辞書順に(アルファベットの"a"から)探索し、条件を満たせば採用する点が貪欲法なんでしょう。
そして条件というのが、「その文字($S_i$)を採用した場合、$S_{i+1}$文字目以降で最終的に長さ$K$の文字列を作れるか」ということになります。

コードに沿って考えてみます。

ans = [] curr_pos = 0

まずnex[0]を見ます。この時点ではまだ文字を選んでいないので、採用できる文字の$S$におけるインデックスは9以下となります。
nex[0]を右から(辞書順に)探索して初めて9以下になるのは"i"なので採用します。

# for i in range(K): i = 0 for j in range(26): nex_pos = nex[curr_pos][j] if N - nex_pos >= K-i: ans.append(j) curr_pos = nex_pos + 1 break "".join([chr(ord("a")+c) for c in ans])

次に、"i"のインデックスを一つ進めたnex[2]を探索し、10以下になるものを探します。
$S[6]$で"n"を見つけたので採用します。

# for i in range(K): i = 1 for j in range(26): nex_pos = nex[curr_pos][j] if N - nex_pos >= K-i: ans.append(j) curr_pos = nex_pos + 1 break "".join([chr(ord("a")+c) for c in ans])

今度はnex[7]で11以下になるものを探索し・・・ということをK回繰り返せば答えが得られるというわけです。

for i in range(2, K): for j in range(26): nex_pos = nex[curr_pos][j] if N - nex_pos >= K-i: ans.append(j) curr_pos = nex_pos + 1 break "".join([chr(ord("a")+c) for c in ans])

まとめ

今更ながら、アルゴリズム、奥が深い。
今回の解法って一般化して活用することはできるんだろうか？🤔