結果
問題 |
No.1192 半部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:49:45 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,486 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,332 KB |
実行使用メモリ | 105,600 KB |
最終ジャッジ日時 | 2025-06-12 18:49:50 |
合計ジャッジ時間 | 3,932 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 15 |
ソースコード
import sys def main(): S = sys.stdin.readline().strip() T = sys.stdin.readline().strip() # Preprocess T for subsequence check n = len(T) next_t = [[n] * 26 for _ in range(n + 1)] for i in range(n - 1, -1, -1): for c in range(26): next_t[i][c] = next_t[i + 1][c] char_code = ord(T[i]) - ord('a') next_t[i][char_code] = i # Check if S is a subsequence of T current_pos = 0 is_subseq = True for c in S: code = ord(c) - ord('a') current_pos = next_t[current_pos][code] if current_pos >= n: is_subseq = False break current_pos += 1 if not is_subseq: print(S) return # Check if S contains any character not in T t_chars = set(T) min_char = None min_pos = float('inf') s_has_char_not_in_t = False for i, c in enumerate(S): if c not in t_chars: s_has_char_not_in_t = True if min_char is None or c < min_char or (c == min_char and i < min_pos): min_char = c min_pos = i if s_has_char_not_in_t: print(min_char) return # Preprocess S for next character positions m = len(S) next_pos_s = [[-1] * 26 for _ in range(m + 1)] last = [-1] * 26 for i in range(m - 1, -1, -1): c_code = ord(S[i]) - ord('a') last[c_code] = i for j in range(26): next_pos_s[i][j] = last[j] # Find the minimal candidate of length 2 min_candidate = None for i in range(m): c1 = S[i] code1 = ord(c1) - ord('a') # Check each possible c2 in order a-z for code2 in range(26): j = next_pos_s[i + 1][code2] if j == -1: continue # Check if c1 followed by c2 is not a subsequence of T pos = next_t[0][code1] if pos >= n: candidate = c1 + chr(code2 + ord('a')) if (min_candidate is None) or (candidate < min_candidate): min_candidate = candidate break pos_c2 = next_t[pos + 1][code2] if pos_c2 >= n: candidate = c1 + chr(code2 + ord('a')) if (min_candidate is None) or (candidate < min_candidate): min_candidate = candidate break print(min_candidate if min_candidate is not None else -1) if __name__ == '__main__': main()