$<.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。苦しい。
k = (b/p+1)/2)がまったく一筋縄ではいかなかった。他にもね、14 行目と 15 行目にある２つの式 k*k*p と (k+k+1)*p が似てるでしょ。自分の目には同じに見える。取り違えてもしかたないよね。それから、後半７行でやっているボーダーライン上のアイテムを買えるだけ買う処理だけど、これ単純に割り算で計算できるらしい。二分探索で求めたボーダーラインの意味を考えればその通りなんだけど、半信半疑になってしまうところがあると思う。■F 問題まで解ける問題が並んでいて、だけど時間内に解けたのは C 問題までってどういうことですか。最近の問題傾向のせいにしてもいいですか。自分は数字とか式を精密に扱うのはまったく苦手なので、たこ焼きに関する問題が解きたいです。文章で発想のヒントとなる過剰なディテールが与えられてるといいなあ。そして発想だけで解けるといいなあ。式変形とかまじ無理なんで、D と E が解けなかったのもそれが原因なので。■D 問題の早い人の提出を見てると、ループで１つの式の合計を求めて、４倍して１を足して答えにしていた (#61802287)。どういう見かたをすればそんなシンプルな理解に至れるのだろう。■F 問題に関連してセグメント木の max_right メソッドへの言及をいくつか見た。どうやらそれは前回の ABC388-F に関して自分が「セグメント木で解こうとすると、何をリクエストして何を得るかという検索インタフェイスがどうあるべきかがよくわからない」「懸案だった検索インタフェイスは左側の境界を与えて判定関数が true を返す区間の右端を探るメソッドということにした」(20250111) と書いていたメソッドそのものではないかという気がする。お名前いただきました。■E 問題。「制約を見たら M の上限が 10 の 18 乗だった。キューから M 回取り出そうとしたら TLE になるのは当たり前」とさっき書いた。AC までいった今だからわかるけど、キューから取り出す回数の上限は M 回ではない。(k+1)^2-k^2 = 2k+1 であることから、+1 個のコストは個数に比例して上がっていき、その和は２乗のオーダーになるから(Σk = n(n+1)/2)、取り出す回数は M の平方根である 10 の９乗に比例する。ていうかコストの定義が kkPi なのだからそれはそう。それでもやっぱり TLE になるように M の上限が 10 の 18 乗程度に定められている。■E 問題。ボーダーラインを求めてさらにボーダー上の境界に注目する問題としては PAST8-I「/2 and *3」を思い出す (#26574800)。知ってる問題だったんだよ。解法の枠組みが自明で、でも式変形が難しすぎた。(i-l)*(r-i) の簡単な式で数えられる。■自分のすべての提出。宿題が多すぎるんよ。D から精進でした。いつまで水色かわからんで。s[-1]=tt if !s.include?(tt) と帳尻を合わせている。自分はすごーく苦労して間違いながら回りくどい処理をした。提出 #62132900 (AC)。最後の文字を最初に取り分けてメインの上書き処理を通さなかったのがうまくなかった。あとから最後の文字だけ上書き処理をして、それによって余ったすでに上書きに使われていた T の文字が無駄にならないように玉突きで再利用を繰り返した。玉突きの適切なインデックスを求める 19 から 21 行目と 28 行目の find メソッドの条件がまあ間違いやすくて WA を２つ出した。N=M=5 程度の小さなランダムケースを作成して、スクリプトの解答と自分の解答(私はバイオコンピュータを内蔵しています)を突き合わせて NG ケースを探して見つけた。でもこの苦労は避けられたはずの無用な苦労だったと。■B 問題 XOR = MOD。A とほぼ同じ人数が通しているみたいだけど自分はこちらの方が解きやすかった(A 問題通されすぎ)。N を増やしながら愚直解を列挙してみれば、N=X が必ず最小の解として存在している。また、解の上限は 2N-1 らしい。N が２の冪乗のときにもっとも解が多く、区間内のすべてが解になる。そこを手がかりに前後の N の２進表現を考えてみると、０の数が答えの数(2.pow(０の数))を決めている。つまり、N の０だった桁が０か１に変化したものが X (決めつけ)。提出 #62134372 (AC)。K-1 のビットパターンを N の０のビットに埋め込む。■C 問題 A^n - 1。N+1 が素数だと解きやすい気がするんだけど、それだけ。こういう問題にアプローチする術(すべ)を持っていない。■D 問題 Moving Pieces on Graph。一応読んだだけ。基本的には最短経路+１本の辺があればコスト２を払って一方が待避することですれ違いができる。最短経路が部分的にでも２本に分岐していれば追加コストはいらない。もちろん全く共有辺を持たない最短経路が２本あるのでもいい。最短経路でなくても、+1 コストの経路には価値があるし、待避できる余分な辺がないならどんなコストであっても２番目の経路に価値がある(全体が輪っかのグラフを想像する)。どうやってコードにするかはわからない。コーディングだけが問題かもわからない。■D 問題。すごいケースがある。S と T が直線で通じていてそれ以外の迂回路がないとき、S または T から外部へ双方が待避して位置を入れ替えることができる。それはもう最短経路とか全く関係がない。■A、B がどちらも緑 diff だったらしい。ARC は怖いところだよ。緑落ち寸前の自分が解いているという事実に納得しかないけども。■■■D 問題に訪れた AtCoder 最高の瞬間。提出 #62153446 (WA×1/AC×63)。circle_like というケース名をヒントにランダムケースに傾向を与えてダメケースを探した。提出 #62154569 (AC)。補助なし時間制限ありでこんな問題解けるわけないよ(自分には)。正解を出力する他の人の AC プログラムを助けにしてデバッグに次ぐデバッグで数え切れないバグを潰してやっとこれ。■正解を知るのにこちらの提出 #62136607 をコンパイル(＆リンク)したものを使わせてもらっていたのだけど、ソースを読むと、変数 L と R を使ってささっと２つ目の最短経路を見つけている。どういうことか。それぞれ f(G,S) と f(G,T) に対応していることから S と T から BFS した結果かと思うのだけど(f 関数を読まない)、最短経路上にある各頂点について、一方(とりあえず S)からの距離をメモして、その距離に重複があれば迂回路があると判定できる？ 迂回路があるということは、S(または T) から等距離に異なる２つ以上の(最短経路を構成する)頂点が存在すること？ そうっぽいけどこれ当たり前にわかること？■自分がやったこと。S から BFS をしたあと T から後戻りすることで最短経路を１つ特定する。最短経路上の S を除く各頂点について、隣接頂点のうち最短経路にないものの S からの距離を調べる。自身の距離を d として、d-2 以下であることはありえない。d-1 である場合は、異なる最短経路が合流してきたことがわかる。d である場合は +1 コストの経路が合流してきている。d+1 の場合は、ここから分岐したのかもしれないし、+2 コストの経路が合流してきているのかもしれないけど、どちらの場合でも扱いは同じ。引き返してはいけないというルールがないので、分岐してすぐ戻ってくることで +2 コストの経路になる。S と T には特別な扱いが必要。S には合流してくる経路がなく分岐していく経路しかないので調べない(今は分岐路の合流点を調べている)。T に隣接する頂点で d+1 の距離を持つ頂点に注意が必要。さっき引き返してはいけないルールがないと書いたけど、T に限っては引き返す経路がすれ違いのための迂回路にならない。しかし +2 コストの本当の迂回路が合流してきている場合も考えられる。最初にやった S からの BFS を T で止めることでこの２つを区別できるようにした。これには +3 コスト以上の迂回路の合流を妨げない意味もある。あとは「すごいケース」への対応を追加でやる。WA×1 はこのケースへの対応がバグっていたせい。最初の１回の BFS 結果を流用するのをやめて、２回目３回目の BFS をすることで間違いがなくなった。たいへんすぎるよ。まずやるべきことがわからないし、やるべきことをやる方法がわからないし、正しくやるのも難しい。■■■『はじめての数論 原著第３版』を開いている。第21章は「法 p でのべき乗と原始根」というタイトル。C 問題は位数と原始根が前提知識として必要だったとわかる。そしてもちろんそれを知っているというだけで解けるなら問題にならない。私の観測範囲の C の初学者、構造体で詰まる人が結構いる。でもってポインタは案外詰まらない。」■構造体で詰まるという詰まり方に興味がある。ポインタでは詰まらないという点に関連付けて想像してみる。C の前に他の Python みたいな言語になじみがあると、数値など不変型とオブジェクトなどの参照型はすでに知っているものと思う。ポインタは参照になぞらえて理解できる。構造体はオブジェクトになぞらえて理解できそう？ C にしかなくて戸惑うのは、不変ではなく参照でもないもの、malloc せずに存在している構造体ではないだろうか。これは自分の実感に基づいた想像で、Ruby に散々なじんだあとで C++ を触ると、変数のごつさにびびってしまう。スライシングみたいな罠にもなるやつ。詰まり方に興味があるというのは要するに、構造体を malloc して使うのは普通にできるんじゃないかと疑っている。