結果

問題 No.1646 Avoid Palindrome
ユーザー ntudantuda
提出日時 2021-08-15 16:28:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,098 ms / 3,000 ms
コード長 1,351 bytes
コンパイル時間 508 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 445,168 KB
最終ジャッジ日時 2024-04-26 03:53:23
合計ジャッジ時間 58,511 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,852 KB
testcase_01 AC 46 ms
60,780 KB
testcase_02 AC 45 ms
59,820 KB
testcase_03 AC 55 ms
65,748 KB
testcase_04 AC 1,603 ms
423,376 KB
testcase_05 AC 1,565 ms
423,308 KB
testcase_06 AC 1,658 ms
411,428 KB
testcase_07 AC 1,574 ms
423,320 KB
testcase_08 AC 1,601 ms
427,008 KB
testcase_09 AC 1,573 ms
409,744 KB
testcase_10 AC 1,712 ms
417,912 KB
testcase_11 AC 1,564 ms
408,240 KB
testcase_12 AC 1,636 ms
422,576 KB
testcase_13 AC 1,629 ms
426,852 KB
testcase_14 AC 1,756 ms
417,332 KB
testcase_15 AC 1,794 ms
423,736 KB
testcase_16 AC 1,737 ms
414,876 KB
testcase_17 AC 1,788 ms
429,836 KB
testcase_18 AC 1,764 ms
420,756 KB
testcase_19 AC 1,769 ms
418,652 KB
testcase_20 AC 1,782 ms
421,572 KB
testcase_21 AC 1,884 ms
429,336 KB
testcase_22 AC 1,811 ms
417,584 KB
testcase_23 AC 1,859 ms
431,292 KB
testcase_24 AC 2,098 ms
445,168 KB
testcase_25 AC 2,075 ms
444,816 KB
testcase_26 AC 2,062 ms
444,776 KB
testcase_27 AC 2,058 ms
445,036 KB
testcase_28 AC 2,069 ms
444,900 KB
testcase_29 AC 1,548 ms
444,172 KB
testcase_30 AC 1,540 ms
444,644 KB
testcase_31 AC 1,717 ms
444,716 KB
testcase_32 AC 1,650 ms
444,164 KB
testcase_33 AC 1,585 ms
444,480 KB
testcase_34 AC 1,930 ms
444,228 KB
testcase_35 AC 42 ms
53,820 KB
testcase_36 AC 41 ms
53,480 KB
testcase_37 AC 40 ms
53,548 KB
testcase_38 AC 39 ms
53,328 KB
testcase_39 AC 41 ms
53,500 KB
testcase_40 AC 38 ms
53,628 KB
testcase_41 AC 43 ms
54,060 KB
testcase_42 AC 41 ms
53,132 KB
testcase_43 AC 1,551 ms
444,156 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
N = int(input())
S = input()
mod = 998244353
dp = [[[0] * 26 for i in range(26)] for j in range(N)]

def code(s):
    return ord(s) - 97

if N == 1:
    if S[0] == "?":
        print(26)
        sys.exit()
    else:
        print(1)
        sys.exit()

if S[0:2] == "??":
    for i in range(26):
        for j in range(26):
            if i != j:
                dp[1][i][j] = 1

elif S[0] == "?":
    j = code(S[1])
    for i in range(26):
        if i != j:
            dp[1][i][j] = 1

elif S[1] == "?":
    j = code(S[0])
    for i in range(26):
        if i != j:
            dp[1][j][i] = 1

else:
    if S[0] != S[1]: 
        dp[1][code(S[0])][code(S[1])] = 1

for i in range(2,N):
    if S[i] == "?":
        AS = [[0] * 27 for _ in range(26)]
        for k in range(26):
            for j in range(26):
                AS[k][j+1] = AS[k][j] + dp[i-1][j][k]
        for k in range(26):
            for l in range(26):
                if k != l:
                    temp = AS[k][l] + AS[k][-1] - AS[k][l+1]
                    dp[i][k][l] = temp % mod

    else:
        x = code(S[i])
        for j in range(26):
            for k in range(26):
                if j != x and k != x:
                    dp[i][k][x] = (dp[i][k][x] + dp[i-1][j][k]) % mod

ans = 0
for i in range(26):
    ans = (ans + sum(dp[-1][i])) % mod
print(ans)
0