Hatena::ブログ(Diary)

vivid memo このページをアンテナに追加 RSSフィード

vivid code というサイトのメモ代わりに記事を書いていました。
現在ははてなブログに移行し、「ひだまりソケットは壊れない」 というブログで記事を書いています。 はてな id も id:nobuoka に変更しました。

2011-06-23

ダイクストラ法による最短経路探索と任意距離の移動が可能な場合の変法

何回か前の TopCoder SRM (SRM509) で出題された最短経路探索問題 (Div2 Hard) が解けなかったので、後から考えた解法をメモしておきます。 実際の問題とは異なりますが、大体こんな感じ、ということで。 実際に出題された問題は、ダイクストラ法で解ける最短経路問題をちょっと難しくしたようなものだったのですが、ここでは、簡単なものと難しいものの 2 つの問題を考えてみます。

まず単純なダイクストラ法で解ける最短経路問題。

M × 横 N のマス目がある。 縦方向には 0 から M - 1 までの数字が、横方向には 0 から N - 1 までの数字が順に振られており、各マスは (x, y) 形式で位置を指定することができる (x, y は 0 ≦ x < M, 0 ≦ y < N の整数) とする。

このマス目上を、初期位置 s から目標位置 e まで移動することを考える。 各マスには正の整数が書かれており、自分がいるマスに書かれた数字のマス目数だけ離れた上下左右のいずれかのマスにのみ移動できるとする。 1 回の移動を 1 ステップと考えるとき、s から e への移動にかかる最小のステップ数はいくらか求めよ。 もし移動できない場合は移動できないという結果を出すこと。

次に、TopCoder SRM で出題されたものに近い、ちょっと難しい問題。 任意距離のマス目移動が可能となっています。

先の問題と同じ設定でマス目が存在するとする。

そのマス目上を、初期位置 s から目標位置 e まで移動することを考える。 各マスは正の整数が書かれているか空欄であり、数字が書かれている場合はその数字のマス目数だけ離れた上下左右のいずれかのマスにのみ移動できるとする。 数字が書かれていない場合は、1 から 9 までの任意の距離だけ離れたマスに移動できるとする。 1 回の移動を 1 ステップと考えるとき、s から e への移動にかかる最小のステップ数はいくらか求めよ。 もし移動できない場合は移動できないという結果を出すこと。

ただし、任意距離の移動は S 回しか行うことができないとする。


簡単な方 (任意距離のジャンプが可能でない場合)

入力として、マス目の情報 (縦横の大きさや、各マスに書かれた数字の情報) が PointLengthMap として、初期位置が s として、目標位置が e として渡されるとする。

  • 0. 各マスに既に到達しているかどうかの情報格納する PointReachedMap を新たに生成する. 初期状態として, 位置 s のみ到達済みとする
  • 1. 位置とステップ数の組 ("( 位置, ステップ数 )" の形式で表すことにする) を格納するキュー P をつくり, 位置とステップ数の組 ( s, 0 ) を P に加える
  • 2. もし P に 1 つも値が含まれていないならば : 目標には到達不可能ということで終了
  • 3. それ以外の場合 :
  • 3-1. P から 1 つ値 (位置とステップ数の組) を取り出し, 位置を p, ステップ数を step とする
  • 3-2. もし p と e が等しい位置を表すならば :
  • 3-2-1. 目標に到達したということで終了. 目標到達にかかったステップ数は step
  • 3-3. それ以外の場合 :
  • 3-3-1. p から移動可能な位置の集合を nextPointSet とする
  • 3-3-2. nextPointSet の各値 (next とする) について :
  • 3-3-2-1. PointReachedMap の情報から, next に既に到達しているかどうか調べ, 既に到達している場合 : 何もしない
  • 3-3-2-2. それ以外の場合 :
  • 3-3-2-2-1. ( next, step + 1 ) を P に加える
  • 3-3-2-2-2. PointReachedMap を書き換え, next に既に到達しているとする
  • 4. step 2 に戻る

step 3-3-1 において、p から移動可能な位置の集合を求める方法は次のとおりです。

  • 1. 新たな位置の集合 S を作る
  • 2. PointLengthMap から, 位置 p における移動距離を取得し, len とする
  • 3. p から x 方向負の向きに len だけ移動した位置を x1 とし, x1 が領域外でなければ S に x1 を加える
  • 4. p から x 方向正の向きに len だけ移動した位置を x2 とし, x2 が領域外でなければ S に x2 を加える
  • 5. p から y 方向負の向きに len だけ移動した位置を y1 とし, y1 が領域外でなければ S に y1 を加える
  • 6. p から y 方向正の向きに len だけ移動した位置を y2 とし, y2 が領域外でなければ S に y2 を加える
  • 7. S が, p から移動可能な位置の集合である

難しい方 (任意距離のジャンプが可能である場合)

入力として、マス目の情報 (縦横の大きさや、各マスに書かれた数字の情報) が PointLengthMap として、初期位置が s として、目標位置が e として渡されるとする。

  • 0. 各マスに既に到達しているかどうかと、到達済みの場合は任意距離移動回数を何回残して到達したかの情報を格納する PointReachedMap を新たに生成する. 初期状態として, 位置 s のみ到達済みとする
  • 1. 位置とステップ数と残り任意距離移動可能回数の組 ("( 位置, ステップ数, 残り任意距離移動可能回数 )" の形式で表すことにする) を格納するキュー P をつくり, 位置とステップ数と残り任意距離移動可能回数の組 ( s, 0, S ) を P に加える
  • 2. もし P に 1 つも値が含まれていないならば : 目標には到達不可能ということで終了
  • 3. それ以外の場合 :
  • 3-1. P から 1 つ値 (位置とステップ数と残り任意距離移動可能回数の組) を取り出し, 位置を p, ステップ数を step, 残り任意距離移動可能回数を rest とする
  • 3-2. もし p と e が等しい位置を表すならば :
  • 3-2-1. 目標に到達したということで終了. 目標到達にかかったステップ数は step
  • 3-3. それ以外の場合 :
  • 3-3-1. もし現在のマスが, 任意距離移動可能なマスであれば (マスに数字が書いていない場合) :
  • 3-3-1-2. もし rest の値が 0 であれば, step 3 全体を抜ける
  • 3-3-1-1. それ以外の場合 : rest の値を 1 減らす
  • 3-3-2. p から移動可能な位置の集合を nextPointSet とする
  • 3-3-3. nextPointSet の各値 (next とする) について :
  • 3-3-3-1. もし next に既に到達しており, かつ過去に到達した際の任意距離移動可能回数の残りが rest 以上ならば (PointReachedMap の情報から調べる) : 何もしない
  • 3-3-3-2. それ以外の場合 :
  • 3-3-3-2-1. ( next, step + 1, rest ) を P に加える
  • 3-3-3-2-2. PointReachedMap を書き換え, next に既に到達しており, かつ到達時の任意距離移動可能回数の残りが rest であるとする
  • 4. step 2 に戻る

step 3-3-2 において、p から移動可能な位置の集合を求める方法は次のとおりです。

  • 1. 新たな位置の集合 Sp と距離の集合 L を作る
  • 2. もし, 位置 p が任意距離移動可能なマスであれば :
  • 2-1. L に 1 から 9 の全ての数字を含める
  • 3. それ以外の場合 : マスに書かれている数字を L に含める
  • 4. L の内部の各数字 (len とする) について :
  • 4-1. p から x 方向負の向きに len だけ移動した位置を x1 とし, x1 が領域外でなければ Sp に x1 を加える
  • 4-2. p から x 方向正の向きに len だけ移動した位置を x2 とし, x2 が領域外でなければ Sp に x2 を加える
  • 4-3. p から y 方向負の向きに len だけ移動した位置を y1 とし, y1 が領域外でなければ Sp に y1 を加える
  • 4-4. p から y 方向正の向きに len だけ移動した位置を y2 とし, y2 が領域外でなければ Sp に y2 を加える
  • 5. S が, p から移動可能な位置の集合である

2011-06-08

組合せ (コンビネーション) を求めるプログラム

今日の TopCoder SRM において 組合せ (コンビネーション; いわゆる nCm と書くやつ) を求める必要があったものの、ぱっと処理を書くことができなかったので反省を込めてメモを。

組合せを求める

組合せ nCm を求める式は以下のようになります。

nCm = ¥frac{n!}{m!(n-m)!} = ¥frac{ n ¥cdot (n-1) ¥cdots 1}{¥{ m ¥cdot (m-1) ¥cdots 1 ¥}¥{ ( n - m ) ¥cdot ( n - m - 1) ¥cdots 1 ¥}} = ¥frac{ n ¥cdot (n-1) ¥cdots ( n - m + 1)}{ m ¥cdot (m-1) ¥cdots 1 }

簡単に実装できそうな感じですが、分子と分母をどういう順番で掛ければ良いかでちょっと悩んでしまいました。 分子と分母を別々に計算して最後に分子を分母で割る、という方法では分子および分母の値があっという間に大きくなってしまいますし、1 個ずつ分子を分母で割ってから掛け合わせる、という方法では丸め誤差が発生してしまうし。。

で、どうしたらいいんだろう、と悩んだんですが、前 (数の大きい方) から掛けるんじゃなくて、後ろのほうから分子、分母を順番に計算していけば問題ないんですね。 Java で書くとこんな感じでしょうか。

/**
 * 組合せ (nCm) を求めるメソッド.
 * n は任意の非負整数, m は 0 以上 m 以下の整数.
 * 値によってはオーバーフローする可能性がある.
 */
long calcCombination( int n, int m ) {
    if( n < m || m < 0 ) {
        throw new IllegalArgumentException( "引数の値が不正です ( n : " + n + ", m : " + m + ")" );
    }
    long c = 1;
    m = ( n - m < m ? n - m : m );
    for( int ns = n - m + 1, ms = 1; ms <= m; ns ++, ms ++ ) {
        c *= ns;
        c /= ms;
    }
    return c;
}