「今週のお題：たくさん配るサンタクロース」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
碁盤の目状に道が配備された領域に対して、同じ道を重複して通ることなく、左上隅から出て戻る最長経路 ( 格子の幅を 1 とする ) を求め、出力する問題です。
領域の幅・高さはカンマ区切り1行で入力されます。
例えば、次の図のように、3×3の領域の場合は答え20となります。
解説
提出版について
最初に断っておきますが、提出したコードには不備がありました。
概要
「同じ道を重複して通ることなく」という条件を考えると、交差点から4方向に行ける中央部分、2方向に行ける隅 ( スタート兼ゴールの左上隅含む ) はともかく、3方向の辺の場合は、必ず通れない道が出てきます。無理に通ろうとすると行き止まりになってしまうからです。
ということで、全部の道から通れない所を除く、それも辺以外はなるべく全部通るということを考えます。
そこで、辺の3方向の内どこを捨てるか? というところですが、中央向けの道を通行不可にしてしまうと、中央に更に通行不可な道ができてしまいますので損です。なので、辺を伝う道路を捨てることで、各辺の約半分と影響を抑えます。
そうしたら他の道は全部通れるの? というところ、本当は検証しなければならないのですが、面倒なので割愛して、まあできることにしてしまいます。ただ、通行不可が交互に現れることから、領域のサイズ ( 幅か高さ ) に偶数が現れる時、現れない時でちょっと状況が変わります。
この図にある通り、偶数が出てくる場合、隅の一部が通れなくなります。なので、奇数の辺があったとしても対向する一方は過半数が通行可、逆にもう一方は過半数が通行不可となってしまいます。ところが、サイズが奇数であれば、どの辺についても過半数が通行可となります。
結局、領域の幅$w$、高さ$h$に対して、つぎのようにまとめられます。
- 全ての道路は $2wh+w+h$本
- 幅か高さのどちらかが偶数の場合、辺の半分の $w+h$本が通行不可になる
→ 答え$2wh$ - 幅と高さが共に奇数の場合、辺の半分よりやや少ない$w+h-2$本が通行不可
→ 答え$2wh+2$
実装
式自体が非常に単純なので、コードもかなり短くなります。以下、提出版のPerl(24)です。
$/=',';print<>*<>*2+2&~2
不備について
と、提出版のコードでもちゃんと全ケースパスしたのですが、実は不備がありました。
この図のように幅か高さが 1 の場合、「辺を通行不可にする」という手法が採れないのですね。うっかりです。
この場合、同じく$w,h$を用いて、
- 幅か高さのどちらかが 1 に等しい
→ 答え $2wh+2$
と、幅・高さが共に奇数の場合と同じ式になります。逆に言えば、例えば1×4の領域の場合など、1×偶数 ( もしくは逆 ) のケースに提出版は対応していなかったということになります。
ということで、提出はしていませんが、修正するとなると次のようになるでしょう。
<>=~/,/;print$`*$'*2+2&~(~-$`*~-$'?2:0)
終わりに
油断大敵ですね。
