トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 037

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 037 - D

  • AtCoder Beginer Contest 037 - D 経路
    • ある長方形の中の任意のマス目から上下左右のマスへ動くことができる
    • ただし動くことができるのは自分のマスより移動先のマスの数字が大きかった場合のみ
    • マス目から動かない場合も1通りと考えた場合、任意のマス目から移動可能な経路は全部で何通りか?

  解説

経路の合計をどうやって求めるか?

  • 任意のマス目を dp[i,j] とすると、上下左右は以下のように表せる
    • 上: dp[i-1][j]
    • 下: dp[i+1][j]
    • 左: dp[i][j-1]
    • 右: dp[i][j+1]
  • dp[i][j] は、少なくとも1以上であることは確定(そこにとどまることができるから)

後は、上下左右のマスがすでに確定していたらそのマス目の経路の総数をdp[i][j]に足しこめば良い。

AC可能な方式

  • いろいろ試してみたところ
    • C++やD言語ではメモ化+DFSで間に合う
    • Rubyではちょっと特殊だが、所与の長方形の周りに空のマス目を作成しそのまま数えるというものがあった

解答への試行錯誤#1

  • 提出 #1986180
    • その通りにメモ化と再帰で組んでみたがTLEとなる。まだ計算量が多い要素がある。

+ 解答への試行錯誤#1

解答への試行錯誤#2

  • 提出 #1987858
    • 上記のブログを参考にdfsを使ってみる。正解数は増えたがやっぱり2秒に間に合わない。

+ 解答への試行錯誤#2

解答への試行錯誤#3

+ 解答への試行錯誤#3

お名前: コメント: