結果

問題 No.102 トランプを奪え
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-21 16:29:19
言語 Go
(1.22.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,120 bytes
コンパイル時間 11,379 ms
コンパイル使用メモリ 218,076 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 03:12:19
合計ジャッジ時間 12,000 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {
	// 结束可以抢夺牌的nim游戏,拿到最后一张牌就胜利
	// 場に４つの山が用意される。
	// 4つの山それぞれの枚数が与えられます(1<=n<=13)。
	// プレイヤーは交互に山からカードを取り手札とする
	// !１回に取れるのは１つの山から１枚～３枚のみ（複数の山からまとめてとることはできない）
	// !パスはできず必ず１枚はカードを取らなければならない
	// ４つの山それぞれについて、最後のカードを取った場合、相手の手札の半分（奇数枚の場合は切り上げ）を奪うことができる
	// すべての山が無くなったとき、手札が多いほうが勝ち
	// 勝利するプレイヤー名（"Taro"か"Jiro"）、引き分けの場合は"Draw"を出力してください。

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

	nums := [4]int{0, 0, 0, 0}
	for i := 0; i < 4; i++ {
		fmt.Fscan(in, &nums[i])
	}

	memo := make([]int, 20)
	for i := range memo {
		memo[i] = -1
	}
	var grundy func(state int) int
	grundy = func(state int) int {
		if memo[state] != -1 {
			return memo[state]
		}
		if state == 1 {
			memo[state] = 1
			return 1
		}
		nextStates := make(map[int]struct{})
		for j := 1; j <= 3; j++ {
			if state-j >= 0 {
				nextStates[grundy(state-j)] = struct{}{}
			}
		}
		mex := 0
		for {
			if _, ok := nextStates[mex]; !ok {
				break
			}
			mex++
		}
		memo[state] = mex
		return mex
	}

	xor := 0
	for i := 0; i < 4; i++ {
		xor ^= grundy(nums[i])
	}

	if xor == 0 {
		fmt.Fprintln(out, "Jiro")
	} else {
		fmt.Fprintln(out, "Taro")
	}
}

// dag: 博弈的每个状态组成的有向无环图.
//  返回值: 每个状态的Grundy数.
//  grundy[i] = mex{grundy[j] | j in dag[i]}.
//  - 如果grundy为0,则先手必败,否则先手必胜.
//  - 若一个母状态可以拆分成多个相互独立的子状态，`则母状态的 SG 数等于各个子状态的 SG 数的异或。`
func GrundyNumber(dag [][]int) (grundy []int) {
	order, ok := topoSort(dag)
	if !ok {
		return
	}

	grundy = make([]int, len(dag))
	memo := make([]int, len(dag)+1)
	for j := len(order) - 1; j >= 0; j-- {
		i := order[j]
		if len(dag[i]) == 0 {
			continue
		}
		for _, v := range dag[i] {
			memo[grundy[v]]++
		}
		for memo[grundy[i]] > 0 {
			grundy[i]++
		}
		for _, v := range dag[i] {
			memo[grundy[v]]--
		}
	}

	return
}

func topoSort(dag [][]int) (order []int, ok bool) {
	n := len(dag)
	visited, temp := make([]bool, n), make([]bool, n)
	var dfs func(int) bool
	dfs = func(i int) bool {
		if temp[i] {
			return false
		}
		if !visited[i] {
			temp[i] = true
			for _, v := range dag[i] {
				if !dfs(v) {
					return false
				}
			}
			visited[i] = true
			order = append(order, i)
			temp[i] = false
		}
		return true
	}

	for i := 0; i < n; i++ {
		if !visited[i] {
			if !dfs(i) {
				return nil, false
			}
		}
	}

	for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
		order[i], order[j] = order[j], order[i]
	}
	return order, true
}
0