【Go言語】AtCoder ABC167 復習(問題E～問題F)

package main

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

var mod uint64 = 998244353

var maxfac uint64 = 200000
var fac []uint64  // n! % mod
var ifac []uint64 // k!^(mod-2) % mod

func initCombination() {
	fac = make([]uint64, maxfac+1)
	ifac = make([]uint64, maxfac+1)
	fac[0] = 1
	ifac[0] = 1
	var i uint64
	for i = 0; i < maxfac; i++ {
		fac[i+1] = fac[i] * (i + 1) % mod
		ifac[i+1] = ifac[i] * powMod(i+1, mod-2) % mod
	}
}
func combination(n, r uint64) uint64 {
	if n == 0 && r == 0 {
		return 1
	}
	if n < r || n < 0 {
		return 0
	}
	return (fac[n] * (ifac[r] * ifac[n-r] % mod) % mod)
}

func powMod(n, m uint64) uint64 {
	var ans uint64 = 1
	for m != 0 {
		if (m % 2) != 0 {
			ans = ans * n % mod
			if m == 1 {
				break
			}
		}
		n = n * n % mod
		m = m / 2
	}
	return ans
}

func main() {
	list := getStdinIntArr64()
	var N uint64 = uint64(list[0])
	var M uint64 = uint64(list[1])
	var K uint64 = uint64(list[2])

	initCombination()

	var ans uint64 = 0
	var k uint64 = 0
	for k = 0; k <= K; k++ {
		var tmp uint64 = 0
		tmp = M * combination(N-1, k) % mod
		tmp = tmp * powMod(M-1, N-1-k) % mod
		ans = (ans + tmp) % mod
	}

	fmt.Printf("%d\n", ans)
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*1)

func getStdin() string {
	return readLine()
}
func getStdinIntArr64() []int64 {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int64, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.ParseInt(val, 10, 64)
	}
	return rtn
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

package main

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

type kakko struct {
	str string
	min int
	max int
}

func main() {
	N := getStdinInt()
	F := make([]kakko, 0, N)
	L := make([]kakko, 0, N)
	for i := 0; i < N; i++ {
		s := getStdin()
		min, max := minmaxKakko(s)
		if min >= 0 {
			F = append(F, kakko{s, min, max})
		} else {
			L = append(L, kakko{s, min, max})
		}
	}
	sort.Slice(F, func(i, j int) bool { return F[i].max-F[i].min < F[j].max-F[j].min })
	sort.Slice(L, func(i, j int) bool { return L[i].max > L[j].max })

	K := make([]kakko, N)
	for i := 0; i < len(F); i++ {
		K[i] = F[i]
	}
	for i := 0; i < len(L); i++ {
		K[i+len(F)] = L[i]
	}

	first := -1
	last := -1
	for i := 0; i < len(K); i++ {
		if K[i].str[0] == '(' {
			first = i
			break
		}
	}
	for i := len(K) - 1; i >= 0; i-- {
		if first != i && K[i].str[len(K[i].str)-1] == ')' {
			last = i
			break
		}
	}

	if first == -1 || last == -1 {
		fmt.Printf("No\n")
		return
	}

	stack := 0
	stack = okKakko(K[first].str, stack)
	if stack < 0 {
		fmt.Printf("No\n")
		return
	}
	for i := 0; i < len(K); i++ {
		if first == i || last == i {
			continue
		}
		stack = okKakko(K[i].str, stack)
		if stack < 0 {
			fmt.Printf("No\n")
			return
		}
	}
	stack = okKakko(K[last].str, stack)
	if stack < 0 {
		fmt.Printf("No\n")
		return
	}

	if stack == 0 {
		fmt.Printf("Yes\n")
	} else {
		fmt.Printf("No\n")
	}
}

func minmaxKakko(s string) (int, int) {
	stack := 0
	max := math.MinInt32
	min := math.MaxInt32
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack++
			if stack > max {
				max = stack
			}
		}
		if s[i] == ')' {
			stack--
			if stack < min {
				min = stack
			}
		}
	}
	return min, max
}

func okKakko(s string, stack int) int {
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack++
		}
		if s[i] == ')' {
			stack--
		}
		if stack < 0 {
			return -1
		}
	}
	return stack
}

var sc = bufio.NewScanner(os.Stdin)

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}