#952194 (Go) No.2636 No Waiting in Vain

提出ソース

結果

問題	No.2636 No Waiting in Vain
ユーザー	ynm3n
提出日時	2024-02-18 14:33:11
言語	Go (1.22.1)
結果	AC
実行時間	17 ms / 2,000 ms
コード長	5,899 bytes
コンパイル時間	11,078 ms
コンパイル使用メモリ	229,632 KB
実行使用メモリ	7,624 KB
最終ジャッジ日時	2024-09-29 00:29:18
合計ジャッジ時間	12,882 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 6,824 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	16 ms 7,624 KB
testcase_05	AC	16 ms 7,624 KB
testcase_06	AC	14 ms 7,620 KB
testcase_07	AC	16 ms 7,620 KB
testcase_08	AC	13 ms 7,624 KB
testcase_09	AC	16 ms 7,620 KB
testcase_10	AC	15 ms 7,620 KB
testcase_11	AC	13 ms 7,620 KB
testcase_12	AC	16 ms 7,624 KB
testcase_13	AC	16 ms 7,620 KB
testcase_14	AC	14 ms 7,620 KB
testcase_15	AC	17 ms 7,620 KB
testcase_16	AC	14 ms 7,620 KB
testcase_17	AC	16 ms 7,620 KB
testcase_18	AC	14 ms 7,620 KB
testcase_19	AC	16 ms 7,620 KB
testcase_20	AC	16 ms 7,620 KB
testcase_21	AC	16 ms 7,620 KB
testcase_22	AC	15 ms 7,624 KB
testcase_23	AC	16 ms 7,620 KB
testcase_24	AC	1 ms 6,816 KB
testcase_25	AC	1 ms 6,816 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	1 ms 6,816 KB
testcase_28	AC	1 ms 6,816 KB
testcase_29	AC	1 ms 6,816 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	1 ms 6,816 KB
testcase_32	AC	1 ms 6,816 KB
testcase_33	AC	1 ms 6,820 KB
testcase_34	AC	1 ms 6,820 KB
testcase_35	AC	1 ms 6,816 KB
testcase_36	AC	1 ms 6,820 KB
testcase_37	AC	1 ms 6,816 KB
testcase_38	AC	1 ms 6,816 KB
testcase_39	AC	1 ms 6,816 KB
testcase_40	AC	1 ms 6,816 KB
testcase_41	AC	1 ms 6,816 KB
testcase_42	AC	1 ms 6,816 KB
testcase_43	AC	1 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

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

// 解答欄
func solve(in *input, out, outErr *output) {
	m := newModulus(mod998_244_353)
	n, k := in.nextInt2()
	s := make([]rune, n+1)
	s[0] = 'P'
	copy(s[1:], in.nextRunes())

	cntT := 0
	cntN := 0
	for i := 1; i <= n; i++ {
		if s[i] == 'N' {
			cntN++
			if s[i-1] != 'C' {
				cntT++
			}
		}
	}

	combi, _ := m.newCombinationCalculator(cntT)

	ans := 0
	for i := 1; (cntN-i) >= k && (cntT-i) >= 0; i++ {
		tmp := combi(cntT, i)
		ans = m.add(ans, tmp)
	}
	out.println(ans)
}

// 以下のサイト様のアルゴリズムを真似させていただきました
// https://drken1215.hatenablog.com/entry/2018/06/08/210000
func (mAddr *modulus) newCombinationCalculator(n int) (func(n, k int) int, struct{ fac, finv, inv []int }) {
	m := int(*mAddr)
	n++
	fac := make([]int, n)
	finv := make([]int, n)
	inv := make([]int, n)
	if n == 1 {
		fac[0], finv[0] = 1, 1
	} else {
		fac[0], fac[1] = 1, 1
		finv[0], finv[1] = 1, 1
		inv[1] = 1
		for i := 2; i < n; i++ {
			fac[i] = fac[i-1] * i % m
			inv[i] = m - inv[m%i]*(m/i)%m
			finv[i] = finv[i-1] * inv[i] % m
		}
	}

	f := func(n, k int) int {
		if (n < k) || (n < 0) || (k < 0) {
			return 0
		}
		return fac[n] * (finv[k] * finv[n-k] % m) % m
	}
	s := struct {
		fac  []int
		finv []int
		inv  []int
	}{fac, finv, inv}
	return f, s
}

// modulo tools
type modulus int

const mod1_000_000_007 = 1_000_000_007
const mod998_244_353 = 998_244_353

func newModulus(p int) *modulus {
	m := modulus(p)
	return &m
}
func (m *modulus) mod(a int) int {
	if a < 0 || a >= int(*m) {
		a %= int(*m)
	}
	if a < 0 {
		a += int(*m)
	}
	return a
}
func (m *modulus) add(a, b int) int { return m.mod(a + b) }
func (m *modulus) sub(a, b int) int { return m.mod(a - b) }
func (m *modulus) mul(a, b int) int { return m.mod(a * b) }
func (m *modulus) div(a, b int) int { return m.mul(a, m.inv(b)) }
func (m *modulus) inv(a int) int {
	x, _ := extGcd(a, int(*m))
	return m.mod(x)
}
func (m *modulus) pow(a, n int) int {
	res := 1
	b := m.mod(a)
	for n > 0 {
		if n&1 > 0 {
			res = m.mul(res, b)
		}
		n >>= 1
		b = m.mul(b, b)
	}
	return res
}

func extGcd(a, b int) (int, int) {
	x0, y0 := 1, 0
	x1, y1 := 0, 1
	for a%b != 0 {
		q := a / b
		r := a % b
		x2, y2 := x0-q*x1, y0-q*y1

		a, b = b, r
		x0, y0 = x1, y1
		x1, y1 = x2, y2
	}
	return x1, y1
}

// 入出力の準備(in, out, outErr)
func main() {
	const (
		// インタラクティブ問題の時 true
		// バッファ無し出力に変更する。入力は変わらない
		interactiveProblem = false

		// 「X個のテストケースが与えられる」系の問題の時 true
		// 入力の一番最初でテストケース数が与えられる場合のみ使える
		variableSolveCount = false
	)

	const startBufSize = 4096
	const maxBufSize = math.MaxInt64
	in := &input{sc: bufio.NewScanner(os.Stdin)}
	in.sc.Buffer(make([]byte, startBufSize), maxBufSize)
	in.sc.Split(bufio.ScanWords)
	out := &output{}
	if interactiveProblem {
		out.w = os.Stdout
	} else {
		bw := bufio.NewWriter(os.Stdout)
		out.w = bw
		defer func() {
			if err := bw.Flush(); err != nil {
				panic(fmt.Errorf("flush error: %w", err))
			}
		}()
	}
	outErr := &output{w: os.Stderr}

	loop := 1
	if variableSolveCount {
		if _, err := fmt.Scan(&loop); err != nil {
			panic(fmt.Errorf("valiableSolveCount = %v, loop = %v: %w", variableSolveCount, loop, err))
		}
	}
	for i := 0; i < loop; i++ {
		solve(in, out, outErr)
	}
}

type input struct{ sc *bufio.Scanner }

func (in *input) nextString() string {
	in.sc.Scan()
	return in.sc.Text()
}
func (in *input) nextStrings(n int) []string {
	res := make([]string, n)
	for i := range res {
		res[i] = in.nextString()
	}
	return res
}
func (in *input) nextRunes() []rune {
	return []rune(in.nextString())
}
func (in *input) nextInt() int {
	s := in.nextString()
	res, err := strconv.Atoi(s)
	if err != nil {
		panic(fmt.Errorf("in.nextInt: %w", err))
	}
	return res
}
func (in *input) nextInts(n int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = in.nextInt()
	}
	return res
}
func (in *input) nextFloat() float64 {
	s := in.nextString()
	res, err := strconv.ParseFloat(s, 64)
	if err != nil {
		panic(fmt.Errorf("in.nextFloat: %w", err))
	}
	return res
}
func (in *input) nextFloats(n int) []float64 {
	res := make([]float64, n)
	for i := range res {
		res[i] = in.nextFloat()
	}
	return res
}
func (in *input) nextInt2() (int, int) {
	return in.nextInt(), in.nextInt()
}
func (in *input) nextInt3() (int, int, int) {
	return in.nextInt(), in.nextInt(), in.nextInt()
}
func (in *input) nextInt4() (int, int, int, int) {
	return in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()
}

type output struct{ w io.Writer }

func (out *output) print(a ...any) {
	if _, err := fmt.Fprint(out.w, a...); err != nil {
		panic(fmt.Errorf("out.print: %w", err))
	}
}
func (out *output) printf(format string, a ...any) { out.print(fmt.Sprintf(format, a...)) }
func (out *output) println(a ...any)               { out.print(fmt.Sprintln(a...)) }

// simple math functions for int
func max(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res < a {
			res = a
		}
	}
	return res
}
func min(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res > a {
			res = a
		}
	}
	return res
}
func chMax(a *int, b int) {
	*a = max(*a, b)
}
func chMin(a *int, b int) {
	*a = min(*a, b)
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func pow(a, n int) int {
	res := 1
	b := a
	for n > 0 {
		if n&1 > 0 {
			res *= b
		}
		n >>= 1
		b *= b
	}
	return res
}
func sum(s ...int) int {
	res := 0
	for _, v := range s {
		res += v
	}
	return res
}

// slice utility functions
func fillSlice[T any](s []T, v T) {
	for i := range s {
		s[i] = v
	}
}
func countSlice[T comparable](s []T, v T) int {
	res := 0
	for _, w := range s {
		if w == v {
			res++
		}
	}
	return res
}

yukicoder

結果

テストケース

ソースコード