結果

問題 No.1646 Avoid Palindrome
ユーザー sgsw
提出日時 2021-08-13 22:32:12
言語 Go
(1.23.4)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

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