最初に

EDPC J - Sushiという競プロの問題をRubyで解いてました。

この問題自体は、大学受験数学の難しい方の典型にありそうな問題の延長で、確率の漸化式を作り式を整理してメモ化再帰の形で動的計画法に乗せると解けます。

詳しい解説は、kyopro_frienedsさんのEDPC解説記事(F～L)を読むといいでしょう。

しかし、Ruby 2.7だと、時間がだいぶギリギリです。 kyopro_friendsさんの解説どおりの解法をとっても、定数倍高速化をしないとTLEになります。式を整理して定数倍高速化をして、ようやく1900ms台に乗せることができます。そのせいか、RubyでACされてる方は、kuma_rbさんという方しかいませんでした。

多次元配列の要素数のちょっとした工夫で1950ms前後から1750ms前後と0.2秒ほど速くなったので、定数倍高速化の参考にのせます。

多次元配列の高速化

多次元配列を作るさいに、添字の順番が特に関係ないのであれば、多次元配列の内側よりも外側の要素数が小さくなるようにして、全体の配列数を減らした方がいいです。

n < mとして、m個の要素の配列をn個作る方が、n個の要素の配列をm個作るよりも、速いです。

生成の比較

require 'benchmark'
n = 10**2
m = 10**4
Benchmark.bm(12) do |r|
  x = r.report("a few arrays"){ a = Array.new(n){ [0] * m } }
  y = r.report("many arrays "){ b = Array.new(m){ [0] * n } }
end

#                   user     system      total        real
# a few arrays   0.000397   0.004267   0.004664 (  0.004749)
# many arrays    0.004898   0.004679   0.009577 (  0.009607)

ローカルで配列の生成を計測した結果で、明らかに差がありました。

配列を作るのは時間のかかる操作で、全体で配列を作る個数が減る方が速いのは当然なのかもしれません。

参照の比較

さらにアクセス時間でも検証しましたが、配列数の少ない多次元配列の方がちょっぴり速そうでした。

require 'benchmark'
n = 10**2
m = 10**4
a = Array.new(n){ [0] * m } 
b = Array.new(m){ [0] * n }

Benchmark.bm(12) do |r|
  r.report("a few arrays"){ n.times{ |i| m.times{ |j| a[i][j] } } }
  r.report("many arrays "){ n.times{ |i| m.times{ |j| b[j][i] } } }
  r.report("a few arrays"){ n.times{ |i| ai = a[i]; m.times{ |j| ai[j] } } }
  r.report("many arrays "){ m.times{ |j| bj = b[j]; n.times{ |i| bj[i] } } }
end

#                   user     system      total        real
# a few arrays   0.053819   0.000000   0.053819 (  0.053898)
# many arrays    0.089143   0.000000   0.089143 (  0.089156)
# a few arrays   0.045093   0.000000   0.045093 (  0.045101)
# many arrays    0.046487   0.000000   0.046487 (  0.046492)

その他

ハッシュでは速くならなかった

ハッシュを用いても、今回の問題では速くはなりませんでした。

多次元配列の代わりに多次元ハッシュを使うと、TLEしました。
多次元ハッシュの代わりに、数値を組み合わせて1つの数値にすることでギリギリAC。具体的には、[a][b][c]の代わりに、[(a * 301 + b) * 301 + c]という形。 1999msなので本当にギリギリです。

今回の問題でハッシュは有効ではなかったです。しかし、キーのパターンが少ないケースでは有効と思われるので、一概に決めつけずハッシュが有効なパターンも試してみるといい気がします。

EDPC J - Sushiのための高速化

ブログタイトルから離れて、EDPC J - Sushiの定数倍高足化について。

再帰関数内の分母･分子

再帰関数が呼び出される回数が多いところで、この再帰関数内の定数倍高速化させるかどうかでRuby 2.7で通せる･通せないが変わってくるようです。分母･分子で同じ値で割っていたらこの部分はコードで計算しないようにしたり、定義して1度しか使わない変数は定義しないようにする必要があったり、細かい部分を頑張る必要があるようです。

もっと速い別の解法

kuma_rbさんという方が1900ms台の解法以外に1350ms前後のもっと速いコードを通していて、根本的にもっと高速化させる方法があるようです。ちょっと見てみたのですが、異なる解法で難しそうでした。

最後に

このあたりのEDPCの問題は、Ruby 2.7だと厳しいですね。ちょっとした工夫で、ちょっと速くなることを知れたので良かったです。

universato's blog

【Ruby】多次元配列の定数倍高速化(EDPC J - Sushi)

最初に