「 今週のお題:セルの結合で一筆書き」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 表計算ソフトめいた縦横$n\times m $のセルがあるとき、以下の条件を満たす「セルの結合方法」が何通りあるか出力する。
    • 各セルの外周を全て辿る一筆書きができること ( 結合したセル同士の境界は外周に含まれない )。
    • 一筆書きの条件を満たすならば、全く結合しなくても良い。
    • セルの結合については、長方形状に配置されたセル同士で行うこと ( L字等ではできない )。
  • $m,n$はカンマ区切り1行で入力される。

解説

提出したコードは、次のPerl(20)でした。

print+($_=<>)-/,/+$'

やっているのは、$m+n-1$の計算です。そのまんま素直に実装したものです。まる。

…だけだと解説にならないので一応。 オイラーの定理 ( Wikipedia )にもある通り、一筆書きができるのは、

  • 頂点の次数 ( その頂点に連結されている辺の数 ) が全て偶数
  • 次数が奇数となる頂点がちょうど2つのみ

のいずれかに限られます。
そうすると、全セル結合 ( 次図左端 ) か、結合の結果2セルのみになるパターン ( 次図中央・右端 ) しかありません ( これより結合を少なくすると、奇数次数の頂点が増えてしまいます )。なお、図中青丸が偶数次数の頂点、赤丸が奇数次数の頂点を表します。

f:id:ange1:20160316004736p:plain

ということで、結局 1通り、$m- 1$通り、$n- 1$通り全て合計して$m+n-1$通りとなるわけです。

終わりに

今回は知っていればとても簡単、というパターンでした。…でも知らなければ…どうするんでしょうね。( そのためか、一応何らか解答すればヒントが出るようになっていたようです )