$<.read か gets かの違いか？ ローカルでも遅いから再現性があるんだけど、何が悪いのかさっぱり。提出 #61608160 (AC / 256 ms)。配列の shift をやめて添字アクセスにしたら数十秒が数百ミリ秒になって AC になった。S という配列に対して shift したり []= で代入したりするのがどういうわけか遅くなるみたい。それが [] と []= の組み合わせだと大丈夫だと。これが S という配列に対してイテレータでループを回している最中の話だと因果が見えやすいけど、そうではない。この時間の差は Ruby 3.1、2.7、1.9、1.8 までさかのぼっても変わらなかったので、Ruby で最初の提出のような書き方をしてはいけないということを自分が知らなかっただけということになるのだけど、何度見てもまずさがわからないのがやばいと思う。一応書いておくと、Ruby の Array#shift は要素を前に詰める線形時間の操作ではないし、shift 操作が(配列の実データ共有を無効化する) copy on write を引き起こすこともない。……と書いて気がついたけど、[]= による代入が配列のコピー書き換えを引き起こしているのだな。自分には S という配列が１つあるだけにしか見えないから、書き換え前にコピーしなければいけない理由がわからないけど。shift には注意しよう。あ、問題について書いていない。各人が配る石がどのタイミングで尽きるかをメモしておいて、あとは決まった流れを再生する。■E 問題 Simultaneous Kagamimochi。上に乗せるおもちは小さい方から順番に選んでいくしかない。最初に間違えたのは、一度下にしたおもちを上に乗せるおもちに再利用してしまったこと。それで乗せ替えをしたりややこしいことをしてなんとか答えを合わせたけど、おもちを前半と後半に分けるともっとすっきり解けたのだろうか。■F 問題 Dangerous Sugoroku。黒マスブロックの前後に集中する BFS なのかなと思ったけど、いい具合に集中する手順が出て来なかった。■G 問題 Simultaneous Kagamimochi 2。セグメント木で連結を工夫して二分探索でできないかな。■E まで解いてまさかの緑パフォ。あまりにも厳しい。■■■精進。G 問題。セグメント木でどのセグメントをどのように連結して答えに近づいていくかを考えていたら、それってダブリングぽいなと思った。提出 #61669596 (AC / 503 Byte / 1728 ms)。セグメント木ではなくダブリング。たぶんメモリ使用量の点で、ざっくり要素数の２倍を使うセグメント木に対して、ダブリングのために要素数×log2(要素数)のサイズのデータを準備したのが不利だと思う。しかし 2 対 18 は定数倍の範囲。できあがったものは実装途中よりもシンプルになったけどすんごくややこしくて、バグはなかったけど寝る時間がなくなった。実はやってることは E 問題への提出 #61589354 とあまり変わらなくて、高速に乗せ替えをするためにセグメントごとに前計算をしたみたいな感じ。セグメントの連結というのが上のおもちと下のおもちがオーバーラップしないように乗せ替える操作にあたる。乗せ替えると何が起こるかというと、前計算で得ていた下に敷くおもちのインデックスが右にずれる。どれだけずれるかは添字との差だけから計算できる。E 問題を解くのにそんな回りくどいやり方をして時間を無駄にしていたのだった。ダブリングでなくセグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない(だから都合良くダブリングを採用した)。二分探索をセグメント木の外部に担わせると木の操作の log と合わせて log が２乗になってしまうけど、log は１つで済ませられるはずなので(実際そうだった)、セグメント木に探索を丸投げするために何をリクエストすればいいのか。汎用性(普遍性)のある問いとは何か。■セグメント木に乗せるのは下に敷くおもちのインデックスそのものではなくて、いくつ右かというオフセットにするのがいいらしい？ そうすると l+k+max(l...l+k)≦r で判定できる？ k を二分探索すると log が２乗になるので Ruby が許されるかどうか。提出 #61683769 (TLE×13/AC×33)。許されなかった。残念。もう AC があるので定数倍改善の意欲はありません。しかし、インデックスの代わりにオフセットを扱うだけでびっくりするほど簡単にセグメント木が利用できるようになるのだね。そういううまいやり方があるのは ABC371-F「Takahashi in Narrow Road」(20240914) のおかげで知っていたはずだけど。「FはまずXi←Xi-iとすることで条件を狭義単調増加から広義単調増加に書き換えておく。すると用事を完了するためには邪魔になる人もろとも目的の座標までずらせばよく、」(週記（2024/09/09-2024/09/15） - kotatsugameの日記)。他には ABC353-G「Merchant Takahashi」(20240511) も同じようなセグメント木の使い方をする。セグメント木ではないけど ARC120-C「Swaps 2」(20211022p01) も同じ発想で解く。以前はポテンシャルという勝手用語で説明していたけど、改めて共通点を見つけ出そうとすると、絶対相対変換という見かたができると思った。位置相対的な値をセグメント木に乗せても共通の土俵で比較することができなくて困るときは絶対的な値を乗せる。そしてややこしいことに逆のニーズもあって、今回の F がそうなんだけど、絶対座標が扱いにくくて相対値を乗せたいこともある。そういうテクニック。■ついに許された！ 提出 #61689758 (AC / 1030 Byte / 1837 ms)。セグメント木。定数倍ではなくオーダーを改善して log を１つにした。懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした。しかし 118 ms オーバーで惜しくも TLE (#61689533)。しかたがないので判定関数ではなく判定の閾値を引数にして判定処理を埋め込む苦肉の策でやっとの AC。苦しい。