結果

問題 No.3626 Not a Prefix
コンテスト
ユーザー 👑 loop0919
提出日時 2026-08-10 23:19:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,213 ms / 2,000 ms
+ 314µs
コード長 1,912 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 230 ms
コンパイル使用メモリ 95,720 KB
実行使用メモリ 831,140 KB
最終ジャッジ日時 2026-08-14 20:52:44
合計ジャッジ時間 10,758 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

sys.setrecursionlimit(10**6)


N, M = map(int, input().split())
S = [input() for _ in range(N)]

limit = N - M

# children[v][c] := 頂点 v から文字 c で進んだ先
children = [{}]

# same[v]:
# 頂点 v に対応する文字列と等しい S_i の個数
same = [0]

# super[v]:
# 頂点 v に対応する文字列を接頭辞として持つ S_i の個数
super_ = [0]


# Trie を構築する
for s in S:
    v = 0

    for c in s:
        if c not in children[v]:
            children[v][c] = len(children)
            children.append({})
            same.append(0)
            super_.append(0)

        v = children[v][c]
        super_[v] += 1

    same[v] += 1


path = []


def dfs(v, sub):
    """
    v に対応する文字列を prefix とする部分木を辞書順に探索する。

    sub:
        S_i のうち、現在の prefix の接頭辞となっているものの個数。
    """

    for c in "abcdefghijklmnopqrstuvwxyz":
        # この文字の子が Trie に存在しない場合
        if c not in children[v]:
            # X = prefix + c とすると
            # super_X = same_X = 0, sub_X = sub
            if sub <= limit:
                return "".join(path) + c

            continue

        u = children[v][c]
        new_sub = sub + same[u]

        # この頂点以下では、少なくとも new_sub 個の S_i が
        # X の接頭辞になるため、条件を満たせない。
        if new_sub > limit:
            continue

        path.append(c)

        # u 自身を X とする場合
        bad = super_[u] + new_sub - same[u]

        if bad <= limit:
            return "".join(path)

        # u の子孫を探索する
        ans = dfs(u, new_sub)

        if ans is not None:
            return ans

        path.pop()

    return None


ans = dfs(0, 0)

if ans is None:
    print("No")
else:
    print("Yes")
    print(ans)
0