結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:38:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,237 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 55,800 KB |
最終ジャッジ日時 | 2025-06-12 21:43:27 |
合計ジャッジ時間 | 3,637 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | AC * 2 WA * 38 |
ソースコード
import sys from collections import defaultdict MOD = 998244353 def main(): s = sys.stdin.readline().strip() n = len(s) dp_prev = defaultdict(int) # Initialize for the first character (i=0, 0-based) if s[0] == '?': for c in 'abcdefghijklmnopqrstuvwxyz': dp_prev[(None, c)] = 1 else: dp_prev[(None, s[0])] = 1 for i in range(1, n): dp_current = defaultdict(int) for (a_prev, b_prev), count in dp_prev.items(): if s[i] == '?': possible_c = 'abcdefghijklmnopqrstuvwxyz' else: possible_c = [s[i]] for c in possible_c: if i == 1: # Second character (i=1, 0-based) if c == b_prev: continue else: if c == b_prev or c == a_prev: continue new_state = (b_prev, c) dp_current[new_state] = (dp_current[new_state] + count) % MOD dp_prev = dp_current if not dp_prev: break result = sum(dp_prev.values()) % MOD print(result) if __name__ == "__main__": main()