Ruby
競技プログラミング

Rubyのstack level too deep回避をファイル内で完結させる

More than 3 years have passed since last update.

競技プログラミングでは、深すぎる再帰がしばしば問題になる。

キューや(データ構造の)スタックを使ってコーディングすれば防げるが、やはり再帰は便利である。

AtCoder Regular Contest 045 C エックスオア多橋君を例に取る。

再帰が深すぎる場合、Pythonでは、sys.setrecursionlimit()により再帰の深さを変更できる。

cf: http://arc045.contest.atcoder.jp/submissions/526958

Rubyには同様の機能として、RUBY_THREAD_VM_STACK_SIZE環境変数がある。しかし、この値自体をプログラム中から変更しても、挙動を変更することはできない。

オンラインジャッジには単一のファイルしか提出できないため、通常の方法ではスタック拡張は困難ということになる。

今回は、環境変数を設定しつつ自分を実行し直すことで、当該ファイル内で完結させることができた。

cf: http://arc045.contest.atcoder.jp/submissions/526902

if !ENV['RUBY_THREAD_VM_STACK_SIZE']

#Rubyパスを取得するには、rbconfigかrubygemsを使う。AtCoderでは--disable-gemsされているので、require 'rubygems'は必須である。
#require 'rbconfig';RUBY=File.join(RbConfig::CONFIG['bindir'],RbConfig::CONFIG['ruby_install_name'])
require 'rubygems';RUBY=Gem.ruby
exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},RUBY,$0) #100MB
end

ただし、binディレクトリは移動可能(librubyはRPATHから拾える)なので、その場合には対応できないことは留意。