読者です 読者をやめる 読者になる 読者になる

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で、残りの頂点の次数は全て偶数 →運筆が起点に戻らない場合(閉路でない路)

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

一筆書きができる図形の例(1)

f:id:ibeckuu:20160316001807p:plain

f:id:ibeckuu:20160316001830j:plain

全ての頂点の次数が偶数
青丸をつけた頂点(交差点と折り返し点)はつがなっている辺(線)の数が全て偶数
スタートした頂点に最後にもどる事ができる。

一筆書きができる図形の例(2)

f:id:ibeckuu:20160316001925j:plain

次数(つながっている辺の数)が奇数である頂点の数(赤丸)が2で、残りの頂点の次数は全て偶数(青丸) 次数が奇数である頂点を奇点と呼ぶ事にすると、一方の奇点からスタートし、もう一方の奇点を最後に訪れるたどり方しか一筆書きはできない。

一筆書きができない図形の例

f:id:ibeckuu:20160316002029j:plain

次数が奇数である頂点の数(赤丸)が2より多い
ある奇点からもう一方の奇点にたどり着くとどうしても通れない辺ができる。

この様に、奇点が0か2の図形しか一筆書きができない事になる。
これより、長方形のセルを結合した図形を考えた時、長方形の内部に縦か横に一本だけ線を加えたものと内部に線の無い長方形だけが一筆書きができるものとなる。

{m \times n}このセルの内部に一本だけ線を加えるパターン数は
{(m-1)+(n-1)}
これに線の無いパターン1を加え {m+n-1}
が求めるパターン数となる。
これを実装したのが上記のコード。

では、

Sponsored Link