結果

問題 No.3299 K-th MMA String
コンテスト
ユーザー ID 21712
提出日時 2025-10-20 02:41:57
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 2,840 bytes
コンパイル時間 13,345 ms
コンパイル使用メモリ 234,988 KB
実行使用メモリ 7,764 KB
最終ジャッジ日時 2025-10-20 02:42:11
合計ジャッジ時間 13,680 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 9 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "math/big"

func main() {
	var n,k int
	Scan(&n,&k)
	s := make([]byte, n)
	for i := range s {
		s[i] = 'A'
	}
	Zero := NewInt(0)
	One := NewInt(1)
	dp := make([][3][2]*Int, n+1)
	const (
		A int = iota
		MA
		MM
	)
	const (
		ALL int = iota
		MMA
	)
	for i := 0; i < 3; i++ {
		for j := 0; j < 2; j++ {
			dp[n][i][j] = Zero
		}
	}
	dp[n][A][ALL] = One
	dp[n][MM][ALL] = One
	p, c := 0, 0
	all := false
	next := A
	for i := n-1; i >= 0; i-- {
		dp[i][A][ALL] = new(Int).Add(dp[i+1][A][ALL], new(Int).Add(dp[i+1][MA][ALL], dp[i+1][MM][ALL]))
		dp[i][A][MMA] = new(Int).Add(dp[i+1][A][MMA], new(Int).Add(dp[i+1][MA][MMA], dp[i+1][MM][MMA]))
		count := dp[i][A][MMA].Int64()
		if int(count) >= k {
			println("A")
			println(i)
			println(count)
			d := dp[i+1][MM][MMA].Int64()
			if int(count-d) < k {
				p, c = i+1, int(count)
				next = MM
				break
			}
			count -= d
			d = dp[i+1][MA][MMA].Int64()
			if int(count-d) < k {
				p, c = i+1, int(count-d)
				next = MA
				break
			}
			p, c = i+1, int(count-d)
			next = A
			break
		}
		dp[i][MA][ALL] = dp[i+1][A][ALL]
		dp[i][MA][MMA] = dp[i+1][A][MMA]
		count += dp[i][MA][MMA].Int64()
		if int(count) >= k {
			println("MA")
			println(i)
			println(count)
			s[i-1] = 'M'
			p, c = i+1, int(count)
			next = A
			break
		}
		dp[i][MM][ALL] = new(Int).Add(dp[i+1][MA][ALL], dp[i+1][MM][ALL])
		dp[i][MM][MMA] = new(Int).Add(dp[i+1][MA][ALL], dp[i+1][MM][MMA])
		count += dp[i][MM][MMA].Int64()
		if int(count) >= k {
			println("MM")
			println(i)
			println(count)
			s[i-1] = 'M'
			if d := dp[i+1][MM][MMA].Int64(); int(count-d) < k {
				p, c = i+1, int(count)
				next = MM
			} else {
				p, c = i+1, int(count-d)
				next = MA
				all = true
				println(i)
			}
			break
		}
	}
	for ; p < n; p++ {
		if all {
			switch next {
				case A:
					d := dp[p+1][MM][ALL].Int64()
					if c-int(d) < k {
						next = MM
					} else {
						c -= int(d)
						d = dp[p+1][MA][ALL].Int64()
						if c-int(d) < k {
							next = MA
						} else {
							c -= int(d)
							next = A
						}
					}
				case MA:
					s[p-1] = 'M'
					next = A
				case MM:
					s[p-1] = 'M'
					d := dp[p+1][MM][ALL].Int64()
					if c-int(d) < k {
						next = MM
					} else {
						c -= int(d)
						next = MA
					}
			}
		} else {
			switch next {
				case A:
					d := dp[p+1][MM][MMA].Int64()
					if c-int(d) < k {
						next = MM
					} else {
						c -= int(d)
						d = dp[p+1][MA][MMA].Int64()
						if c-int(d) < k {
							next = MA
						} else {
							c -= int(d)
							next = A
						}
					}
				case MA:
					s[p-1] = 'M'
					next = A
				case MM:
					s[p-1] = 'M'
					d := dp[p+1][MM][MMA].Int64()
					if c-int(d) < k {
						next = MM
					} else {
						c -= int(d)
						next = MA
						all = true
					}
			}
		}
	}
	Println(string(s))
}
0