結果
| 問題 | No.3626 Not a Prefix |
| コンテスト | |
| ユーザー |
 lif4635
|
| 提出日時 | 2026-08-14 23:06:49 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,157 ms / 2,000 ms |
| + 590µs | |
| コード長 | 8,699 bytes |
| 記録 | |
| コンパイル時間 | 226 ms |
| コンパイル使用メモリ | 95,980 KB |
| 実行使用メモリ | 700,096 KB |
| 最終ジャッジ日時 | 2026-08-14 23:07:05 |
| 合計ジャッジ時間 | 10,424 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 45 |
ソースコード
# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]
mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")
prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right
"""
含んでも含まれても ng で M 個選べるような X を求めよ
辞書順最小化もしてね💜
ある文字を選んだとき、それが可能かの判定は＿？
- それが接頭辞でないものすべて + X \in S であるもので、もっとも trie の
- trie の各ノードで max と sum を持てば ok かな
- 面倒くさいです
"""
from array import array
class Trie:
__slots__ = (
"alphabet", "symbol_index", "sigma", "dense", "transitions",
"terminal_count", "subtree_count", "terminal_ids", "parent",
"parent_symbol", "word_count",
)
def __init__(self, alphabet=None):
self.alphabet = alphabet
if alphabet is None:
self.symbol_index = None
self.sigma = 0
self.dense = False
self.transitions = [{}]
else:
alphabet = tuple(alphabet)
if len(set(alphabet)) != len(alphabet):
raise ValueError("alphabet symbols must be unique")
self.alphabet = alphabet
self.symbol_index = {
symbol: i for i, symbol in enumerate(alphabet)
}
self.sigma = len(alphabet)
self.dense = True
self.transitions = array("i", [-1]) * self.sigma
self.terminal_count = [0]
self.subtree_count = [0]
self.terminal_ids = [None]
# self.parent = [-1]
# self.parent_symbol = [None]
self.word_count = 0
def __len__(self):
return len(self.terminal_count)
@property
def node_count(self):
return len(self.terminal_count)
def _new_node(self, parent, symbol):
node = len(self.terminal_count)
if self.dense:
self.transitions.extend([-1] * self.sigma)
else:
self.transitions.append({})
self.terminal_count.append(0)
self.subtree_count.append(0)
self.terminal_ids.append(None)
# self.parent.append(parent)
# self.parent_symbol.append(symbol)
return node
def _symbol(self, symbol):
index = self.symbol_index.get(symbol)
if index is None:
raise ValueError("symbol is outside the fixed alphabet")
return index
def move(self, node, symbol):
if node < 0:
return -1
if self.dense:
index = self.symbol_index.get(symbol)
if index is None:
return -1
return self.transitions[node * self.sigma + index]
return self.transitions[node].get(symbol, -1)
def add(self, word, word_id=None, count=1):
assert count > 0
node = 0
path = [0]
if self.dense:
sigma = self.sigma
transitions = self.transitions
for symbol in word:
index = self._symbol(symbol)
position = node * sigma + index
next_node = transitions[position]
if next_node == -1:
next_node = self._new_node(node, symbol)
transitions[position] = next_node
node = next_node
path.append(node)
else:
transitions = self.transitions
for symbol in word:
next_node = transitions[node].get(symbol)
if next_node is None:
next_node = self._new_node(node, symbol)
transitions[node][symbol] = next_node
node = next_node
path.append(node)
self.terminal_count[node] += count
self.word_count += count
for vertex in path:
self.subtree_count[vertex] += count
if word_id is not None:
ids = self.terminal_ids[node]
if ids is None:
self.terminal_ids[node] = [word_id]
else:
ids.append(word_id)
return node
insert = add
def find(self, word):
node = 0
for symbol in word:
node = self.move(node, symbol)
if node == -1:
return -1
return node
def count(self, word):
node = self.find(word)
return 0 if node == -1 else self.terminal_count[node]
def contains(self, word):
return self.count(word) > 0
__contains__ = contains
def prefix_count(self, prefix):
node = self.find(prefix)
return 0 if node == -1 else self.subtree_count[node]
count_prefix = prefix_count
def ids(self, node):
if node < 0:
return []
ids = self.terminal_ids[node]
return [] if ids is None else ids
def iter_prefixes(self, sequence):
node = 0
if self.terminal_count[0]:
yield 0, 0
for end, symbol in enumerate(sequence, 1):
node = self.move(node, symbol)
if node == -1:
return
if self.terminal_count[node]:
yield end, node
def longest_prefix(self, sequence):
result = (0, 0) if self.terminal_count[0] else (-1, -1)
for end, node in self.iter_prefixes(sequence):
result = end, node
return result
def erase(self, word, count=1):
assert count > 0
node = 0
path = [0]
for symbol in word:
node = self.move(node, symbol)
if node == -1:
return False
path.append(node)
if self.terminal_count[node] < count:
return False
self.terminal_count[node] -= count
self.word_count -= count
for vertex in path:
self.subtree_count[vertex] -= count
return True
remove = erase
def words(self):
result = []
stack = [(0, ())]
while stack:
node, prefix = stack.pop()
count = self.terminal_count[node]
if count:
result.append((prefix, count))
if self.dense:
offset = node * self.sigma
for index in range(self.sigma - 1, -1, -1):
child = self.transitions[offset + index]
if child != -1:
stack.append((child, prefix + (self.alphabet[index],)))
else:
for symbol, child in self.transitions[node].items():
stack.append((child, prefix + (symbol,)))
return result
n, m = MI()
trie = Trie(alplow)
for i in range(n):
s = SI()
trie.add(s)
path = []
def dfs(v, p):
# m 個のこるなら ok
if v != 0 and n - p - trie.subtree_count[v] >= m:
print("Yes")
print("".join(path))
exit()
np = p + trie.terminal_count[v] # 個々を足す
if n - np < m:
return None
for c in alplow:
u = trie.move(v, c)
path.append(c)
if u == -1:
# 存在しないとき
if n - np >= m:
print("Yes")
print("".join(path))
exit()
else:
res = dfs(u, np)
if res != None:
return res
path.pop()
return None
ans = dfs(0, 0)
print("No")