CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第92回「最短距離で往復できる形は？」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160420045549j:plain

問題文を要約すると下記の通り

  • 格子状の道路があり、左下のA点から右上のB点まで最短距離で移動し、A-B点の移動を繰り返す。
  • このとき、一度通ったルートは通らず全てのパターンを通ったとき、最終的にA点で終わる場合を考える。
  • A-B間の移動距離nが標準入力から与えられたとき、最終的にA点で終わる形のうち、横幅が最小になるものを解答する。
  • A点で終わるものがない場合は0を出力する。
  • {n \leq 99999}

f:id:ibeckuu:20160518001127p:plain

方針

幅{w}、高さ{h}の格子状の対角線上の位置{A,B}を最短距離で移動する時の場合の数は
組み合わせ {_{w+h} C _w} ( = {_{w+h} C _h} ) 通りである。

{A,B}を往復し全てのルートを通って出発地点に戻るためにはこの組み合わせが偶数であれば良い。
これより、問題の距離を幅{1}から始めて場合の数が最初に偶数になる幅を解答とする。

{_n C _r}の値が最初に偶数になる{r}を探すが、普通に計算すると大きい入力で計算値が大きくなりすぎ、時間がかかるため、分母・分子をその都度最大公約数で割り(約分)、分子が最初に偶数になった時の回数を解答とする。

実装(Ruby)

では、

Sponsored Link