pop(K) かなと思ったけど、出力のしやすさから rotate(-K) にした。irb で確かめたら rotate(K) ではなかったから rotate(-K) にした。下から K 枚といういやらしい設定はちゃんと読めていた。■ B 問題「Decrease 2 max elements」。偶奇によらず A.sum/2 で間違いないことを確かめたと思ったらサンプルの２に殺された。場合分けをして祈りながら出した。こんなにはらはらさせられる B 問題はそうそうない。あ、シミュレートできる制約なんだ。無駄に考えてしまった。でも 100×100×100=100万のオーダーだと見積もるのも簡単ではないね。■ C 問題「Triple Attack」。シミュレートします。その際に、１周期(T を３増やして体力を５減らす)を超える処理は周期数を数えて一括して計算します。サイクルはどこから数えても１周した結果が同じだということを都合良く利用します。■ D 問題「Minimum Steiner Tree」。シュタイナー木とは見かけた名前だけど中身は知らない。調べませんよ。頂点を輪っかに並べて最小限の頂点と辺を選ぶアルゴリズムがあった気がしたけど、覚えていない。調べませんよ。テキトーに根を決めて、深さを計って、最も深い所から浅いほうへ向かって、必須の頂点を種にして、１つだけの共通祖先に行き着くまで親を取り込んでいくようにした。根に収束していくので頂点数程度の操作回数。テキトーに根を決めていいのか考えたけど、木は頂点間のパスが一意に決まるのでどこが根とか関係なさそう。終了条件を間違えて１ペナ。無条件にテキトーに決めた根までさかのぼってしまっていた。中断するときは、最も浅いところにある指定された頂点を取り込み忘れないようにする。X で見たけど、テキトーに決める根を V1 なり Vk なり必須の頂点の１つにしておけば何の面倒もなかったらしい。それは……頭がいいね。調べないと書いた２つ目は Auxiliary Tree という名前だったと X で見て思い出した。読めない名前はそのぶん手がかりが少なくて思い出しにくいかもね。そしてこれはこの問題には不適だったとも書いてあった。■ E 問題「Train Delay」。問題文が難しい。サンプルも利用して理解したところでは、ある１つの電車が遅延したとき、遅延によってできたはずの乗り換えが不可能にならないように、連鎖的に後ろの電車を遅延させていくと、遅延の合計はいくつになりますか、というもの。答えに選択要素はなく、無駄なく遅延させていけば答えになる。効率的にやるのが難しい。最初は電車の組み合わせを考えた。ある駅で発着する電車と電車で相互作用をさせる(相互ではない)。30 分かけて書いたこれは TLE だった。遅延の伝播をアドホックにやるのではなくトポロジカルソート順にやるのかと思って５分で書き直したものは、１つだけ TLE が減ったけどまだ TLE だった。たとえば半分の電車が駅１を発ち、半分の電車が駅１に着くとき、電車と電車の組み合わせは M^2 のオーダーなのだから、TLE はしかたがない。こういう、ダメな理由は、いざ TLE が出るまで考えないのです。途方に暮れていた時間を含めて 25 分でイベントソート版をでっちあげたら、総取っ替えの大手術だったにもかかわらず、TLE なしの WA×2 で筋が良い。その後５分で AC に至る。終了１分前。WA の原因は同時刻の発着を必ずしも着→発の順に処理していなかったこと。着イベントと発イベントを時系列順に再生しながら、駅ごとに最後に到着した電車の時刻(遅延込み)を記録しておくだけで伝播する遅延を確定していける。提出 #57090926 (AC / 397 Byte / 1847 ms)。昨日の日記(20240823)に「イベントを時系列順に並べることで考えるべき対象が限定できる」と書いていたことを思い出せたのが打開のきっかけ。■ F 問題「Dividing Game」。配点が同じなので最初に実装を始める前に F 問題まで問題を読んでいた。「ゲーム、Nim、Grundy 数、うっ、頭が……」ということだけ確認してから A 問題からの実装を始めた。F 問題が簡単だとは言わない。自分には解けない。答えに至る論理の道筋を納得しながら辿ることができないので。Nim の必勝法とか XOR のあたりで論理がお隠れになる。だから他の人も同じように解けないでいて欲しいのだけど、順位表を見ると 2454 人が通している。それはおかしいよ、俺に優しくないよ。ちなみに E 問題の方は 327 人。問題文が難しいし長かったからね、読みたくないからしかたないね。■自分のすべての提出。■精進……失敗。G 問題「Add and Multiply Queries」。前々回の F 問題 Maximum Composition を思い起こさせる設定。セグメント木なのかな、自分には乗せられないなと思っていたけど、「A,Bは正なのと、3つ目のクエリの条件より、区間内にB[i]が2以上な物は高々log(10^18)個程度しかない。B[i]=1の部分は、v+=A[i]をした方が良いのは明らか。よって各クエリに対し、B[i]=1の部分はBITを使ってA[i]の和を一気に加算し、B[i]＞1のところだけ加算と乗算どちらを取るか両方試していこう。」というのを読めば自分でも実装できる。提出 #57100689 (TLE×1)。こんなのってないよ。■最近タイプミスが多すぎるんだけど、たぶん爪が長い。白い部分が長いもので 6 mm ある(モニターの前に裁縫用のメジャーがあります)。短いのは 0 mm。むしろマイナス。ついつい噛んだり裂いたりしてなくなってしまいがちなので、触らないようにして最近は保護が行き過ぎている。長い爪というのは他の爪を攻撃しやすいのであり、また、長い爪というのは側面のちょっとしたささくれからぺりぺりと裂かれやすいのであり、攻撃力が高く防御力は低く、たいへん失われやすいものであるので、衝動を抑えていられる限りアンタッチャブルにしておきたいと思っているが、不便だな。ということをこの場所に書いているからには、不便を感じる機会が他にはあまりないということなんだな。■■■精進成功。G 問題。提出 #57153896 (AC / 918 Byte / 1161 ms)。配列の全長が高々 60 だとわかっていれば、長さ N の仮想配列に対する対数オーダーの処理を提供する BIT を使う必要はなくて、普通の配列に線形オーダーの基礎的な操作を施す方が定数倍がいいという話。というより、「次」を見つけるのに対数時間ではなく定数時間で済むという付加価値が大きいのかな。これでネタバレを恐れずに Ruby で唯一の AC だった konayuki さんの提出 #57098548 (AC / 1861 ms) を見に行ったら、クエリ３の答えをメモしていた。そう、１ケースだけだから、どういうクエリに弱いかを特定して対処しようと自分も考えていた。でもテストケースが見られないとなかなかわからないよね。■ちょっと勘違いをしていた。クエリ３の計算結果に制約があるのであって、1<Bi (i=1..N) なる要素の数が制約されているわけではない。だから B 数列の２以上の要素を管理するのに BIT ではなく Array を使うのにはリスクがある。ほとんどがクエリ２であるテストケースがあったら O(QN) で TLE だった。