/ 最近 .rdf 追記 編集 設定 本棚

脳log[20240225]



2024年02月25日 (日) [AtCoder] 昨日は HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)があった。結果は知らない。ABCD のふりかえりと EF の精進を書くよ。■A 問題「Yay!」。人間はひと目で見つけて数えて答えが出せるけど、コンピュータにやらせるのが同じ程度に簡単なわけではない。Ruby には便利メソッドがあるので Array#tally だとか Hash#invert を使って見た目だけは簡潔にできるけども、さもなければ手間を惜しまず堅実にステップを刻むのがいいと思う。■B 問題「Which is ahead?」。人から位置への逆引きインデックスを作っておく。A 問題より簡単では?■C 問題「Many Replacement」。昨日の不調はここから始まっていた。前から順番に置換表を更新していってもサンプルが合わない。それは、連鎖的な変換が考慮されていないから。連鎖的、再帰的ということで UnionFind で解けるだろうとは思ったけど、どうにも無駄に牛刀を持ち出しているように思える。結局置換表を逆順に更新していくことで答えが出せたけど、12 分かかってるんだよなあ。他所で読むまで気付いてなかったんだけど、想定解は置換表(サイズ26)を毎回スキャンして置換する 26×Q≦520万ステップの愚直解法だったんだろうか。そうか、フルスキャンをしても 26 か。■D 問題「Square Pair」。いかにも D 問題らしく、シンプルに効率を求められる問題。苦手な部類。平方数を列挙しようと思ったけど、上限が A.max**2 になるのでためらってしまった。A.max は 20 万。そのループの中で A の各要素について対になって平方数を作るものの存在を確かめるとなると、A.max×N≦20万×20万 になる。次は素数を列挙しようと思った。A の素因数になり得る素数は2万個以下。A を素因数分解して奇数個の素因数の積として分類し直すと、掛けて平方数を作る組み合わせは同じグループからの組み合わせに限られる。このように答えの出し方はわかっているが、果たして2万×N で間に合うだろうか。比較的遅いことはわかってるけどとりあえず Integer#prime_division を使った解答を提出してみて、それで間に合っていた。約1秒。他の人の提出を見ていたら 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 操作があるなら意味があっただろうけど、ないのでいらない。■自分のすべての提出。レート遷移は知らない。どれだけ減ったかなんて知りたくない。