質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.09%

【アルゴリズム】rubyによる深さ優先検索

受付中

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 2,659

score 11

環境

  • 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

+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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/02 20:38 編集

    コメントありがとうございます。
    当問題で間違いありません。TLE残り2つ、、素晴らしいです。。
    確かに、2次元配列⇒1次元配列は早くなりそうです。ありがとうございます。末尾再帰最適化はいまのところお手上げです。
    profile使って検証してみたいと思います。

    Atcoderの話に戻りますが、Rubyで大規模データを使ったD問題に対するACがないので、やはり厳しいのかなと。。ただ、なんとか、、!と思い、やるのもある意味楽しいです。仰っている意味は僅かながら理解できる気がします。。

    ありがとうございました。

    キャンセル

+2

質問された内容と違いますが・・・

コンパイルが必要な言語使ったほうが、コンパイル時に最適化してもらえるからよいです。

特にデータのサイズが大きくなって計算量が大きくなった時にLL言語は、よほどチューニングしても正当できないことがあるようです。

同じ解法をつかって、書いた言語の問題でパスしないのはもったいないです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/02 14:41

    コメントありがとうございます。
    仰るとおりで、コンパイル型の言語では同じ解法でもパスしますので確実だと私も感じています。
    なんとかLLであるRubyで実行してみたんですけどこのとおりです。

    キャンセル

  • 2016/06/02 22:08

    競技プログラミング初心者の方かと勘違いしました。大変失礼しました。
    ruby縛り面白そうなので、挑戦してみます。うまく行ったら報告します。

    キャンセル

+1

その問題、たぶん探索で解くべきではありません。線形計画法を用いるべきです。
表に、「ここからの経路はn通り」というデータをわかるところから埋めていき、最終的にスタート地点にその数字を埋めることができたら完了とします。

  1. 問題の表と同じ大きさの表を作り、すべてに「経路数=0」を入れておきます。
  2. すべての座標を、整数値の降順にソートします。
  3. ソートしたキューから一つずつ座標を取り出して次のことを行います。
    ●周囲の4点のうち、自分より整数値の大きい座標の経路数の合計を自分の経路数とします。
    ●いま埋めた座標がスタート地点であるならループを抜けます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/02 23:17

    私もこのやり方の方がスマートだとは思います。もちろん、データの偏りにも依るので、かなり偏っているのですかねえ・・・

    キャンセル

  • 2016/06/02 23:58

    お気付きの方おられると思いますが、この通りのアルゴリズムだと0しか出てきませんね。
    記述が足りていなくて、「四方がすべて自分より小さければ、経路数は1とする」が必要でした。

    キャンセル

  • 2016/06/03 10:42

    あと、「線形計画法」ではなくて「動的計画法」でした。線形計画法は高校の数学で軽くやった経営最適化のやつです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.09%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る