require 'faster_prime'
しているものを見つけた。なにそれ知らない。■E 問題「Last Train」。これは精進。パラメータが多くて頭が壊れてしまった。解法はすんなり出てくる。ゴールの N に到着する最も遅い電車を始点にしてプライオリティキューでダイクストラ法をする。しかしパラメータが多いのと、最短ではなく最遅を求めるというので、普段と勝手が違って無限にバグを生み出し続けて時間切れになってしまった。キューに入れるのは時刻と街のペア。たくさんあるパラメータはキューに入れる次の時刻を計算するために使う。あとはがんばって頭の中を整理すれば答えは合う。だけど昨日は、列車の運行を逆向きにたどっていることが合わさって、出発時刻と到着時刻の前後関係がどうあるべきなのかとか、判断をするその時刻に k 項ある等差数列の先頭末尾どちらの数字を使うのかとか、およそすべてのポイントで間違えた。■F 問題「Black Jack」。これも精進。昨日も今日も WA を出したがやっと AC が出た。まず、ディーラーの値 y が L≦y の範囲でどういう確率で分布しているかを知るために 0 から N まで DP をする。E 問題もそうだったけど、この問題も考えることが多くてこんがらかる。y<L の範囲ではサイコロを振るけど、L≦y の範囲では振らない。今 DP で求めようとしているある場所にいる確率というのは、同時に、サイコロを振って次の場所にいる確率を求めるために使う値にもなるのだけど、L を境界として両者が異なる値を取るということ。そこをきっちり区別しなければいけない。ところで、サイコロは D 面あり、DP のためには D 個の値の合計が知りたくなるが、愚直に合計するには D の数が大きすぎることがある。こういうことを1つのループの中で全部考えながら整理するのは非常につらい。今回も evall のとき(20240128)と同じように class を使った別解(#50640033)を書いた。解答の後半は前半とは逆に N から 0 に戻る逆順の DP をした。N にいるときがスタート。サイコロを振れば必ず負け、サイコロを振らないときは y=N の場合を除いて勝つ。y=N の場合の確率は前半の DP ですでに求めている。後半の DP でもサイコロを振った場合の勝率を求めるために D 個の値の合計が必要になるので、前半と同じ class を使って楽ができる。そのクラス(LastNSum)を読み直していたら、@first が完全に無意味なことに気がついてしまった。pop 操作があるなら意味があっただろうけど、ないのでいらない。■自分のすべての提出。レート遷移は知らない。どれだけ減ったかなんて知りたくない。