AtCoder Regular Contest 217

　AB二完。Bはまあまあ速かった。実験したら解ける問題はある程度速く解ける（こともある）らしい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 217 AB二完。Bはまあまあ速かったがCもDも解けず。
A sampleがヒント。0 1 3 2 4 5 7 6……。
B 実験。各iを動かせると+2^i。iの左により大きいものが置いてある確率。
D Mが大きい方から考えると、ある品物を買うときの挙動が繰り返されるからメモ化できる気がしたが解けず。

— titia (@titia_til) April 5, 2026

C - Greedy Customers 2

　公式解説を読み、解説放送を見てAC。

・所持金のmultisetが同じなら、人がどういう順番で来ても買う商品のsetは変わらない

　というのが気付くべきポイント。これにも気付いていなかったので、コンテスト中のACは遠い。

　その後はDPなのだが……。

　品物がk個以上売れる確率を求めたいというのは良い。

　が、k回そういうDPを行うというのは意外だった。

　DP[i][j]でA[i]以上のお金をj人が持っている確率、とすれば、kを固定していれば遷移が回るというのは分かりやすい。が、kを固定しないと回らない（のか？　少なくとも解説ではそうなっている）というのが混乱しやすい気がした。

　なお、PyPyではTLEしたため、codonでACした。