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

「今週のお題:たくさん配るサンタクロース」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

碁盤の目状に道が配備された領域に対して、同じ道を重複して通ることなく、左上隅から出て戻る最長経路 ( 格子の幅を 1 とする ) を求め、出力する問題です。
領域の幅・高さはカンマ区切り1行で入力されます。

例えば、次の図のように、3×3の領域の場合は答え20となります。

f:id:ange1:20160107000458p:plain

解説

提出版について

最初に断っておきますが、提出したコードには不備がありました。

概要

「同じ道を重複して通ることなく」という条件を考えると、交差点から4方向に行ける中央部分、2方向に行ける隅 ( スタート兼ゴールの左上隅含む ) はともかく、3方向の辺の場合は、必ず通れない道が出てきます。無理に通ろうとすると行き止まりになってしまうからです。

f:id:ange1:20160107000902p:plain

ということで、全部の道から通れない所を除く、それも辺以外はなるべく全部通るということを考えます。
そこで、辺の3方向の内どこを捨てるか? というところですが、中央向けの道を通行不可にしてしまうと、中央に更に通行不可な道ができてしまいますので損です。なので、辺を伝う道路を捨てることで、各辺の約半分と影響を抑えます。

f:id:ange1:20160107010042p:plain

そうしたら他の道は全部通れるの? というところ、本当は検証しなければならないのですが、面倒なので割愛して、まあできることにしてしまいます。ただ、通行不可が交互に現れることから、領域のサイズ ( 幅か高さ ) に偶数が現れる時、現れない時でちょっと状況が変わります。

f:id:ange1:20160107010328p:plain

この図にある通り、偶数が出てくる場合、隅の一部が通れなくなります。なので、奇数の辺があったとしても対向する一方は過半数が通行可、逆にもう一方は過半数が通行不可となってしまいます。ところが、サイズが奇数であれば、どの辺についても過半数が通行可となります。

結局、領域の幅$w$、高さ$h$に対して、つぎのようにまとめられます。

  • 全ての道路は $2wh+w+h$本
  • 幅か高さのどちらかが偶数の場合、辺の半分の $w+h$本が通行不可になる
    → 答え$2wh$
  • 幅と高さが共に奇数の場合、辺の半分よりやや少ない$w+h-2$本が通行不可
    → 答え$2wh+2$

実装

式自体が非常に単純なので、コードもかなり短くなります。以下、提出版のPerl(24)です。

$/=',';print<>*<>*2+2&~2

不備について

と、提出版のコードでもちゃんと全ケースパスしたのですが、実は不備がありました。

f:id:ange1:20160107012816p:plain

この図のように幅か高さが 1 の場合、「辺を通行不可にする」という手法が採れないのですね。うっかりです。
この場合、同じく$w,h$を用いて、

  • 幅か高さのどちらかが 1 に等しい
    → 答え $2wh+2$

と、幅・高さが共に奇数の場合と同じ式になります。逆に言えば、例えば1×4の領域の場合など、1×偶数 ( もしくは逆 ) のケースに提出版は対応していなかったということになります。

ということで、提出はしていませんが、修正するとなると次のようになるでしょう。

<>=~/,/;print$`*$'*2+2&~(~-$`*~-$'?2:0)

終わりに

油断大敵ですね。