ABCDFの5完。Eがわからなかったけど面白くて考え続けてしまった。Fは16分くらいで解いたと思う。今回は好きなセットだった。
（今日のABCは楽しかったし力も出せたと思うけど）最近の競プロに対するやる気のなさは、精神状態が苦しくないからかもしれないな。競プロは苦しいときの逃避先になる。
先週は金土日とAtCoderがあって、今週は土曜のABCのみ。おいうリーグのチャレンジャーリーグが、先週は公式大会があったため試合がなく、今週は金曜と日曜にあるという、自分にとってめちゃくちゃ都合のいいことになっていた。
てかなんでTwitterも見ずにブログ書いてるだけで2時過ぎてるんだよ。ずっとEを考えてたからだね。そもそも復習しながらブログを書いてたら2時間かかるのは当たり前。
A - Daily Cookie
自由度があってB問題より難しいようにも思える。空き箱の数を求めるので、空き箱に変化するD個に加えて現在の空き箱を数える。
B - Daily Cookie 2
A問題の時点で左右の概念があったけど気づいてなかった。右から見て空き箱でないものを空き箱にする操作をD回まで行う。このB問題は好き。
C - Kaiten Sushi
350点で警戒するが、各jに対してA_iがB_j以下となる最小のiを求めればいいだけだ。パッと思いつくのはセグ木二分探索。もう少し考えると、Aを左から累積minで塗り潰してしまって二分探索すればいい（左に自分より美食度小さい人いたら一つも食えない）。広義単調減少の数列を二分探索するので、std::greaterを使う。ABの要素が小さいのでlogを付けない解法もありそうだが、コンテスト中は急いでいるのでそこまで考えない。
終了後に解き直した。美味しさを与えると誰が食べるかを返すテーブルを作る。2*10^5から始めて、A_i以上のまだ塗られてない領域をiで塗り潰す。思ったより短いコードになった。
D - Keep Distance
問題文を読むと、ボールに仕切りを入れるやつだ。仕切りをN-1個入れると勘違いしていたが、N個だった。数列の自由度がない場合はボールが0個。共通している+10を除いて考えて、1以上でなければならないのも考慮すると、制約にある10*N-9が出てくる。これをMから引けばボールの個数になる。制約からボールは最大でも9個、仕切りが最大12個なので、出力する数列は最大で30万個くらい。長さ12の数列を30万個出力させるのはAtCoderの出力量として見たことないくらい多い。だからTLも5秒なのか。Googleで21C9を計算する方法がコンテスト中はわからなかったけど、「21 choose 9」でググればいいのね。あとは、仕切りとボールを0と1で表してnext_permutationで出力していくだけだが、順方向に回したら辞書順の逆になってしまったので、ここでもstd::greaterを使った。個数の出力が必要なことに気づいてなかったので、まず空のnext_permutationを回し個数を求めた。
E - Expansion Packs
1回の開封で0枚からN枚増える確率をDPで求めておく。次に、ちょうどi枚になったときの開封個数の期待値をDPできないか考えるが、はっきりしない。最後に何枚増えたかで貰うDPをしたが、今考えると最後にj枚増えた確率は簡単にはわからない。X枚「以上」というのも難しい。簡単にできそうなのにできなくて、面白い。そもそも開封して枚数が増えない場合もあり、これはあとから考えて「増えないループ」を抜け出すまでの回数の期待値は求まると気づいた。それを操作回数に相当するコストと思えば、必ず枚数が増える場合に帰着できそう。サンプル合わすだけのこともできなくて、結局3乗（「増えないループ」を除けばX回以下で終わるので何回で何枚になる確率というのを全部DPで求める）でサンプルは合ったが、FFTの形をしているので高速化できる気がしない。根本的に方針が違うのかもしれないが、何も思いつかない。
（追記）解説を見る。i枚増える確率を求めておくのは解説でもやってた（P_iが100種類しかないので、やらない可能性も考えていた）。そして、解説で求めているのは、ちょうどi枚になったときの期待値ではなくi枚以上になるまでの期待値。これも当然考えてはいたが、何が違うのかよくわからないままだった。あたらめて考えるとなんかできそう（自分が全くできなかったことが簡単にできては困るという感情と、そもそも難しくて解説が理解できなかったら困るという感情のバランスをとりながら進むの難しい）。配るか貰うかでも迷う。いや初めて3枚以上になった状態から4以上の目（1からNの目が均等とは限らない決まった確率で出るサイコロで考えている）を出すと7枚以上になるって考えても、3枚以上は既に7枚以上かもしれないわけだし。そもそも最後にどんな目を出して7枚以上になるかの確率は簡単にわからない。で、解説をちゃんと読むと、それについて書いてない。今度は解説放送を見る。そのことについて説明されるか不安を抱えながら時間をかけて見る。そしたら、「初めてi枚以上になるまでの期待値」を言い換えて、「すごろくで残りiマスのときの期待値」としていた。うわあ逆なのか。自分は今までスタートからゴールに向かってDPをしていたが、ゴールから後退解析みたいに考えるんだ。そしたらまんますごろく典型じゃないか。添え字が逆だから気づかなかった（は？？）。じゃあさっきの疑問は？X枚以上になるまでの期待値について考えて、これからX枚以上を目指す最初の開封でちょうどj枚出たとき、そこからはmax(X-j, 0)枚以上になるまでの期待値になる。なるほど解説はそういう意味だったのか、自分の思い込みのせいで読めてなかった。「3枚以上」というのは、「ゴールまであと3枚だから3枚以上入手すればいい」ということであって、「スタートしてから3枚以上入手した」という意味ではなかった。値としては同じだけど。また、SSRSさんの提出を見て、（すごろくで考えて）各マスに降り立つ確率を求める方法でも解き直した。何回目の移動かを全部まとめて扱うと、（さっきのは3乗だったけど）2乗でできる。マスiを訪れる確率を求めるには、直前に訪れたマスで場合分けすればDPできる。ゴールまでに（スタート地点を含め）訪れたマスの個数の期待値がわかればいいので、各マスの確率を足していけば答え。
どう見ても解ける問題なのに解けないとき、その解けるのに解けないという「矛盾」を顕在化させて考えを進めるのが常套手段だが、コンテスト中は全然矛盾させることができなくて力不足を感じた。
