結果

問題 No.1646 Avoid Palindrome
ユーザー sgswsgsw
提出日時 2021-08-13 22:32:12
言語 Go
(1.22.1)
結果
TLE  
実行時間 -
コード長 1,907 bytes
コンパイル時間 17,483 ms
コンパイル使用メモリ 222,276 KB
実行使用メモリ 128,512 KB
最終ジャッジ日時 2024-10-03 20:14:07
合計ジャッジ時間 20,033 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
12,072 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 43 ms
5,248 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

/*
	Go-Lang(1.16) Template for Programming-Contest.

	author : sgsw

	generated : 2021/08/13
	when : 22:20:51

*/

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var wg = bufio.NewScanner(os.Stdin)

const (
	inf            = int(1e18)
	initialBufSize = int(1e6)
	maxBufSize     = int(1e6)
	alphas         = "abcdefghijklmnopqrstuvwxyz"
	mod            = 998244353
)

var buf []byte = make([]byte, initialBufSize)

// greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

func init() {
	wg.Split(bufio.ScanWords)
	wg.Buffer(buf, maxBufSize)
}

func reverse_array(array []int) []int {
	//reverse the slice
	for i, j := 0, len(array)-1; i < j; i, j = i+1, j-1 {
		array[i], array[j] = array[j], array[i]
	}
	return array
}

func nextInt() int {
	wg.Scan()
	i, e := strconv.Atoi(wg.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextStr() string {
	wg.Scan()
	i := wg.Text()
	return i
}

func main() {
    //Pyには時間厳しすぎる...
	n := nextInt()
	s := "$" + nextStr()
	dp := make([]map[string]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make(map[string]int)
	}

	if s[1] != '?' {
		dp[1][string(s[0])+string(s[1])] = 1
	} else {
		for char := 'a'; char <= 'z'; char++ {
			dp[1][string(s[0])+string(char)] = 1
		}
	}

	for i := 2; i <= n; i++ {
		switch s[i] {

		case '?':
			for _, c := range alphas {
				for k, v := range dp[i-1] {
					if rune(k[0]) != rune(c) && rune(k[1]) != rune(c) {
						s := string(k[1]) + string(c)
						dp[i][s] += v
						dp[i][s] %= mod
					}
				}
			}

		default:
			c := s[i]
			for k, v := range dp[i-1] {
				if rune(k[0]) != rune(c) && rune(k[1]) != rune(c) {
					s := string(k[1]) + string(c)
					dp[i][s] += v
					dp[i][s] %= mod
				}
			}
		}
	}
	ans := 0
	for _, v := range dp[n] {
		ans += v
		ans %= mod
	}
	fmt.Printf("%d\n", ans)
	return
}
0