AtCoder Beginner Contest 404（Promotion for Engineer Guild）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 404（Promotion for Engineer Guild）Eで右側へ行けると誤読して時間を食う。Gは牛ゲーに見えるけど、どういう最短経路に帰着できるか分からず。
B 回転四通り試す。
C 次数は2か？　全頂点繋がっているか？
D 2^(2*N)全探索
E すぐ左の1へ行くまでの手数を求めていく。

— titia (@titia_til) May 3, 2025

F - Lost and Pound

　解説AC。解説放送も見た。

　分割数全部調べる方法は理解できたけれど、DP内でDPする方法の方が理解できず苦戦した。

　結局自分で（再帰で）書いて見たらACコードは書けたけど、かなり難しく感じた。

　残りターンT回、残り押さなくてはいけない回数K回のときの勝率をcalc(T,K)、とし、

（残りターンT回のとき）残りボタンを押す回数M回、kai回押す場所を決め、残り押さなくてはいけない回数x回のときの勝率をcalc2(M,kai,x)という関数を定義し、計算した。

　引っ掛かっていたのは、kaiという変数が必要なこと。

　kai回当たらなかった場合、当たりのボタンはN-kai個の中に含まれるので、当たりの確率は上がっているはず。

　解説や解説放送のDPではこれをどう処理しているのかが分からなかったので、必要ないのか？　と思ったけど、やっぱり必要でした。

　snukeさんのコードだと、26行目に(n-i)を掛けているのがそれに当たるんですね。

　再帰だと（多分）同等なコードが書けるけど、このDPを書くのは難しい……。確率DPは再帰じゃないと書けないかもしれない。

　

G - Specified Range Sums

　解説放送を見てAC。

　牛ゲーは、解説を見れば理解できるけど自力で構成するのは難しい。

　牛ゲーじゃないかと思ったときは、けんちょんさんのこの記事を見るのが良いかもしれない。