こんにちは。昼過ぎに起きて洗濯や自炊をしていたらもう7時になって愕然としていました。とーです。
ABC:032B,C/054B/060D/112C
ABC060D
ナップザック問題やんけ！できるかも！と思ってやってみたところ、重さdpしか知らないため制限重量W <= 10**9ではとてもじゃないけど扱えないということで答えを見ました
この問題のキモは、与えられた品物の重量の最大値と最小値の差が高々3しかないということ つまり、最初に重さごとに分類しておいて、それから「重さxの品物をいくつ取るか」ということを全探索で求めていけば十分間に合う（最悪の計算量は、100個の品物が25個ずつに均等に分かれて、品物をいくつ取るかの選択が25**4となるときだが、これは10**6よりは小さいのでなんとか間に合う）
pythonは実行時間がやや遅いので、ここでは工夫して、まず品物を重さごとに分類した後で価値の高い順にソート→前から累積和をとっていく（つまりリストのi番目が、そのリストの中からi+1個選んだことに相当する）ようにした これによって、品物をいくつ取るかを決めた時点で、その個数選ぶ際の最大価値が一目で分かるようになった
しかし、初めから特定の重さの品物がないときは、例外処理の全探索のコードを書くのが難しくなるので、品物を0個選ぶのと、価値0の品物を一つ選ぶことは等価と考え、ソートして累積和をとった後でリストのケツに0を突っ込む作業をした こうすることで、例外処理をする必要がなくなる
ABC032C
数列の中にある部分列の項の積を、与えられた数字Kよりも小さくなるようにしながら、できるだけ長く伸ばすと長さはどんなもんよ？っていう内容
しゃくとり法というやり方が使えます（蟻本にはp.137あたりに、部分列の項の和を求めるところでこの手法を使っていますが、今回は積で使っています）
イメージとしては、
①スタートとゴールを持っておく
②スタートからゴールまでの積がK以下であればゴールを延ばす（そのうえでゴールの数字を掛ける）
③スタートからゴールまでの積がKより大きくなったらスタートを縮める（そのうえでスタートの数字で割る）
というのを繰り返しやっていく
結構簡単そうに見えるが実装の際に気を付けなければならないことも多く、メジャーなものとしては
①スタートがゴールを追い越さないようにする
②ゴールが数列のケツにたどり着いた時点でゴールを延ばすのをやめる
みたいなのがある
また、足し算の実装は比較的簡単だが、掛け算になるとこれまた気を付けるべき点増えて、この問題に限って言えば、
①数列の中に0が入っていたら、Kがどんな数字であれ条件は満たされる
②K == 0である場合、数列の中に0があればオッケーだけど、逆に0がない場合は条件を満たすような部分列はない（これはコーナーケースでひっかかりがち）
③例えば数列が 2 2 2 2 でK == 16なら、掛け算が一度も止まることなく（始点と終点を動かすことなく）最後まで行ってしまうのでちゃんとカウントを最後でとめる
といった点に注意すべきである
とりあえずpython3でのコードを書いたが、これもっと改善できると思うので、次回解くときには簡潔に書く工夫ができたらいいな
解けなかった問題
ABC:059D
ABC059D
grundy数というのを使う
grundy数というのは
①その状態からどの状態へも遷移できない場合を0
②遷移できる先があれば、その遷移先のgrundy数以外の最小の非負整数をとる
という数
簡単な例で言えば、爆弾ゲームというのがある
小学校で、「0から始め、交互に1または2を足して、最終的に11を言った人の勝ち」というゲームをしたことがある
結論から言うと、これは先手必勝のゲームである これをgrundy数を使って考えてみる
これにgrundy数を当てはめてみると、まず11は0である（このゲームの終わりなので）
そして、10は11に遷移できるので、grundy数は1
9は、10,11のどちらにも遷移できるので、0,1以外の最小の非負整数2をとる
8は、9,10に遷移するので、9,10のgrundy数2,1以外の最小の非負整数の0をとる
......とやっていくと、0~11とgrundy数の対応表は以下の通り
数字 0 1 2 3 4 5 6 7 8 9 10 11
grundy数 2 1 0 2 1 0 2 1 0 2 1 0
これを見ると、
①grundy数が0でなければ、必ず一手でgrundy数を0にできる
②grundy数が0であれば、遷移先のgrundy数は0ではない
となる
必勝法を考える上ではこの言い回しはやや分かり辛いが、結局のところ、先手が自分であるならば、もし自分のターンでgrundy数でを0にした状態で相手に回したら、次の相手のターンでは、相手はgrundy数を0でない状態にしてこちらに回すことになるので、こちらが最適な行動をとれば、相手に負け確定の9,10（9,10はgrundy数が2,1）を押し付けることができる、ということになる
先手は0から始めて2,5,8,11の順で必ず言うことができるので、こうすれば必ず勝つことができる
ニムもこれと本質的には同じで、最後にgrundy数（もしくはXOR）を0にした方が勝ちというゲームの場合、
初期条件のgrundy数（XOR）が0ではない→先手必勝
初期条件のgrundy数（XOR）が0→後手必勝
という風になる
0にした方が負け、という場合は、先手と後手が逆転する
さて長々書いてきたわけだが、このゲームでも同じように考えるとどうやら山の石の数が(0,0),(0,1),(1,0),(1,1)がgrundy数=0の状況になるので、最終的にこの状況に自ら持っていくことができれば勝てるということになる つまり最初のgrundy数が0でなければ先手必勝、そうでなければ後手必勝
逆算して石を増やしていくと、grundy数==0となる場合は、二つの山の石の個数の差が1以下であるときになるそうです（これはちょっと実装できてないので確かめられない）
例えば石の数が(2,1)なら、初期条件のgrundy数は0で、Alice(先手)が山を(0,2)にしてBrown(後手)に回さなければならず（この時点でgrundy数!=0）、Brown(後手)は(1,0)でAliceに回すことになり、この時点でgrundy数は0になったことになり、初期条件のgrundy数==0→後手必勝が分かります
これはまたあとで実装力をつけたらやりたいと思います トホホ
