x.zip(y,z).map(&:sum).max(M).sum でいい。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版。仕様も変わっているので注意)」)