#1177075 (C++23) No.3626 Not a Prefix

提出ソース

結果

問題	No.3626 Not a Prefix
コンテスト
ユーザー	kwm_t
提出日時	2026-08-14 23:08:53
言語	C++23 (gcc 15.2.0 + boost 1.90.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	WA
実行時間	-
コード長	6,897 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	2,905 ms
コンパイル使用メモリ	366,928 KB
実行使用メモリ	131,628 KB
最終ジャッジ日時	2026-08-14 23:09:04
合計ジャッジ時間	6,496 ms
ジャッジサーバーID （参考情報）	judge1_0 / judge3_0

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 1 WA * 1
other	AC * 27 WA * 18

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_DATA_STRUCTURE_TRIE_HPP
#define KWM_T_DATA_STRUCTURE_TRIE_HPP

#include <vector>
#include <functional>
#include <optional>

/**
 * @brief 汎用Trie（配列ベース）
 *
 * 任意の整数列（例：文字列, bit列）を扱うTrie
 * trans/inverseは外部注入可能
 *
 * 典型用途:
 *   - 文字列Trie
 *   - bit列Trie（BinaryTrieの代替）
 *   - 辞書順k番目
 *
 * 計算量:
 *   - 各操作 O(|S|)
 *
 * 注意:
 *   - eraseは存在する要素にのみ使うこと
 *   - inverse未指定時はvector<int>のみ返す
 *   - 問題固有の操作は関数追加して対応してください
 *
 * 使用例
 *   - https://atcoder.jp/contests/abc403/submissions/74526192
 *   - https://atcoder.jp/contests/abc377/submissions/74526225
 */
namespace kwm_t::data_structure {
// ---------------- デフォルトNode ----------------
struct EmptyNode {
	void add(int, int, int) {}
	void erase(int, int, int) {}
};

// ---------------- Trie本体 ----------------
template<class T = std::vector<int>, class Node = EmptyNode>
struct Trie {
private:
	int kind;

	std::vector<int> cnt;   // 部分木サイズ（必須）
	std::vector<std::vector<int>> next;
	std::vector<bool> end;
	std::vector<Node> node;

	// 外部注入
	std::function<std::vector<int>(const T&)> trans;
	std::function<T(const std::vector<int>&)> inverse;
	bool has_inverse = false;

	// 初期化
	void init() {
		cnt.assign(1, 0);
		end.assign(1, false);
		next.assign(1, std::vector<int>(kind, -1));
		node.assign(1, Node());
	}
public:
	// ---------------- コンストラクタ ----------------

	// 最小構成（そのままvector<int>使う）
	Trie(int _kind)
		: kind(_kind),
		trans([](const T& v) { return v; }) {
		init();
	}

	// transのみ
	Trie(int _kind,
		std::function<std::vector<int>(const T&)> _trans)
		: kind(_kind), trans(_trans) {
		init();
	}

	// trans + inverse
	Trie(int _kind,
		std::function<std::vector<int>(const T&)> _trans,
		std::function<T(const std::vector<int>&)> _inverse)
		: kind(_kind), trans(_trans), inverse(_inverse), has_inverse(true) {
		init();
	}

	// ---------------- 基本 ----------------

	void insert(const T& x, int id = -1) {
		auto v = trans(x);
		int now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			if (next[now][v[i]] == -1) {
				next[now][v[i]] = (int)cnt.size();
				cnt.emplace_back(0);
				end.push_back(false);
				next.emplace_back(std::vector<int>(kind, -1));
				node.emplace_back(Node());
			}
			now = next[now][v[i]];
			cnt[now]++;
		}
		end[now] = true;
		node[now].add(v.size() - 1, v.size(), id);
	}

	// prefixも追加
	void insert_prefix(const T& x, int id = -1) {
		auto v = trans(x);
		int now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			if (next[now][v[i]] == -1) {
				next[now][v[i]] = node.size();
				cnt.emplace_back(0);
				end.push_back(false);
				next.emplace_back(std::vector<int>(kind, -1));
				node.emplace_back(Node());
			}
			now = next[now][v[i]];
			cnt[now] += (int)v.size() - i;
			end[now] = true;
			node[now].add(i, v.size(), id);
		}
	}

	bool search(const T& x) const {
		auto v = trans(x);
		int now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			if (next[now][v[i]] == -1) return false;
			if (cnt[next[now][v[i]]] <= 0) return false;
			now = next[now][v[i]];
		}
		return end[now];
	}

	void erase(const T& x, int id = -1) {
		auto v = trans(x);
		int now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			now = next[now][v[i]];
			cnt[now]--;
		}
		end[now] = false;
		node[now].erase(v.size() - 1, v.size(), id);
	}

	void erase_prefix(const T& x, int id = -1) {
		auto v = trans(x);
		int now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			now = next[now][v[i]];
			cnt[now]--;
			node[now].erase(i, v.size(), id);
		}
		end[now] = false;
	}

	// ---------------- kth ----------------

	std::vector<int> kth_element_vec(int k) const {
		int now = 0;
		std::vector<int> ret;
		while (true) {
			bool ok = false;
			for (int i = 0; i < kind; ++i) {
				int nxt = next[now][i];
				if (nxt == -1) continue;
				if (k <= cnt[nxt]) {
					ret.push_back(i);
					now = nxt;
					ok = true;
					break;
				}
				else {
					k -= cnt[nxt];
				}
			}
			if (!ok) break;
		}
		return ret;
	}

	// inverseがある場合だけ使える
	std::optional<T> kth_element(int k) const {
		if (!has_inverse) return std::nullopt;
		return inverse(kth_element_vec(k));
	}

	// ---------------- index ----------------

	int getIndex(const T& x) const {
		auto v = trans(x);
		int ret = 0, now = 0;
		for (int i = 0; i < (int)v.size(); ++i) {
			if (now != 0) {
				ret += cnt[now];
				for (int j = 0; j < kind; ++j) {
					int nxt = next[now][j];
					if (nxt != -1) ret -= cnt[nxt];
				}
			}
			for (int j = 0; j < v[i]; ++j) {
				int nxt = next[now][j];
				if (nxt != -1) ret += cnt[nxt];
			}
			if (next[now][v[i]] == -1) break;
			now = next[now][v[i]];
		}
		return ret;
	}

	vector<int>dfs() {
		vector<int>ret;
		auto dfs_ = [&](auto&& self, int node, int end_)->bool {
			end_ += end[node];
			rep(i, 26) {
				int nxt = next[node][i];
				if (nxt == -1) {
					if (!end_) {
						ret.push_back(i);
						return true;
					}
				}
				else {
					ret.push_back(i);
					auto res = self(self, nxt, end_);
					if (res)return true;
					ret.pop_back();
				}
			}
			return false;
		};
		dfs_(dfs_, 0, 0);
		return ret;
	}
};

} // namespace kwm_t::data_structure
#endif // KWM_T_DATA_STRUCTURE_TRIE_HPP
vector<int> tra(string s) {
	vector<int>ret;
	rep(i, s.size())ret.push_back(s[i] - 'a');
	return ret;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<string>s(n);
	rep(i, n)cin >> s[i];
	sort(all(s));
	kwm_t::data_structure::Trie<string> tr(26, tra);
	rep(i, m) {
		tr.insert(s[i]);
	}
	auto v = tr.dfs();
	if (v.empty()) {
		// 4ケース誤判定している
		cout << "No" << endl;
		return 0;
	}
	// 2ケースは普通に間違っとる
	cout << "Yes" << endl;
	string ans;
	for (auto e : v)ans += e + 'a';
	cout << ans << endl;
	return 0;
}

yukicoder

結果

ソースコード