UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) F 問題メモ

UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)

5完速解きで橙Perfが出る回

F - String Cards

問題

$N$ 個の英小文字列 $S_1,S_2,...,S_N$ が与えられる
ここからちょうど $K$ 個を連結してできる文字列のうち、辞書順最小のものを求めよ
$1 \le K \le N \le 50$
$1 \le |S_i| \le 50$

解法

なかなか気付きづらい。

基本的には辞書順の小さい文字列から頭に持っていくのが良さそうだが、 bba と bbaa のように一方がもう一方のprefixになっているような場合に狂う。

bba と bbaa を繋げる場合、bbaa + bba の方が小さい
bba と bbaa から1つだけ選択する場合、bba の方が小さい

さらに bbaaa などが加わり、prefixが多重的になってくると、訳がわからなくなる。

優先度

使う文字列を固定した場合、どの文字列を優先的に先頭に持ってきたらよいかは、実は1つの指標だけで判断できる。

bbaa は bba よりも（この2つを繋げるなら）優先的に前に持ってきた方が良い。
これを「bbaa は bba に比べて優先度が高い」ということにする。

また bbaaa と bbaa を比べると、優先度は bbaaa の方が高い。

この時、bbaaa と bba は直接比較していないが、 bbaaa > bbaa かつ bbaa > bba なら、必ず bbaaa > bba となるのである。

公式editorialにもあるが、以下のように証明できる。

$S_i,S_j$ を26進数としてみる。ただし $|S_i|,|S_j|$ は文字列としての長さとする。

この2つを文字列として繋げた時の辞書順は、桁数は同じなので $S_i*26^{|S_j|}+S_j$ と $S_j*26^{|S_i|}+S_i$ の数値的な大小比較で判断できる。

$S_i*26^{|S_j|}+S_j \le S_j*26^{|S_i|}+S_i$ を整理すると $\displaystyle \frac{S_i}{26^{|S_i|}-1} \le \frac{S_j}{26^{|S_j|}-1}$ となり、単独の $S_i$ だけから計算できる指標によって文字列の優先度が判定できることがわかる。

実際には $S_i$ や $26^{|S_i|}$ はとても大きくなるのでそのまま指標とすることはできない。

（$S_i$ を文字列の扱いに戻して）「$S_i + S_j \lt S_j + S_i$ なら、$S_i$ の方を小さいと見なす」という比較関数でソートする。

または、多倍長整数の分数を扱えるモジュール等がある言語ならば、指標をそのままソートできる。

採用する $K$ 個

優先度はわかった。

ただしこれはあくまでも全て繋げる場合なので、前述の通り $K$ 個だけ使うとなれば優先度的には後でも短い文字列の方が有利になることがある。

DP的なことを行うことになる。
その際、優先度の高い方から（先頭から）確定させていきたくなるが、それだと上手くいかない。

×: $DP[i][j]=i$ 番目に優先度の高い文字列までのうち $j$ 個を使って、辞書順最小の文字列

なぜなら、$S_i$ を使うか使わないかは $S_{i+1}$ 以降に依存する。

$S_{i+1}$ 以降を組み合わることで、「全体で $K$ 個になるように選んだときに $S_i$ とprefixが同じでより短い文字列が作れる」場合、 $S_i$ は使うべきでないことになる。

5 4
bababaaa
bababaa
ba
ba
b

bababaa は優先度2位だが、
それ以降の ba ba b を使った方がより短いのができる。
↓
bababaaa ba ba b が最善

5 4
bababaaa
bababaa
ba
b
b

bababaa 以降では、全体で4個使いつつprefixが同じものを作れない。
↓
bababaaa bababaa ba b が最善

なので、先頭から決めることはできない。

逆に、優先度が低い方から決めると、こちらは上手くいく。

$DP[i][j]=i$ 番目に優先度の低い文字列までのうち $j$ 個を使って、辞書順最小の文字列

これはなかなか気付きづらい。

Python3

from fractions import Fraction
from operator import itemgetter

n, k = map(int, input().split())
ttt = []

ord_a = ord('a')

for i in range(n):
    s = input()

    t = 0
    for c in s:
        t = t * 26 + ord(c) - ord_a
    f = Fraction(t) / Fraction(pow(26, len(s)) - 1)
    ttt.append((f, s))

ttt = list(map(itemgetter(1), sorted(ttt, reverse=True)))

dp = ['']

for t in ttt:
    if len(dp) <= k:
        dp.append(t + dp[-1])
    for i in range(len(dp) - 2, -1, -1):
        dp[i + 1] = min(dp[i + 1], t + dp[i])

print(dp[k])

もしくは、制約が小さいので、以下でも通った。

とりあえず優先度の高い順に並べる
各 $S_i$ について、それを除いて残りを繋げた文字列を作る
作られた文字列の中で一番辞書順が小さくなる時に除いた $S_i$ を除く
残り $K$ 個になるまで繰り返す

目次

UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) F 問題メモ

F - String Cards

問題

解法

優先度

採用する $K$ 個