週記(23/05/28)：Sushi

今週のまとめ

次女の誕生日お祝いでお寿司食べた
Thunderさん本を読み始める
ABC304は5完もUnrated…

です。

(本文中にEDPC J-Sushi, ABC 303 F, 304 D-Fの解法を含む話題が出てくるのでご注意ください。)

5/28(Sun)

次女の誕生日お祝いでお寿司へ。お寿司デビューなのでまずは回るお寿司から。

くら寿司へ行ったのですが事前予約ができたり、しゃりハーフサイズが選べたり^[1]この年になると少し割高でもしゃりを半分にしてネタを多く楽しみたくなる、お皿を回収してゲームができたりと色々と進化してますね。

寿司で思い出す競プロネタといえばEDPC「J – Sushi」。愚直に状態を持つとダメで期待値を出すのに必要な情報は何か？を考察して状態を見極める必要があるのですが初見時はまったく手も足も出なかった思い出の一問です。

5/29(Mon)

ABC303の「F – Damage over Time」をUpsolve。本番時は面倒なことを確認してGへ行ったのですが、思っていた通り？実装が面倒でした。

ターン数[math]K[/math]を決め打って与えられる最大ダメージを考えます。基本的にダメージの大きい魔法を使うのが良いので[math]d_j[/math]を降順ソートしておきます。

ややこしいのが残りターン数と魔法の有効期間[math]t_j[/math]で総ダメージが変わるところで残りターンと与えられるダメージを図示すると以下になります。

ざっくりいうと青実線部囲まれる領域の格子点数を出せばよく[math]O(N)[/math]かけても大丈夫なので区間[math][t_j, t_{j+1}][/math]ごとに長方形と台形の格子点を数えればよいです。

あとは[math]K[/math]を二分探索すれば解が求まります。

5/30(Tue)

昨日のABC303「F – Damage over Time」で拡張整数ライブラリを使ったのですが、オーバーフローを気にせず本筋のロジックに集中することができました。ただ、

%演算子
int/long longへのキャスト

がなくて冗長なコーディングになったのでこの2つも実装。

5/31(Wed)

高校の同窓会が20年ぶりにあって参加。当時の担任の先生も80才でしたが元気な姿をみせてくれトークも健在でした。

なんやかんやで日付が変わる近くまで飲んで終電もなかったので歩けるところまで歩いて最後はタクシーで帰りました。時計のログによると15km歩いたみたい。

6/2(Fri)

6/11のAHC020に参加できそうなのでThunderさん本こと「ゲームで学ぶ探索アルゴリズム実践入門」を読み始めました。

ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス

P.52のBeam searchまで。priority queueを使った実装が楽ですが、C++だとnth_elementが使えてこちらだと30%くらい速くなりました。知らなかったことがちょいちょい出てきて面白いです。

6/3(Sat)

ABC304の参加

55分(1ペナ)5完でちょっと冷えたなーと思ったらUnratedでした。かなりジャッジが詰まっててFはひたすら待っていたので仕方ないよなぁと思います^[2]本番ではFのジャッジですごい待った挙句、WAだったのでRatedと言われるとそれはそれで辛いですね。。

「D – A Piece of Cake」はケーキがそこまで多くないのでイチゴをケーキの端点に対応付けて個数をカウント。

最小が0になるかは「イチゴのあるケーキの個数」が「全体のケーキの個数」より少ないかで判定しますが、オーバーフローで1WA。全体のケーキの個数は[math]10^{10}[/math]くらいあると考察していたのにいざ実装ではすっぽり抜けてました(涙)

「E – Good Graph」は連結成分の親番号で管理すればOK。[math](x, y)[/math]の親[math](p(x), p(y))[/math]をsetで持って各クエリで[math](p(p), p(q))[/math]がセットになければYes、そうでなければNo。

「F – Shift Table」は[math]N[/math]の約数[math]M[/math]ごとに場合の数をカウント。ややこしいのは重複カウントを除く必要があって約数包除でググりました。本番はジャッジを延々と待たされたので手元でサンプル生成＆愚直解と比較したら落ちたのでそのデバッグをしているうちに終わりました。終了後20分位で無事AC。

来週はThunderさん本でAHCに向けた準備を少しでもできればと思っています。

前週の週記: 「七五三」
翌週の週記: 作成中

脚注[+]

脚注
↑1	この年になると少し割高でもしゃりを半分にしてネタを多く楽しみたくなる
↑2	本番ではFのジャッジですごい待った挙句、WAだったのでRatedと言われるとそれはそれで辛いですね。