【アルゴリズム】rubyによる深さ優先検索
受付中
回答 3
投稿
- 評価
- クリップ 1
- VIEW 2,527
環境
- 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
どこを修正すると速くなるのか教えていただきたいです。
よろしくお願い致します。。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
+3
AtCorder ABC 037 D問題であってますでしょうか？
http://abc037.contest.atcoder.jp/submissions/750568
頑張って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投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
質問された内容と違いますが・・・
コンパイルが必要な言語使ったほうが、コンパイル時に最適化してもらえるからよいです。
特にデータのサイズが大きくなって計算量が大きくなった時にLL言語は、よほどチューニングしても正当できないことがあるようです。
同じ解法をつかって、書いた言語の問題でパスしないのはもったいないです。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+1
その問題、たぶん探索で解くべきではありません。線形計画法を用いるべきです。
表に、「ここからの経路はn通り」というデータをわかるところから埋めていき、最終的にスタート地点にその数字を埋めることができたら完了とします。
- 問題の表と同じ大きさの表を作り、すべてに「経路数=0」を入れておきます。
- すべての座標を、整数値の降順にソートします。
- ソートしたキューから一つずつ座標を取り出して次のことを行います。
●周囲の4点のうち、自分より整数値の大きい座標の経路数の合計を自分の経路数とします。
●いま埋めた座標がスタート地点であるならループを抜けます。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.35%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2016/06/02 20:38 編集
当問題で間違いありません。TLE残り2つ、、素晴らしいです。。
確かに、2次元配列⇒1次元配列は早くなりそうです。ありがとうございます。末尾再帰最適化はいまのところお手上げです。
profile使って検証してみたいと思います。
Atcoderの話に戻りますが、Rubyで大規模データを使ったD問題に対するACがないので、やはり厳しいのかなと。。ただ、なんとか、、！と思い、やるのもある意味楽しいです。仰っている意味は僅かながら理解できる気がします。。
ありがとうございました。