2017-12-21

競プロにおけるNim、Grundy数とNimK

この記事は、「競プロ!!」競技プログラミング Advent Calendar 2017 21日目の記事です。
昨日は DEGwer さんの「数え上げテクニック集」でした。まだ全部読んでないけど凄かったです。
こっちでも同時に競プロのアドベントカレンダーが進められています。

Nim,grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決するタイプのゲーム問題がわりとサクッと解けます。
最近では 5日前、2017/12/16 の Atcoder Regular Contest 087 E で Grundy数の問題が出ました。

この記事の本題はNimの拡張されたゲーム、NimKの話です。
導入として、Nimとかgrundy数を知らないひとにもわかるようにスライドを作成しました。
絵を描くだけのつもりだったのにスライドになってしまいました。
適当すぎてわからん！と思うひともいるかもしてないので参考リンクも貼りました。
それらのページを見てから戻ってきてくれるとうれしいです。

・参考になる記事

augusuto04さん、pekempeyさんの記事が特にわかりやすいです。書いてあるゲームを実際にやりながら考えてみてください。

(1) Grundy数の概要が分かる記事

Grundy数その１ - へなちょここーだー
 http://pekempey.hatenablog.com/entry/2016/01/16/190208

(2) Nim

Grundy数その2 - へなちょここーだー

・他の参考記事
不偏ゲームがNIMに帰着する証明 - SSSSLIDE
グランディ数 - zukky162のブログ
 grundy number - EAGLE 雑記
 grundy数を習得したかった - nanikakaのAOJ航海日誌

・練習に良さそう

最初のリンクは超絶おすすめ、これだけ解けるようになれば優しい問題は大体解ける
Hacker Rank 5 days of game theory (15問あるけど最後のやつ以外は基本だけで解ける)
- 解説はこの記事が参考になると思います。

yukicoderのNimのタグ
 yukicoderのGrundy数のタグ
 競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法] - はまやんはまやんはまやん
 競技プログラミングの不偏ゲーム(Nim, grundy数にまつわる)問題集 - かっさのなにか

本題

・NimK について

NimKとは、一般に知られているNimの拡張です。
プレイヤーは二人のまま、打てる手が変化します。

プレイヤーは自分のターンでK個の山を選択し、それぞれの山に対して好きな数だけ石を取ることができる。

各山に対して石を取ることのできる数が制限される場合など、いろいろな制約がつくパターンもあるようですが、ここではどれだけでも取れるとします。
問題っぽくすると次の文章になります。

$N$ 山の石を取るゲームををAlice,Bobが行う。このゲームではすべての石の中で最後の石を取った人が勝ちです。(石を取れなくなった人の負け)
各山には $pile[i]$ 個の石が積まれている。プレイヤーは各自分のターンに $K$ 個までの山を選択し、各山について石を1つ以上なら何個でも取ることができる。
2人が最適な石の取りかたをする時、Aliceが先攻ならば勝つことができるか？
制約: $1≤N≤10^5$ , $1≤pile[i]≤10^9$ , $1≤K≤10^5$

f:id:Yang33-kassa:20171221201155p:plain

実際にシュミレーションをして、grundy数を出すことは可能ですが、KやNが大きいときは状態数がやばいので厳しさがあります。

先に必勝法の判定は何かを書いておきます。
各山にある石の数を2進数で表したとき、これを
$pile(i)= 2^x*bin(i,x) + 2^{x-1}*bin(i,x-1) + 2^{x-2}*bin(i,x-2) + ... + 2^2*bin(i,2) + 2^1*bin(i,1) + 2^0*bin(i,0)$
となるように $bin(i,x)$ を作成します。
次に $N$ 個の $pile(i)$ についてこれを作成し、 $bin(i,x)$ を同じxについて次のように足し合わせます。
$digitsum(x)$ = $( \sum_{i=0}^{N-1} bin(i,x) )$ $mod (K+1)$
このとき、 $digitsum(x)%(K+1)$ が 0 でなくなるような $x$ が存在する場合には必勝です。(値を復元するとこれがgrundy数になっている)
f:id:Yang33-kassa:20171221202605p:plain

通常のNimでもこれが成り立っています。
Xor (排他的論理和)でgrundy数を求めるものもありますが、あれは2進数の各桁同士の和を $mod$ $2$ で計算した値と一致します。どちらの計算も2進数でみると各桁の数字は1の出現回数の偶奇で決まるためです。

この前NimKについて先輩と話したところ、「本当にいつものNimと一緒で必ず勝ちの目を維持できるんですか？」といわれてウウッとなり、本当に正しいのかを考えてみて怪しいのですが少し証明をしてみました。エレガントではないし、厳密ではないかもしれないので間違っていたら教えてください。証明とかイヤ！という人はとばしてください。

▶ひらく

考えたこと(ガバ証明)
ゲームの終端を $P$ $position$ とする。これは負けの状態です。 ( $\forall{x}$ $digitsum(x) = 0$ )
今 $P$ $position$ から始まって $P$ $position$ あるいは $not$ $P$ $position$ への移動が存在するかを考えます。

これを発見するためには、 $P$ $position$ からの任意の移動を行ってみます。
これは少なくとも1つの $x$ について、 $digitsum(x)$ の値を変更することになります。
$P$ $position$ から移動し,各桁 $K$ までしか値を減らすことはできないため、値を減少させながら0でない $digitsum(x)$ を一つも残さない様な手は存在しません。したがって $P$ $position$ からの移動は $not$ $P$ $position$ への移動となります。
次に、 $not$ $P$ $position$ の状態で $P$ $position$ に移動できるかを考えます。
$not$ $P$ $position$ ということは、少なくとも一つの $x$ について、 $digitsum(x)$ は $1≤digitsum(x)≤K$ となっています。
もし $digitsum(x)$ $\neq$ $0$ であるような $x$ について、 $pile(y) =0,$ ( $y$ は $x$ の候補に入らないもの)のまま、これを $digitsum(x) = 0$ にできる $pile(i)$ ( $0≤ i ＜N$ ) の残り方が存在すれば $not$ $P$ $position$ から $P$ $position$ への移動が存在します。
これで、少なくとも $P$ $position$ ー＞ $P$ $position$ への移動はないことがわかりました。
また、先のような手が存在するとすると、これはいつものNimのようなゲームと同様に、適切な手を選択すれば必ずゲームの開始前に先手必勝か後手必勝かを判定することができます。

そのような手が存在しないと意味が無いので、
次にそのような手が存在するかを考えます。

$not$ $P$ $position$ -> $P$ $position$ となる手が必ず存在することの証明
ここでは必ず $not$ $P$ $position$ から、 $P$ $position$ となるような手が存在することを示すことで証明とします。

$M = \sum_{i=0}^{N-1} ( 2^x * digitsum(x) )$ とします。今、 $M \neq 0$ となっています。またこのとき、 $digitsum(x)$ = $digitsum(x)$ $% (K+1)$ としておきます。すると $digitsum(x)$ は $K+1$ 進数となっています。
$M$ の $0$ でない最上位の桁の数を $digitsum(L)$ とします。(下の桁から $L+1$ 番目)すると、 $pile(i)$ の2進数に展開したものの中に、 $2^L$ の値について少なくとも $digitsum(L)$ 個の $1$ が存在します。(実際には非負整数を $n$ として $digitsum(x)$ $+ n(K+1)$ 個だけ存在する可能性はある)
あと、あとで使うのでこの値を $digitsum(L)copy$ とか適当な名前をつけます。
これにあてはまる $pile(i)$ を減らす候補とします。
まず、 $digitsum(L)$ を0にするためにこれらの候補の $pile(i)$ の $2^L$ につく数を1から0にして、更にそれより下の桁をすべて $1$ となるように変更します。(最上位の桁を触るので下の桁は自由な値に設定できる)
この操作によって $digitsum(L)$ は0になりますが、 $digitsum(l)$ ( $l ,0≤ l \leq L-1$ ) の値は変化します。

次に、 $M' = \sum_{i=0}^{N-1} ( 2^x * digitsum(x) )$ とします。
$M'$ の $0$ でない最上位の桁の数を $digitsum(L')$ とします。(下の桁から $L' + 1$ 番目)
先の操作から、 $M$ の一番大きい桁は $0$ にしたので、 $L ＞ L'$ となっています。また、 $M$ -> $M'$ への変更で選んだ $pile(i)$ の2進数展開した $L' + 1$ 桁目は全て $1$ になっています。
なんか2つ状態があるっぽいのでこれを場合分けします。
(ⅰ) $digitsum(L)copy$ $≧$ $digitsum(L')$
この場合は、前の操作で選択した $pile(i)$ のうち $K$ 個以下の $pile(i)$ を選択することで、 $digitsum(L')$ を $0$ にできる。

(ⅱ) $digitsum(L)copy$ $＜$ $digitsum(L')$
この場合は、前の操作で選択した $pile(i)$ の $L' + 1$ 桁目の値を $0$ にすると、 $digitsum(L')$ は前の $digitsum(L')$ - $digitsum(L)copy$ となっています。(操作した分を引いただけ)
さらに残った選択候補のうち、 $L' + 1$ 桁目が $1$ となっているものを $digitsum(L')$ - $digitsum(L)copy$ 個だけ選択し、今までと同じ操作を行う。

この操作によって、変更された $digitsum(L)$ $=$ $0$ , $digitsum(L')$ $=$ $0$ となります。
これを繰り返すことによって最大K個の数値を変更させることで、 $\forall{x}$ $digitsum(x) = 0$ を達成することができます。

はてなブログの $tex$ 記法がめんどくさすぎる。疲れました。

というわけで、存在します。

1つの山しか選択できない Nim と同様に手番を常に勝ち→負けへと動かすことができます。

コードを見たほうがはやい！みたいな人もいるはずなのでC++で先の問題のコードを書きました。上に書いたとおりに書いただけなので実際にはbin[i][x]とかは使わずに書けます。

void Nimk(int N, int K, vector<int>& pile) {
	vector< vector<int> > bin(N, vector<int>(30, 0)); // 2次元配列

	for (int i = 0; i < N; i++) { //pile[i]について、2進数に展開する
		int twopow = 1; // 2のべき乗
		for (int x = 0; x < 30; x++) {
			if (twopow & pile[i])// 2^xにくっつく数は0か1か
				bin[i][x] = 1;
			else
				bin[i][x] = 0;
			twopow = twopow * 2;
		}
	}

	vector<int> digitsum(N, 0); // 桁ごとの和

	for (int x = 0; x < 30; x++) {// 桁xについて
		for (int i = 0; i < N; i++) {
			digitsum[x] = digitsum[x] + bin[i][x];
		}
	}

	int win = 0; // 負けを0、勝ちを1とする
	for (int x = 0; x < 30; x++) {
		if (digitsum[x] % (K + 1) != 0) {
			// 桁の値が0ではないときは勝ちのポジション、grundy数が0でないことが確定する
			win = 1;
		}
	}

	if (win == 1) { // 先手の勝ち
		cout << "Alice" << endl;
	}
	else { // 先手の負け
		cout << "Bob" << endl;
	}

}

実際に解いてみましょう！

蟻本4-2節の練習問題にもある、 POJ2315 は問題文こそ分かりにくいですが、ゲームとしてみるとNimKです。
この記事を読んで理解した方なら”やるだけ”ですね！(実際にはPOJ特有のアレや問題文がアレなのでやるだけではないかも)

明日は575検出のプロ、YazatenさんのICPC引退ポエム？です。

[追記]

組合せゲームの勉強に良さそうな本 (一般的なゲーム理論ではない方)

(A) 組合せゲーム理論入門
(B) 石取りゲームの数学
競技プログラミングから外れるものも多いので、一部分だけ読めばNim,grundy数のことがわかります。(ちゃんとインターネットに演習問題の答えもあって比較的やさしい)
ちゃんと読むと、Aでは AOJ-ICPC1000点問題が、Bでは Atcoder 1100点問題とかが解けるようになります(もちろん多少の前提知識があれば本を読まなくても考えると解けます(という人もいる))

2017-11-04

競技プログラミングの桁DP問題集

桁DPです。
だいたい $O(N)$ では求めることができないものについて、与えられた条件をみたす数をDPで求めます。 $N=10^{10000}$ とか
再帰派とDP派(桁"DP"なのに)の二つがあるようですが僕は単純な問題以外は再帰の方がいいと思います(簡単なものはDPでよい(楽なので))
基本的には、
$dp[(上から)i桁まで見た][N未満か？][なんらかの状態]$ := (上から)i桁まで見たときに、indexの状態を満たす総数
として求めることが多いような気がします。これで解けなかったのは以下の3の問題だけです。
クエリに高速に答えるためには配列の埋まり方を考慮する必要があります。(問題6.参照)
埋まり方を理解すると計算がNに依存しない部分のみになります。(とてもうれしい)

以下僕の解いていった順です。3以外は全て再帰で解きました。

1. D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder

2. E: 数 - Typical DP Contest | AtCoder

3. D: 壊れた電卓 - CODE FESTIVAL 2014 予選A | AtCoder これ再帰で書けなくて悲しい

4. D: 1 - AtCoder Beginner Contest 029 | AtCoder

5. ジグザグ数 | Aizu Online Judge

6. Codeforces Manthan, Codefest 17 E Salazar Slytherin's Locket 理解するのに非常に良い?

7. No.189 SUPER HAPPY DAY - yukicoder

8. No.220 世界のなんとか2 - yukicoder

9. No.260 世界のなんとか3 - yukicoder

10. No.315 世界のなんとか3.5 - yukicoder ちょっと好き

11. No.319 happy b1rthday 2 me - yukicoder

12. No.372 It's automatic - yukicoder

13. No.362 門松ナンバー - yukicoder

14. F: レシート - 東京工業大学プログラミングコンテスト2015 | AtCoder

15. H: Bit Count - 京都大学プログラミングコンテスト2015 | AtCoder

16.

17.

18.

19.

20.

まだ
Investigation - LightOJ 1068 - Virtual Judge
LIDS | Toph
Problem - D - Codeforces
Palindromic Numbers - LightOJ 1205 - Virtual Judge
Contest Page | CodeChef
Problem - G - Codeforces
SPOJ.com - Problem TAP2012C
Digit Count - LightOJ 1122 - Virtual Judge
Contest Page | CodeChef
Dev Skill - Sanvi and Magical Numbers
SPOJ.com - Problem CPCRC1C
SPOJ.com - Problem PR003004
SPOJ.com - Problem RAONE
SPOJ.com - Problem LUCIFER
SPOJ.com - Problem NUMTSN
Contest Page | CodeChef

2017-09-15

競技プログラミングの不偏ゲーム(Nim, grundy数にまつわる)問題集

ゲーム理論

はじめに

ゲーム問題へのアプローチについて

ゲームの末尾から考えるとルールや必勝法がわかりやすいです。
Sprague-Grundyの定理によってプレイヤーごとに打つ手が変化しないような”二人完全情報不偏ゲーム”はNimberによってニムに帰着できます。
ゲームをあらかじめ先手必勝か後手必勝かを考えることができます。→これを読みました。

組合せゲーム理論入門 ?勝利の方程式?

作者: M.H.Albert,R.J.Nowakowski,D.Wolfe,川辺治之
出版社/メーカー: 共立出版
発売日: 2011/09/21
メディア: 単行本
クリック: 5回
この商品を含むブログ (1件) を見る

僕はゲームについてよくわかっていないことが多かったのでこれで何とかなりました。章末問題の答えもWebにアップロードされているのでお金があれば買ってなければ図書館や友人から借りるといいと思います。ゲームの末尾の考え方や拡張が丁寧に書かれているのでとても良い本だと思います。(競プロの主体で読むならば直接関係のない難しいところは読みとばしてもよいと思います。)賢い方や日頃以下の問題を解いている方は読まなくても組合せゲーム理論の基礎的な概念を理解しているようなので必要ないと思います。

また不偏でないゲームについても終局面を考えれば大体の問題を解くことができます。これはDPか再帰で求めることができます(ゲームが終了することを示すことができればDAGであるので。)

以下に問題のリンクを張ります。これらは難易度順ではなく本を読んだ上で僕が解いた順です。適当な解説はgithubにあげてあるので見たい人はみつけてください。

1. C: 笑いをとれるかな？ - AtCoder Regular Contest 013 | AtCoder

2. codeforces 399 div2 E Game of Stones

3. codeforces 417 div2 E Sagheer and Apple Tree

4. Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017) E Arpa and a game with Mojtaba

5. ICPC Regionals 2010 Asia Jakarta Playing With Stones

6. SPOJ.com - Problem MMMGAME

7. SPOJ.com - Problem MATGAME

8. No.2 素因数ゲーム - yukicoder

9. No.102 トランプを奪え - yukicoder

10. No.103 素因数ゲームリターンズ - yukicoder

11. No.153 石の山 - yukicoder

12. No.361 門松ゲーム2 - yukicoder

13. No.524 コインゲーム - yukicoder

14. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-game-of-stones

15. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers

16. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-1-a-chessboard-game

17. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-nim-game

18. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/misere-nim

19. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/nimble

20. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/day-2-poker-nim

21. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-2

22. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/tower-breakers-3

23. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game

24. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/digits-square-board

25. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/fun-game

26. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/powers-of-two-game

27. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/deforestation

28. https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/final-tower-breakers むずかしい。

29. B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

30. C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder 条件つきgrundy数の高速な求め方

31. Problem - 603C - Codeforces

32. HOJ 828 EEEEndless gamEEEE

33. Black and White Boxes | Aizu Online Judge 組合せゲーム理論の4,5章を読まないとたぶん厳しい問題。不偏ゲームではないがゲームの値が登場する。

34. 3537 -- Crosses and Crosses

35. 2975 -- Nim

36. 2315 -- Football Game Nim K

37. Codeforces Beta Round #99 Div1 D World of Darkraft

38. 1082 -- Calendar Game

39. 2068 -- Nim

40. 3688 -- Cheat in the Game

41. 1740 -- A New Stone Game

2017-07-28

問題集集

Codechef - Tags | CodeChef
Codechefのタグ

タグ一覧 - yukicoder
Yukicoderのタグ

AtCoder Problems
Atcoder過去問

AOJ-ICPC
AOJ-ICPC

AOJカテゴリー別問題集
AOJのタグ

https://www.hackerrank.com/domains/algorithms/warmup
HackerRankの分野別の基礎のヤツ

http://codeforces.com/problemset/tags/dp
Codeforecesのタグ(tags/"hoge"とすると選べる)

AOJ/Atcoder-JOI
JOIの問題(atcoderのスペシャルジャッジは壊れているので?AOJで提出した方がよい(2017/10/01現在))

2017-07-28

木dp問題集

先に読むとよい記事：
codeforces.com

2017-07-08

Hamako Online Judge ukuku09 contest B ghoststudents

動的BIT

問題概要

https://hoj.hamako-ths.ed.jp/onlinejudge/problems/767
うくさんはICPC部に所属しています。
ある日いつものように部活に参加していたうくさんは、部活に来ている部員の数が最初より減っていることに気づきました。
そこで、出席記録から、ある日以降（その日を含む）に一体何人が部活に参加しているのかを調べることにしました。ただし、うくさんは適当な性格をしているので、調べている途中で新しい記録が見つかることもあります。
ICPC部員にはそれぞれ1からNまでの独立な番号がつけられています。ここで、ある日以降に部活に参加している人数を「その日以降に一度でも部活に参加した人」の数の和と定義します。
クエリ1: $A$ 日目に( $1≤A≤10^9$ )に $B$ 番目( $1≤B≤10^9$ )の生徒が部活に参加したことを表します。
クエリ2: $C$ 日目を含むその日以降に( $1≤C≤10^9$ )に出席した人数を求めたいことを表します。
クエリ2が入力として与えられた場合、それに対する出力をジャッジが受け取るまで以降の入力が行われないことに注意してください。
$1≤N≤10^5$ , $1≤Q≤10^5$

解説

動的BIT or seg木で解くことができる。
BITの int data[] を map<int,int>data みたいにすればちょっと重くなるけど
メモリを使う部分しか消費しないのでうれしい。
何人参加していないかという情報をノードに持たせて、ある人が参加していることが分かった時刻にいもす法っぽく端の情報を修正すればいい。(内部で対数時間で足し合わせるので)
C日目以降の出席人数が知りたいので、出席日が更新されるごとに、０日目の情報からその日の情報に情報を修正していき、
[0,C)の範囲にいるC日目以降に出席していない人数を求めればよい。

コード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

ll N, Q;
ll ans = 0LL;

struct BIT { // 0-index
        ll N;
        map<ll, int> data;
        BIT(ll n) {
                N = n;
        }
        void add(ll i, int w) { // a[i] += w
                i++;
                for (ll x = i; x <= N; x += x & -x) {
                        data[x] += w;
                }
        }
        int sum(ll i) {
                int ret = 0;
                i++;
                for (ll x = i; x > 0; x -= x & -x) {
                        ret += data[x];
                }
                return ret;
        }
};

ll last[100005];

int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);

        cin >> N >> Q;
        BIT bit(INT_MAX);
        bit.add(0, N);
        for(int i = 0; i < Q ; i++){
                int num; cin >> num;
                if (num == 1) {
                        int a, b; cin >> a >> b;
                        b--;
                        if (last[b] < a) {
                                bit.add(last[b], -1);
                                last[b] = a;
                                bit.add(last[b], 1);
                        }
                }
                else if (num == 2) {
                        int c; cin >> c;
                        ans = N - bit.sum(c - 1);
                        cout << ans << endl << flush;

                }
        }

        return 0;
}

2017-07-08

Hamako Online Judge ukuku09 contest A photography

セグ木座標圧縮二分探索

問題概要

https://hoj.hamako-ths.ed.jp/onlinejudge/problems/766
うくさんはコンテストのために以下のような問題を考えました。
N人が横1列に並んでいます。左からi番目の人の可愛さは $X_i$ です。可愛さが負になることもあります。
チノちゃんは列のある連続する範囲にいる人たちを写真に収めたいです。ただし写真の中にいる人の可愛さの総和がP以上である必要があります。
このとき, 写真の中にいる人の最大の人数を出力してください。
$1≤N≤2×10^5$ , $-10^{15}≤P≤10^{15}$ , $-10^9≤X_i≤10^9$

解説

区間+座標圧縮+にぶたん
問題から $sum(i)-sum(j)≧P$ を考える。
累積和をキーにして、これをみたす $(j,i)$ の組のうち区間長が最大になるものを見つけたい。
式変形を行い $sum(i)-P≧sum(j)$ をみる。
$sum$ を昇順に並び替え順番にiを見ていくときに、欲しい累積和の最大値 $sum(j)$ がこれで決まったので
この最大値以下のうちindexが最小のものを見つける。
これは累積和を座標圧縮したものをソートして最小値のseg木にのせておけば対数時間で見つけることができる。

コード

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)

struct SegTree {
	ll N;
	vector<ll> dat;
	SegTree(ll _N) {
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<ll>(N * 2 - 1, INT_MAX);
	}
	void update(ll k, ll val) {
		k += N - 1;
		dat[k] = val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); // merge
		}
	}
	// 区間[a,b)の評価
	ll query(ll a, ll b, ll k, ll l, ll r) {
		if (r == -1)r = N;
		if (r <= a || b <= l)return INT_MAX; // 区間が被らない 
		if (a <= l&&b >= r)return dat[k]; // 値を返す
		ll v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(v1, v2); //merge
	}
	inline ll query(ll a, ll b) {
		return query(a, b, 0, 0, N);
	}
};


ll N, P;
ll a[200005];
ll sum[200005];
bool f[200005];
ll ans = 0;

int main() {

	scanf("%lld %lld", &N, &P);
	vector<ll>v;
	ll b = 0;
	v.push_back(0LL);

	for (int i = 0; i < N; i++) {
		scanf("%lld", &a[i]);
		sum[i + 1] = sum[i] + a[i];
		v.push_back(sum[i + 1]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	SegTree seg(v.size());

	FOR(i, 0, N + 1) f[i] = 0;

	FOR(i, 0, N + 1) {
		int x = lower_bound(v.begin(), v.end(), sum[i]) - v.begin();
		if (!f[x]) {
			f[x] = 1;
			seg.update(x, i);
		}

		int y = upper_bound(v.begin(), v.end(), sum[i] - P) - v.begin();
		int j = seg.query(0, y);
		if (j != INT_MAX)
			ans = max(ans, (ll)(i - j));
	}

	printf("%d\n", ans);
	return 0;
}

・参考になる記事

(1) Grundy数の概要が分かる記事

(2) Nim

・ 練習に良さそう

本題

・NimK について

実際に解いてみましょう！

組合せゲームの勉強に良さそうな本 (一般的なゲーム理論ではない方)

はじめに

ゲーム問題へのアプローチについて

問題概要

解説

コード

問題概要

解説

コード

・練習に良さそう