「 今週のお題：100問目！100人限定！百マス計算！」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 百マス計算 ( Wikipediaの記事参照のこと ) の盤面に対して、左上隅のマスから右下隅のマスまで辿る時、経路上のマスの合計の最小値を出力する。
  • 盤面の情報は、上端に並ぶ数の一覧、左端に並ぶ数の一覧が、1行ずつカンマ区切りで入力される。

問題に記されていた例としては、次の画像のような状況で最小値117というのがありました。

https://codeiq.jp/sites/default/files/answer_ready/2865/q40_2.png

解説

パッと見、Dijkstra案件ぽいかな、と思ったのですが、全マスを走査していっても解けそうで、組むのが楽に思えたのでそれで実装しました。提出したコメント・コード ( Ruby ) は次の通りです。

上端の数・左端の数の合計たる各マスを、合計する前の2数に分解して考えると、経路に沿って、必ず上端・左端の各数字が1度以上現れるため、全数字の合計をベースとして考える。

そうすると、ベースから上回る分は、
・右移動の場合は、同じ行の左端の数
・下移動の場合は、同じ列の上端の数

なので、各マスへの合計最小経路は、
・上のマスでの合計から下移動分加算
・左のマスでの合計から右移動分加算

の両者を比べて小さい方を採用することで得られる。 ( ただし、一番上の行では右移動、一番左の列では下移動に限られる )

# 上端・左端の数字の配列
xa,ya=$<.map{|s|s.split(?,).map(&:to_i)}
# 一番上の行の各マスへの経路での合計最小値、右移動のみ
w=(0..xa.size-1).map{|i|ya[0]*i}
# 行毎のループ
# 一つ前の行の情報を使って、各マスの合計最小値を更新
1.upto(ya.size-1){|i|
  # 一番左のマスは下移動のみ
  w[0]+=xa[0]
  # 一つ前の ( 左の ) マスのと、一つ前の ( 上の ) マスから、
  # 今のマスへの合計最小を調べる
  1.upto(xa.size-1){|j|
    w[j]=[w[j]+xa[j],w[j-1]+ya[i]].min
  }
}
puts w[-1]+xa.reduce(&:+)+ya.reduce(&:+)

終わりに

今回は100回目ということで、久しぶりに手動フィードバックでした。想定解答と同じだったようで、ある意味ほっとしました。( CodeIQの感謝祭でお話を伺ったところでは ) 毎週問題を作って…というのは、やはり大変なようですが、頑張ってもらえると嬉しいところですね。