結果

問題 No.3626 Not a Prefix
コンテスト
ユーザー 👑 Nachia
提出日時 2026-08-14 21:50:57
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,769 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 646 ms
コンパイル使用メモリ 112,964 KB
実行使用メモリ 71,548 KB
最終ジャッジ日時 2026-08-14 21:51:01
合計ジャッジ時間 3,334 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


struct Node {
  ll lower = 0;
  ll upper = 0;
  ll just = 0;
  map<ll,ll> nx;
};

void testcase(){
  ll N, M; cin >> N >> M; M = N - M;
  V<string> S(N); REP(i,N) cin >> S[i];
  V<Node> trie(1);
  for(auto& s : S){
    ll p = 0;
    for(char c : s){
      if(!trie[p].nx.count(c)){
        trie[p].nx[c] = trie.size();
        trie.push_back(Node());
      }
      p = trie[p].nx[c];
    }
    trie[p].lower += 1;
    trie[p].upper += 1;
    trie[p].just += 1;
  }

  ll Z = trie.size();
  REP(i,Z) for(auto [u,v] : trie[i].nx) trie[v].upper += trie[i].upper;
  for(ll i=Z-1; i>=0; i--) for(auto [u,v] : trie[i].nx) trie[v].lower += trie[i].lower;

  string ans;

  auto dfs = [&](auto& dfs, ll p) -> bool {
    if(p != 0 && trie[p].lower + trie[p].upper - trie[p].just < M) return 1;
    if(trie[p].upper >= M) return 0;
    for(ll k='a'; k<='z'; k++){
      if(trie[p].nx.count(k)){
        if(dfs(dfs, trie[p].nx[k])){
          ans.push_back(k);
          return 1;
        }
      } else {
        ans.push_back(k);
        return 1;
      }
    }
    return 0;
  };
  if(dfs(dfs, 0)){
    reverse(ans.begin(), ans.end());
    cout << "Yes\n";
    cout << ans << "\n";
  } else {
    cout << "No\n";
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}
0