結果

問題 No.3626 Not a Prefix
コンテスト
ユーザー ks2m
提出日時 2026-08-14 22:54:15
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
WA  
実行時間 -
コード長 1,521 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,414 ms
コンパイル使用メモリ 100,324 KB
実行使用メモリ 185,040 KB
最終ジャッジ日時 2026-08-14 22:54:41
合計ジャッジ時間 12,154 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		String[] s = new String[n];
		for (int i = 0; i < n; i++) {
			s[i] = br.readLine();
		}
		br.close();

		Arrays.sort(s, Collections.reverseOrder());
		Node root = new Node();
		for (int i = 0; i < m; i++) {
			Node o = root;
			for (int j = 0; j < s[i].length(); j++) {
				char c = s[i].charAt(j);
				Node o2 = o.map.get(c);
				if (o2 == null) {
					o2 = new Node();
					o2.c = c;
					o.map.put(c, o2);
				}
				o = o2;
			}
			o.end = true;
		}

		String ans = dfs(root, new StringBuilder());
		if (ans == null) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
			System.out.println(ans);
		}
	}

	static String dfs(Node o, StringBuilder sb) {
		if (o.end) {
			return null;
		}
		for (char c = 'a'; c <= 'z'; c++) {
			sb.append(c);
			if (o.map.containsKey(c)) {
				String res = dfs(o.map.get(c), sb);
				if (res != null) {
					return res;
				}
			} else {
				return sb.toString();
			}
			sb.deleteCharAt(sb.length() - 1);
		}
		return null;
	}

	static class Node {
		char c;
		Map<Character, Node> map = new HashMap<>();
		boolean end;
	}
}
0