. を数えるか @ を数えるかして、D を足すか引くかする。■B 問題 Daily Cookie 2。後ろから書き換える。愚直に N^2 の時間をかけて大丈夫。String の場合は検索開始位置が渡せるのでケチって線形時間にもできる。Array で検索開始位置が指定できないのはスライスを使えってことなのかなと思うけど、添字の調整が面倒くさいからやらない。■C 問題 Kaiten Sushi。配点がちょっと高い。上流にいる人が食べたいものをすべて食べてしまうという容赦ない設定は流し索麺を思い出す(Somen Nagashi)。あちらは離席して食べる時間があるけども、こちらは容赦なき総取り。人の列が減少列になるように間引いてから二分探索をしたけど、寿司の方をソートしてしまえば二分探索はいらなかった。計算量のオーダーは変わらないので実装はお好みで。■D 問題 Keep Distance。すべて出力しろと言っているのだから、愚直に列挙して間に合う制約になっている。DFS が書けますかという問題。あ、嘘嘘。愚直に列挙したら最大ケースが終了しなかったので先を見て予め列挙範囲を限定する必要があった。無駄なく列挙しないといけなかった。■E 問題 Expansion Packs。２乗の DP が許される制約(？)。解答形式が小数だからサンプルも小数で書かれているし、サンプルの２が自己ループを含むものになっているおかげでデバッグが捗って助かった。何をしたか。現在持っているレアカードの枚数 R とそこに至る確率をベースとして、今開ける１パックの期待値(＝１パック×確率)を答えに足し、レアカードが R+X 枚になる確率を配っていきたい。そうすると１パックあたり X 枚のレアカードを得る確率を予め計算しておく必要がある。そうすると１パックにレアカードが０枚で足踏みしてしまう場合があることに気がつく。こういうのは具体的にどうするとうまくいくかを考えた。１パックあたり３分の１の確率でレアカードが０枚に終わるケースで考えると、１回に２分の３パック開ければレアカードが期待できる。レアカードが入っている前提ではレアカードが X 枚入っている確率は、分母(全体の場合の数)が減っているのだから最初に求めた数字より大きくなるはずで、1/(1-1/3) の式で倍率を表すと丁度いい大きさになるなと考えた。要はレアカードが０枚の場合を含む全事象からレアカードが１枚以上の全事象への分母の減少率の逆数。しかし！ TLE が解消できなかった。C++ で書き直したものはループの範囲を限定したりといった小細工なしでも 39 ms で AC だったけど(#60354761)、時間内には間に合わなかった。制約に泣かされた。Ruby で通している人が１人いたので、これは泣き言なんだよなあ。■F 問題 Falling Bars。消えない回らないスライドしない、落ちるだけのテトリス。区間更新区間取得のセグメント木の最も基本的な使い方がわかりますかという問題。残念ながら区間更新ができるセグメント木を持っていないので、即座に撤退して E 問題の TLE 解消に戻った(解消できなかった)。あまりにもストレートな問題なので、区間更新ができるセグメント木を書くいい機会かなと思った。以前読んだ競プロに関する翻訳された PDF (現物をなくしてダウンロード元も不明) のおかげで、トップダウン式のトラバースが自分の実装に欠けていることがわかっている。セグメント木を最初に雰囲気で実装したときに、末端から LCA までを辿るようなアクセス方法になった。だけど遅延された(区間)更新が伝播するのは根から末端に向けてなので、ボトムアップ式のアプローチはまったく役に立たない。トップダウン式の辿り方をでっちあげて区間更新ができるものをがんばって実装したけど、TLE だった(#60355045)。もうちょっと実装を洗練させたり無駄を省いたり手抜きをしたりする余地がないか考えてみたいけど、とりあえずここまで。■F 問題。通った！ 提出 #60379219 (AC / 1143 Byte / 1869 ms)。さっきの TLE で再帰呼び出しをしていた４行を直接インスタンス変数を書き換えるように変更したら間に合った。今は 0 とか max とかをあちこちにrequire 'numo/narray' していた。うん、それはね、Rust も Crystal も numo/narray もローカルに、古い Windows にインストールできなくて試行錯誤できないから捨ててるんだ。あきらめがついてすっきりした。■E 問題。あきらめたと書いたそばから通っちゃったね。提出 #60486554 (AC / 355 Byte / 1966 ms)。しょうもないなあ。コードテストで判断すると、制限時間が３秒なら TLE だった提出も TLE ではなかった。TLE と AC の違いはアルゴリズムの違いではなく、スクリプトの記述の違いでしかない。だからしょうもない。でも飛び道具なしのピュア Ruby でも不可能な制約ではなかったと自分で証明してしまったんだよな。なんだよくやしいなあ、あきらめがつかないじゃないか。■■■@2024-12-18 ABC357-F の精進について 20241218 に書いた。ついでに書くけど、さっき通ったと喜んでいた ABC382-F への自分の提出 #60379219 (AC) にはバグがある。61 行目のセグメント木の初期化サイズが間違っているので、N が W よりたっぷり小さいときエラーが出る。