if ～ else ～ end と書いているところがあちらでは until groups.empty? do ～ end になっていて、新しい配列を伸ばす一方ではなく処理対象にしてしまっている。そのおかげで一度のスキャンで必要な処理を終えられているのだろう。自分のように何度も何度もスキャンしないで済んでいる。それ以外の部分は全体的によく似ていて理解がしやすいあたり、O(N) 解法までわりと惜しいところまでいっていたのだな。解説に書いてあった O(N) 解法のヒント(凸包)が何のことかはさっぱりわかりませんが(「俺は凸包の点数はいらねーんだ」「それは自分の人生とは一切関わることのない専門用語」)。■まねまね>提出 #30381972 (AC / 66 ms)。Span.new(0,0))を配置する。提出 #30372922 (AC / 64 ms)。実際これで Span#accl_l と Span#accl_r の呼び出しが減るんだけど、ケースが弱くて差が出ないどころか遅くなったように見える。■いや、初期値は不定(nil)にして、一端が不定のあいだは他端に隣接する区間から打診されるどんな速度も(上限に関わらず)受け入れるようにしないと N の２乗は改善しない気がするな。(k-1).times を k.times にすると合うようになる(search メソッドの仕様が適切にコメントしてあるからすぐわかる)。あとは速度だけ。それも 2182 ms であって 22xx ms とは違うから 182 ms 削るだけ。■テストケースが利用できる Cutting Woods でソート済み配列の分割パラメータである A,B を 30,60 から何パターンか変えて実行してみると、ほとんど傾向は変わらないんだけどやっぱり 2,3 くらい極端だとちょっと遅い。Ruby で実装してるから動的配列でありオブジェクトであるノードを細かく分けると空間コストも操作コストも無駄に大きくなりがち。スクリプトはできるだけ多くの処理をインタープリタに任せる方が性能が出やすいと思う。もちろんインタープリタもアルゴリズムのオーダーには従うから構造を工夫しているところではあり、その範囲内でのことだけど(全部を１つの Array につっこむ無茶をインタープリタに任せるとは言わない)。■めでたい。提出 #29810599 (AC /「2-3木 (高速化した第2版。仕様も変わっているので注意)」)
Twitter で読んだけど ABC217-D「Cutting Woods」を Ruby でまじめに解いた人は対策ができていたらしい。自分は(略)なかった」 嘘だった。別解として BIT バージョンを通していた>提出 #28790707 (AC)。「対策」とは値から添字を逆引きする BIT のあまり一般的ではないメソッドのことであり、これを通したのがちょうどひと月前だってのに、どうして今日通せなかったの？■@2022-03-01 20220228で (30,60)-木を使って通したあとだけど、コンテスト中の最初の方針であった BIT を使っても D 問題を通したよ>提出 #29790983 (AC / 1944 ms / 後註)。Hash ベースの BIT でギリギリ間に合ってるのに最初の提出(Array ベースの BIT を使っていて有利)で RE/WA/TLE になったのなんでだろう。ともあれ、WA の原因は BIT の使い方に間違いがあったからなんだけど、貼り付けた自分のコードが信用できなくてサンプルを合わせるときに手を入れる場所を間違えたんだな。RE/WA だけならデバッグをがんばれたけど TLE もあったので諦めてしまった。□(註) さっきの提出のコメントに嘘があった。「
アクセス可能な範囲(0..@n-1)なら」の正しい範囲は
0..@n-2。スクリプトは合ってる。コメントだけ嘘。The series of pairs is separated by the ampersand, "&" (or semicolon, ";" for URLs embedded in HTML and not generated by a <form>...</form>. See below).」「
This convention is a W3C recommendation.[6] W3C recommends that all web servers support semicolon separators in addition to ampersand separators[9] to allow application/x-www-form-urlencoded query strings in URLs within HTML documents without having to entity escape ampersands.」 W3C がってところが今となっては、かなあ。もちろん立場が違えばセミコロンが解釈できなくて話が通じない相手とはそれまでっていうのが自分のスタンスなんだけど、AtCoder には合わせるしかない。■@2022-03-07 最近 OpenBD のデータが、抜けているというより常に取得できてないなと気がついて見たら、セミコロン区切りのせいでクエリが失敗するようになっていた。ここでもなのか。
no! if U[a,b] の no! を取り除くとダメになるケース(8 4／3 3 3 1 1 1 1 1／1 2／1 3／2 3／7 8)がある。この提出 #29483417 (WA×1) を阻んでいる random_21.txt が同等の(無駄な辺と森化による辺の必要数の減少が相殺する)ケースだと思う。■■■E 問題「Subtree K-th Max」。最近似た名前の問題がありましたね>「Prefix K-th Max」。一読して表現の微妙な変化に気がついたんですよ。ABC234で「K 番目に大きい値」という表現だったものが ABC239 では「
大きい方から Ki 番目の値」になっていた。それが「中途半端な値は見ようによって大きい値でもあるし小さい値でもある。自分に言わせればそれは単に「大きい方から K 番目の値」なんであって、大きい値でも小さい値でもない」をうけての変化だとは思わないけど、自分が理解しやすい表現になっていたのは間違いない。それなのに AC 前の５分で 2 WA しました(WA、WA、AC)。読んで、表現の変化にも気がついて、でも結局間違えるんだ。手癖で書いてるってことなんだろうなあ。■「AtCoderの公式生放送「あーだこーだー」 第51回 - YouTube」を聞いていると E 問題「Subtree K-th Max」に関連して Wavelet Matrix の単語が何度も聞こえてきた。E 問題では K の上限が意図的に小さく抑えられていて、ここを突破口にして解けよ、というヒントがあからさまだったけど、さもなければ Wavelet Matrix を使って解くことになったらしい。Crystal では通ってるぽいのに Ruby で TLE になるの悔しいよね。通ってほしい。参考図書『[単行本] 岡野原 大輔【高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)】 岩波書店』は持ってるだけは持ってる。WEB+DB PRESS vol.42 の記事を読んで著者の名前を覚えていた。