.reverse_each.inject を while .pop に、もう１つは .each を while .shift に。たぶん２つ目は時間に効くけどメモリに効くと意識したことはない。じゃあ Enumerator を返す使い方の Array#reverse_each に罠がありますか？ あと、ちょっとだけ余分な時間がかかり、TLE と AC を分けることもあると知られている多重代入が複数の代入に分解されているのも確認できるけど、これは最初にこれだけをやってみて効果がなかったのでカウントしていない>提出 #68965976 (TLE×2)。■提出 #68970098 (MLE×2)。これは最初の TLE 提出の .reverse_each.inject を .reverse.inject に書き換えただけのもの。reverse_each が罠なのかどうかを確かめたくて。結果は全体的に実行時間もメモリ使用量も何割か改善しているけど MLE になってしまった。そういえばメモリ制限は 1024 MiB だった。.reverse_each を .reverse に書き換えることで TLE は解消したけど MLE がそのままだったので AC にならなかった。ただの数値配列なのにメモリ制限が厳しい。使用済みのデータを随時破壊的にシュリンクしていって GC させないといけませんか。■Ruby の提出を時刻の早いものから見ていってる。提出 #68945143 (konayuki さん)。BIT を使って何をするのかわかりません。提出 #68947172 (hmmnrst さん)。なんとクエリ先読みが必要ない。クエリ２では x からと y からの両方を同時にたどってどちらが他方にたどり着くかを確かめている。自分の TLE/MLE の原因は x,y の順序を決めるための先読み部分の深さ優先探索にあったから、両方をたどってみるのが労なく AC できて正解だった。準備せずやってみるだけ！ 同時にたどるのがたぶん重要なポイントで、順番にたどってみようとするとリストの全体をたどってしまうことを覚悟しないといけなくて、それは Q^2 のオーダーで TLE になる。他の提出は全部 BIT を使わないリスト解法かな。リストを二重リンクリストにして x から両方向にたどってるっぽいヴァリエイションもあった。■直近４回くらい緑パフォ安定で結果は出ないしコンテスト中は全然おもしろくないんだけど、だからふりかえりも書かないんだけど、精進日記や精進未満日記が３つ続くところを見ると問題自体に問題はなくて解くのを楽しめているような気がするんだよね(そのように見える判断できるというだけで楽しいと思ってはいない)。でも圧倒的に時間が足りていなくて、この F 問題は問題を読んだのが今日だった。この難易度の問題を後日提出の宿題にしてしまってはいけないんだよ。でも D 問題も F 問題も１時間では AC にならないし、E 問題は解けてもいない。メモ化再帰で書こうとして書けていない。キープする面の組み合わせをを選んでその場合の数を数えたいけどできない。■■■D 問題についても書こ。時間内に１時間かけたものは半分 AC で半分 WA だった (#68940840)。おしまい。終了後に最初の実装を捨ててもう一度書いた。実装の機微がすでに明らかなので、位置関係を分類して (左,右,同じ)×(上,下,同じ) の９通りを実装するのはやめて、現在の両者の距離と１秒後の両者の距離がゼロかどうかと変化量を見て判断することにした。分類して予測するより単位時間の経過を見る！ 提出 #68953965 (AC)。D 関数がある時点の両者の距離で、X 関数がある時間の両者の重なり回数。実装し直しただけで AC になるのだから最初の提出の WA は実装ミスなんだろう。変化量が負になりうることを全く想定していなかったのでたぶんそのあたり。問題を一読したときから考える要素は１秒分もなかったけど、重なっている回数をうまく数えることができなかった。簡単な実装方針が見極められるのも実力のうち。ありませんでした。■■■リストを同時にたどるというアイデアが自分の頭から出てくる見込みがなさすぎて悔しいので、これが悔し紛れになるのかは知らないけど本で得ていた知識を１つ書こう。リストがループを持っているとき、その形は輪っかか輪っかにしっぽがついた「の」の字になるけど、輪っかがあるかどうか、あるとしたらそのサイズは何かを知るために２つのポインタでリストを同時にたどる方法がある(らしい)。アルゴリズムのキモはポインタの進む速さが異なっていることで、遅い方は１つずつ速い方は２つずつ進めていって、いつ２つが衝突するかを観察することから始めて、しっぽとサイクルの接続点を２つ(３つ)のポインタ以外の記憶領域を必要とせずに求めてしまう。そのときにはサイクルの長さもしっぽの長さも(数えたいなら)数え終わっている。というようなことが『プログラミング原論』の 2.3 衝突点 (pp.23-28) に書いてある。本の最初の最初のただの前置きみたいな部分なのに難しいね。宣言的でないコードは分離して端に掃き出すとよい」を自然と後押ししてくれるのが関数型言語のモナドだと思ってるけどよく知らない。■波線がないところに「波線」と書かれていたので、これは破線(ハセン)の変換ミスだなと思って自分でも変換してみたところ、破線と波線の読みがどちらもハセンだと知って驚いたのが今日の日記の中身。ナミセンには項目も立っていなかった。区別できないじゃん。
（1）（行きおさめる意）使者。」「
（2）旅行の荷物。旅行の支度。転じて、旅。」「
（3）旅行用の荷物入れ。竹または柳で編み、つづらのようにつくったもの。衣類入れにも使う。「柳―」」「
（4）軍隊の戦闘または宿営に必要な弾薬・糧秣（りょうまつ）・器具などを運ぶ部隊」■人だったり旅だったり荷物入れだったり軍の部隊だったり、いったいなんなのだ。旅にまつわる何かではあるのか。それにしても対象が
竹・柳などで編んだ箱形の物入れ。かつては旅行用の荷物入れに用いたが、いまでは衣類などの保存に使う。「柳─」」とだけあり、これは広辞苑の３番目の意味だが、自分が知っていたのはこれ。実物は見たことがないし見てもそれとはわからないけど、
IX = XI = X であるような行列 I を単位行列と呼ぶはずだけど、I がたぶん Identity の頭文字。英語では習わなかったけども。ということは、id の名前で返すべきは何の作用ももたらさない操作なのかなと。e と id の区別が難しかったんだよね。最大値を求める操作に対しての負の無限大、最小値を求める操作に対しての正の無限大、数を数える操作に対してのゼロみたいな、初期値としての e とは別に用意される id という「値」はなんだろう、というのが疑問だった。物理的な形式はともかくとして概念としての id は操作ですよね？ ということを納得すると、自分の実装で Op#nop? の名前を与えられている機能は Op#id? が相応しかったんじゃないかなあと思ったり。■コンテスト中の提出 #68152111 (AC / 1796 Byte / 2984 ms) と冒頭にコメントを付加しただけの提出 #68173358 (AC / 2433 Byte / 2596 ms)。ジャッジサーバーが使い回しではなく新規立ち上げだから１ケース目だけ 100 ms 余計にかかってる、みたいな話ではなく、全体的に１割程度の時間差がついている。再提出で 100 ms も差がつくことはないだろうと思っていたから意外に大きな差に驚いている。こんなんではコンテスト中に TLE だったものが終了後の再提出では AC になった、みたいなことが十分に起こりうる。特に遅延セグメント木と３乗の DP が解法となる問題ではシビアな定数倍低減が AC と TLE を分けるのでしゃれにならないよ。■■■@2025-08-07 精進。D 問題。提出 #68259724 (AC / 471 Byte / 1172 ms)。コメントに書いたけど「ひとたびテンションが 0..1000 の範囲に入ったら抜け出せない」ことが見抜けるかどうか。見抜けたらその範囲で DP をする。自分は見抜けなかったので 0..500 の範囲＋それ以上という括りでクエリ全体を一括シミュレートしてサンプルしか通らなかった (TLE×27/AC×3)。さらにもうひとつどこ以降の DP 結果を参照するかを決めるのに二分探索をする必要もあったらしい。すべてのネタバレ後に実装をした。実装だけなら D 問題だったけど考察ポイントが２つもあると問題を総合的に理解していないと解けない。断片的な手がかりからあれかなこれかなというアプローチでは解けない。「
クエリの大きさははったりだなと思ったけど、クエリの数もそうなんかな」と先に書いていた。大きすぎるクエリには二分探索で対応する。(シミュレートするには)多すぎるクエリは 1001 種類の入力にだけ対応した DP で予め答えを出しておく。それでいいそれでできるという判断に必要だったのが「ひとたびテンションが 0..1000 の範囲に入ったら抜け出せない」という洞察。ありませんでした。