CodeIQ 挑戦の記録 : 第84回「今週のアルゴリズム：セルの結合で一筆書き」

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

f:id:ibeckuu:20160316001650j:plain

問題文を要約すると、

表計算ソフトのセルの結合を考える。
標準入力から横が ${m}$ 、縦が ${n}$ のセルの個数が与えられる。
セルの外周を図形として見たとき一筆書きをできる結合のパターンが何通りあるかを答える。
${m \leq 10 \ ,\ n \leq 10}$

提出したコード

Ruby(39byte)

m,n=gets.split(",").map(&:to_i);p m+n-1

Perlでも提出してみた。Perl(28byte)

<>=~/(.+),(.+)/;print$1+$2-1

コードの説明

一筆書きできるパターンを数えるが、その前に一筆書きができるかどうかについての判定法について述べる。
連結グラフにおいて、一筆書きが可能かどうかの条件をWikipediaから引用。

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。

すべての頂点の次数（頂点につながっている辺の数）が偶数 →運筆が起点に戻る場合（閉路）

次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数　→運筆が起点に戻らない場合（閉路でない路）

何を言っているのか良くわからないかもしれないので解説する。　　