ABC416のC問題 Concat (X-th)

At_coder, Python
目次

AtCoder Beginner Contest 416のC問題 Concat (X-th)は、コンテスト参加時には回答できなかった。二分木を使って解くのかと頑張ってみたが、コンテスト終了後に解説を読んでズッコケた。

C - Concat (X-th)

問題：C - Concat (X-th)

\(N\)個の文字列\(S_1,S_2, \cdots, S_N\)が与えられる。これを\(K\)個組み合わせて、ソートする。そして、ソート結果から指定の順位の文字列を回答する問題。

考え方

一般的に全ての組み合わせを作ることは制限時間を超えてしまう。そこで何らかの工夫が必要になる。

しかしこの問題は、制約が

  • \(1 \le N \le 10\)
  • \(1 \le K \le 5\)

となっているので組み合わせは最大で\(10^5\)となる。そこで、何も考えずに全ての組み合わせを実際に作成して、そのソート結果から目的の順位の文字列を得る。

理解

今回の問題は二分木を使うのだと考えたが、解説を読むと、全ての組み合わせを実際に作成すると正解できるとのこと。

この解説を読んでヤラレタと思いました。

この問題の核心は、アルゴリズムではなく計算量の見積もりだったのです。制約から組み合わせは最大で\(10^5\)です。この量ならば、力技で全ての組み合わせを作成してソートしても制限時間に収まることを見抜くことが必要だったのです。

N, K, X = map(int, input().split())

S = []
for _ in range(N):
    S.append(input())

words = S
cat = 1
while cat < K:
    next_words = []
    for w in words:
        for ww in S:
            next_words.append(w + ww)
    cat += 1
    words = next_words
words.sort()
print(words[X-1])

参考サイト