「 今週のお題:セルの結合で一筆書き」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 表計算ソフトめいた縦横$n\times m $のセルがあるとき、以下の条件を満たす「セルの結合方法」が何通りあるか出力する。
- 各セルの外周を全て辿る一筆書きができること ( 結合したセル同士の境界は外周に含まれない )。
- 一筆書きの条件を満たすならば、全く結合しなくても良い。
- セルの結合については、長方形状に配置されたセル同士で行うこと ( L字等ではできない )。
- $m,n$はカンマ区切り1行で入力される。
解説
提出したコードは、次のPerl(20)でした。
print+($_=<>)-/,/+$'
やっているのは、$m+n-1$の計算です。そのまんま素直に実装したものです。まる。
…だけだと解説にならないので一応。 オイラーの定理 ( Wikipedia )にもある通り、一筆書きができるのは、
- 頂点の次数 ( その頂点に連結されている辺の数 ) が全て偶数
- 次数が奇数となる頂点がちょうど2つのみ
のいずれかに限られます。
そうすると、全セル結合 ( 次図左端 ) か、結合の結果2セルのみになるパターン ( 次図中央・右端 ) しかありません ( これより結合を少なくすると、奇数次数の頂点が増えてしまいます )。なお、図中青丸が偶数次数の頂点、赤丸が奇数次数の頂点を表します。
ということで、結局 1通り、$m- 1$通り、$n- 1$通り全て合計して$m+n-1$通りとなるわけです。
終わりに
今回は知っていればとても簡単、というパターンでした。…でも知らなければ…どうするんでしょうね。( そのためか、一応何らか解答すればヒントが出るようになっていたようです )