#844425 (Go) No.1720 Division Permutation

提出ソース

結果

問題	No.1720 Division Permutation
ユーザー	草苺奶昔
提出日時	2023-02-27 14:39:53
言語	Go (1.22.1)
結果	AC
実行時間	370 ms / 4,000 ms
コード長	5,817 bytes
コンパイル時間	14,414 ms
コンパイル使用メモリ	222,144 KB
実行使用メモリ	46,720 KB
最終ジャッジ日時	2024-09-14 22:10:34
合計ジャッジ時間	29,607 ms
ジャッジサーバーID （参考情報）	judge6 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	367 ms 43,264 KB
testcase_14	AC	368 ms 46,592 KB
testcase_15	AC	221 ms 28,160 KB
testcase_16	AC	357 ms 44,160 KB
testcase_17	AC	247 ms 39,552 KB
testcase_18	AC	275 ms 46,720 KB
testcase_19	AC	369 ms 45,056 KB
testcase_20	AC	364 ms 44,928 KB
testcase_21	AC	365 ms 45,312 KB
testcase_22	AC	365 ms 45,056 KB
testcase_23	AC	358 ms 44,928 KB
testcase_24	AC	365 ms 45,056 KB
testcase_25	AC	362 ms 45,440 KB
testcase_26	AC	364 ms 45,056 KB
testcase_27	AC	367 ms 45,868 KB
testcase_28	AC	362 ms 45,952 KB
testcase_29	AC	366 ms 45,824 KB
testcase_30	AC	362 ms 44,800 KB
testcase_31	AC	364 ms 45,440 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	1 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	313 ms 43,392 KB
testcase_44	AC	288 ms 40,448 KB
testcase_45	AC	257 ms 36,224 KB
testcase_46	AC	190 ms 25,984 KB
testcase_47	AC	260 ms 38,656 KB
testcase_48	AC	207 ms 28,160 KB
testcase_49	AC	319 ms 42,240 KB
testcase_50	AC	244 ms 35,200 KB
testcase_51	AC	207 ms 27,648 KB
testcase_52	AC	293 ms 41,344 KB
testcase_53	AC	357 ms 46,464 KB
testcase_54	AC	354 ms 45,568 KB
testcase_55	AC	342 ms 45,440 KB
testcase_56	AC	358 ms 45,184 KB
testcase_57	AC	354 ms 43,264 KB
testcase_58	AC	346 ms 46,720 KB
testcase_59	AC	359 ms 46,080 KB
testcase_60	AC	370 ms 45,568 KB
testcase_61	AC	359 ms 46,336 KB
testcase_62	AC	355 ms 46,208 KB

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

ソースコード

raw source code

package main

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

const MDO int = 998244353

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, k int
	fmt.Fscan(in, &n, &k)
	perm := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &perm[i])
		perm[i]--
	}

	tree := NewPermutationTree()
	root := tree.Build(perm)
	dp := make([][]int, k+1) // dp[k][i] 表示将perm[0:i]分成k段的方案数
	for i := 0; i <= k; i++ {
		dp[i] = make([]int, n+1)
	}
	dp[0][0] = 1

	var dfs func(*Node)
	dfs = func(node *Node) {
		if node.IsCut() || node.IsLeaf() {
			for i := 0; i < k; i++ {
				dp[i+1][node.right] += dp[i][node.left]
				dp[i+1][node.right] %= MDO
			}
		}

		sum := make([]int, k)
		for _, child := range node.children {
			dfs(child)
			if node.IsJoin() {
				for i := 0; i < k; i++ {
					dp[i+1][child.right] += sum[i]
					dp[i+1][child.right] %= MDO
					sum[i] += dp[i][child.left]
					sum[i] %= MDO
				}
			}
		}
	}
	dfs(root)

	for i := 1; i <= k; i++ {
		fmt.Fprintln(out, dp[i][n])
	}
}

type NodeType int

const (
	JOIN_ASC NodeType = iota
	JOIN_DESC
	LEAF
	CUT
)

type Node struct {
	kind        NodeType
	left, right int // [left, right) => 顶点对应的区间
	minV, maxV  int // [minV, maxV) => 顶点对应的区间中的最小值和最大值
	children    []*Node
}

func (n *Node) String() string {
	mp := map[NodeType]string{
		JOIN_ASC:  "JOIN_ASC",
		JOIN_DESC: "JOIN_DESC",
		LEAF:      "LEAF",
		CUT:       "CUT",
	}
	sb := []string{"Node:\n"}
	sb = append(sb, fmt.Sprintf("kind : %v\n", mp[n.kind]))
	sb = append(sb, fmt.Sprintf("left && right : [%v, %v)\n", n.left, n.right))
	sb = append(sb, fmt.Sprintf("minV && maxV : [%v, %v)\n", n.minV, n.maxV))
	sb = append(sb, fmt.Sprintf("childrenCount : %v", len(n.children)))
	return strings.Join(sb, "  ")
}

func (n *Node) Size() int    { return n.right - n.left }
func (n *Node) IsJoin() bool { return n.kind == JOIN_ASC || n.kind == JOIN_DESC }
func (n *Node) IsLeaf() bool { return n.kind == LEAF }
func (n *Node) IsCut() bool  { return n.kind == CUT }

type PermutationTree struct{ Root *Node }

func NewPermutationTree() *PermutationTree { return &PermutationTree{} }

func (pt *PermutationTree) Build(nums []int) *Node {
	n := len(nums)
	desc, asc := []int{-1}, []int{-1}
	st := []*Node{}

	seg := newRangeAddRangeMin(make([]int, n))
	for i := 0; i < n; i++ {
		for desc[len(desc)-1] != -1 && nums[i] > nums[desc[len(desc)-1]] {
			seg.Update(desc[len(desc)-2]+1, desc[len(desc)-1]+1, nums[i]-nums[desc[len(desc)-1]])
			desc = desc[:len(desc)-1]
		}
		for asc[len(asc)-1] != -1 && nums[i] < nums[asc[len(asc)-1]] {
			seg.Update(asc[len(asc)-2]+1, asc[len(asc)-1]+1, nums[asc[len(asc)-1]]-nums[i])
			asc = asc[:len(asc)-1]
		}
		desc = append(desc, i)
		asc = append(asc, i)

		t := &Node{kind: LEAF, left: i, right: i + 1, minV: nums[i], maxV: nums[i] + 1}
		for {
			kind := CUT
			if len(st) > 0 {
				if st[len(st)-1].maxV == t.minV {
					kind = JOIN_ASC
				} else if t.maxV == st[len(st)-1].minV {
					kind = JOIN_DESC
				}
			}

			if kind != CUT {
				r := st[len(st)-1]
				if kind != r.kind {
					r = &Node{kind: kind, left: r.left, right: r.right, minV: r.minV, maxV: r.maxV, children: []*Node{r}}
				}
				pt.addChild(r, t)
				st = st[:len(st)-1]
				t = r
			} else if seg.Query(0, i+1-t.Size()) == 0 {
				t = &Node{kind: CUT, left: t.left, right: t.right, minV: t.minV, maxV: t.maxV, children: []*Node{t}}
				// do while
				for {
					pt.addChild(t, st[len(st)-1])
					st = st[:len(st)-1]
					if t.maxV-t.minV == t.Size() {
						break
					}
				}
				for i, j := 0, len(t.children)-1; i < j; i, j = i+1, j-1 {
					t.children[i], t.children[j] = t.children[j], t.children[i]
				}
			} else {
				break
			}
		}

		st = append(st, t)
		seg.Update(0, i+1, -1)
	}

	pt.Root = st[0]
	return st[0]
}

func (pt *PermutationTree) addChild(t, c *Node) {
	t.children = append(t.children, c)
	t.left = min(t.left, c.left)
	t.right = max(t.right, c.right)
	t.minV = min(t.minV, c.minV)
	t.maxV = max(t.maxV, c.maxV)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

const INF int = 1e18

type rangeAddRangeMin struct {
	n, head            int
	rangeMin, rangeAdd []int
}

func newRangeAddRangeMin(nums []int) *rangeAddRangeMin {
	res := &rangeAddRangeMin{}
	res.n = len(nums)
	res.head = 1
	for res.head < res.n {
		res.head <<= 1
	}
	res.rangeMin, res.rangeAdd = make([]int, res.head*2), make([]int, res.head*2)
	for i := range res.rangeMin {
		res.rangeMin[i] = INF
	}
	copy(res.rangeMin[res.head:], nums)
	for i := res.head - 1; i > 0; i-- {
		res.merge(i)
	}
	return res
}

func (r *rangeAddRangeMin) Update(start, end, add int) {
	r.update(start, end, 1, 0, r.head, add)
}
func (r *rangeAddRangeMin) Query(start, end int) int {
	return r.query(start, end, 1, 0, r.head)
}

func (r *rangeAddRangeMin) Get(pos int) int { return r.Query(pos, pos+1) }

func (r *rangeAddRangeMin) query(start, end, pos, left, right int) int {
	if right <= start || end <= left {
		return INF
	}
	if start <= left && right <= end {
		return r.rangeMin[pos] + r.rangeAdd[pos]
	}
	return min(r.query(start, end, pos*2, left, (left+right)/2), r.query(start, end, pos*2+1, (left+right)/2, right)) + r.rangeAdd[pos]
}

func (r *rangeAddRangeMin) update(start, end, pos, left, right, add int) {
	if right <= start || end <= left {
		return
	}
	if start <= left && right <= end {
		r.rangeAdd[pos] += add
		return
	}
	r.update(start, end, pos*2, left, (left+right)/2, add)
	r.update(start, end, pos*2+1, (left+right)/2, right, add)
	r.merge(pos)
}

func (r *rangeAddRangeMin) merge(pos int) {
	r.rangeMin[pos] = min(r.rangeMin[pos*2]+r.rangeAdd[pos*2], r.rangeMin[pos*2+1]+r.rangeAdd[pos*2+1])
}

yukicoder

結果

テストケース

ソースコード