.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) に書いてある。本の最初の最初のただの前置きみたいな部分なのに難しいね。