結果

問題 No.1314 N言っちゃダメゲーム (5)
コンテスト
ユーザー ID 21712
提出日時 2026-05-28 18:59:01
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,032 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,296 ms
コンパイル使用メモリ 282,880 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-28 18:59:17
合計ジャッジ時間 13,499 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var m, k int
	Scan(&m,&k)
	secondWin := (m-1)/(k+1)
	firstWin := (m-1) - secondWin
	
	var anataWin,grantWin int
	if firstWin % 2 != 0 {
		anataWin = (firstWin+1)/2+secondWin
		grantWin = firstWin/2
	} else {
		anataWin = firstWin/2
		grantWin = firstWin/2+secondWin
	}
	
	switch {
		case anataWin > grantWin:
			Println("Win")
		case anataWin == grantWin:
			Println("Draw")
		case anataWin < grantWin:
			Println("Lose")
	}
}

/*
考察

ゲーム問題、超苦手すぎるのでまるで解ける気がしない

ゲームは N,K のとき
(N - 1) ≡ 0 (mod (K + 1))
のとき後手必勝、それ以外は先手必勝

2～Mの範囲で
後手必勝は floor( (M - 1) / (K + 1) ) 個
それ以外は先手必勝

プレーヤーは交互に先手必勝のゲームを選んでいくのが最善
最後に負けになったプレーヤーは先手必敗（後手必勝）ひたすら引き続ける地獄

先手必勝が 奇数個のとき
 アナタ Grant アナタ
 後手必勝が残っていればGrantが引き続ける(Grantが負け試合を総取り…)
 勝利数は
 　アナタ ceil(先手必勝/2) + 後手必勝
 　Grant floor(先手必勝/2)
 

先手必勝が 偶数個のとき
 アナタ Grant アナタ Grant
 後手必勝が残っていればアナタが引き続ける(アナタが負け試合を総取り…)
勝利数は
　アナタ　先手必勝/2
　Grant　先手必勝/2 + 後手必勝

*/

func init() {
	k := 8
	
	win := 0
	lose := 0

	for n := 2; n <= k*k*7; n++ {
		if !check(n, k) {
			lose++
			println(
				"n=",n,
				",k=",k,
				",n%k=",n%k,
				",?*k+?=",
				n/k,"*k+",n%k,
				" [LOSE]",
				", ",n/k%(k+1),
				", win/lose",win,"/",lose,
			)
			if check2(n, k) || check3(n, k) {
				panic("WRONG!")
			}
		} else {
			win++
			if !check2(n, k) || !check3(n, k) {
				println(
					"n=",n,
					",k=",k,
					",n%k=",n%k,
					",?*k+?=",
					n/k,"*k+",n%k,
					" [WIN]",
					", ",n/k%(k+1),
					", win/lose",win,"/",lose,
				)
				panic("WRONG!")
			}
		}
	}
	
	/*
	法則性の推測
	
	P = floor(N / K) とおく
	
	P % (K + 1) == K - 1 のとき　先手必勝
	
	P % (K + 1) == N % K - 1 のとき 後手必勝
	
	P % (K + 1) == K && N % K == 0 のとき 後手必勝
	
	上記以外　先手必勝
	
	2 <= N <= 1 + C * (K + 1) の範囲で
	先手必勝 C * K 個
	後手必勝 C 個
	
	後手必勝は K+1 回ごとに現れる
	後手必勝かは
	N - 1 ≡ 0 (mod (K + 1))
	ぽい？
	*/
	
}

func check3(n, k int) bool {
	return (n - 1) % (k + 1) != 0
}

func check2(n, k int) bool {
	p := n / k
	if p % (k + 1) ==  k - 1 {
		return  true
	}
	if p % (k + 1) == n % k - 1 {
		return false
	}
	if p % (k + 1) == k && n % k == 0 {
		return false
	}
	return true
}

var memo = map[int]bool{}

func check(n, k int) bool {
	if n == 1 {
		return false
	}
	if r, found := memo[n]; found {
		return r
	}
	for i := 1; i <= min(n-1,k); i++ {
		if !check(n-i,k) {
			memo[n] = true
			return true
		}
	}
	memo[n] = false
	return false
}
0