質問: 環境 -- * Ruby2.0 * Mac OS X El Captain ver:10.11.4 前提・実現したいこと ---------- 深さ優先検索アルゴリズムを用いて、Rubyで問に対する解答を出したい。競技プログラミングの問題を一部修正しています。 問 - H×Wのマス目があり、各マス(aij)に整数値が書かれている。始めにあるマスにいて、そのマスの上下左右に隣接しているマスのうち、今いるマス目より大きな整数が書かれたマスに移動できる。 ありうる経路の数を10E9+7(=1000000007:素数)で割った余りを求めよ。 ### 制約 * 1≦h,w≦1000 * 1≦aij≦10E9 ### 入力 ``` h w # グリッドの大きさ a11 .. a1W # aijはマス目の数字 : aH1 .. aHW ``` 発生している問題 -------- グリッドが大きくなると、時間内に解けない。(どのオーダーでタイムリミットなるか把握できていませんが。。) 該当のソースコード --------- ``` MOD=100_000_007 ans=0 # 高さ、幅の読み取り h,w=gets.chomp.split.map(&:to_i) # マス目を格納する2次元配列及び、経路数を格納する2次元配列を用意 @grid=Array.new(h+2).map{Array.new(w+2,0)} @comb=Array.new(h+2).map{Array.new(w+2,0)} # マス目のよみとり (1..h).each do |i| @grid[i]=gets.chomp.split.map(&:to_i).unshift(0).push(0) end def dfs(i,j) # 動かない場合もあるのでres=1 res=1 # 既に探索した木ならその値を返す return @comb[i][j] if @comb[i][j]>0 # 上下左右のほうが大きければ移動する res+=dfs(i,j-1) if @grid[i][j]<@grid[i][j-1] res+=dfs(i,j+1) if @grid[i][j]<@grid[i][j+1] res+=dfs(i-1,j) if @grid[i][j]<@grid[i-1][j] res+=dfs(i+1,j) if @grid[i][j]<@grid[i+1][j] # 移動経路数を2次元配列に格納し、値を返す @comb[i][j]=res%MOD return @comb[i][j] end (1..h).each do |i| (1..w).each do |j| ans+=dfs(i,j) # MODより大きければ引く if ans>MOD ans-=MOD end end end puts ans ``` どこを修正すると速くなるのか教えていただきたいです。 よろしくお願い致します。。
回答: AtCorder ABC 037 D問題であってますでしょうか? 頑張ってTLEを残り2個まで減らしました。あとは、よろしくお願いします(えっ)。REの1個は再帰呼び出しが深すぎてスタックオーバーフローだと思われますので、これを解消するにはyubaさんが言うような方法にするなど、戦略から書き変えないと無理です。(末尾再帰にしてスタックを使わない最適化に変える事もできないことは無いかも知れませんが、Rubyで末尾再帰最適化はちょっとめんどくさい) 工夫した点は主に`Array#[]`を極力なくすことです。まず、二次元配列ではなく一次元配列にします。Fixnumの四則演算に比べると配列へのアクセスは遅いのでそれだけで20〜30%は短くなるようです。あとは、計算結果を随時変数に入れるとか、なるべく計算しないように頑張ります。 Rubyで高速を目指すなら、profileの使い方を覚えると良いでしょう。ネックになっているところがだいたいつかめるようになります。私も競プロをRubyでといて遊んだりしますが、まぁ、時間がシビアな問題はだいたい解けません。しかし、それを乗り越える楽しさ...があるような気もしないではないと思ってます。 C++で解いた方が速いと言っても、高速すぎて単純な総当たりでも解けちゃうことがあったりすると興ざめですものね。 おまけ AtCoderは問題が表示されないので、簡易な問題作成ツールを作りました。良かったら検証に使ってください。 ``` h = 1000 w = 1000 puts [h, w].join(' ') h.times do puts w.times.each.map{rand(10**9) + 1}.join(' ') end ```