CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第100回「100問目！100人限定！百マス計算！」

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

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

• 標準入力より0から9までの整数がコンマ区切りで10個で1行分、これが2行分与えられる（合計20個）
• 1行目の数を横軸に、2行目の数を縦軸に方形に並べ、数値の交差する位置にそれぞれを加算した数値を置く（100マス計算）
• 計算した数値に対して、左上から右下のマスまで縦横に移動する時、通ったマスの数値を加算した場合に、合計が最も小さい移動経路を求め、その合計数を出力する。

「今週のアルゴリズム・100問目」について

今回、今週のアルゴリズムが記念すべき100回目であった。
その記念に、挑戦を受け付ける人数を先着100人限定とし、優秀正解者の中から10人に出題者の著作をプレゼントするという企画であった。
最近の挑戦者数の増加と、問題の難易度から挑戦できる100人は出題日当日に埋まると予想した為、珍しく当日の夕方に解答を提出した。仕事中にちょっとサボって会社のノートPCでコーディングしてそのまま提出したが、結果的にはそれ程慌てる必要は無かった。
久しぶりの手動採点問題で、正解をもらえたが、フィードバックをもらうまでなかなかの緊張感を味わえた。

方針

問題文を読んだ瞬間はダイクストラ法一択だと思った。
（もちろん他にも良い解法はある。自分が思いつかないだけである）
しかし、コーディングをし始めて何故か、書きなれた再帰で実装していた。
ダイクストラ法は基本的にキューを使った幅優先探索を用いて実装するのが一般的で、出発点から最も近い接点を順に確定しながら、連結している全ての接点への最短距離を求めるアルゴリズムである。
それに対して、今回再帰により実装した方法は、100マスと同じ構造の二次元配列をメモとして用意し、それぞれのマスに移動する時、メモと比較し、メモよりも合計が小さくできればメモを更新し、移動する。小さくできなければその先へ進まないという方法の「メモ化再帰」というより「枝刈り探索」といった方が良いものかもしれない。
今回の問題のサイズではこの方法でも十分に短時間で答えがでるので、他の方法を考えることなく提出した。

実装(Ruby)

今回、手動採点で、コメントを含めた可読性も評価対象との事であった。
コメントについて、最近は手抜きが多かったが、割とマジメに書いたので、提出時のままで記載する。

では、


Sponsored Link