Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2013-10-05

SRM 593

| 02:59 | SRM 593 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 593 - TopCoder煮ブログ

2 年ぶりの参戦。

14481402 (0pt 393位/830人)

--- (challenge: 0勝0敗)

HexagonalBoard (Easy)

Hex な盤面での色塗り問題。

最初は周りのコマ数で判定すればいいやーと思って書いてたら、サンプルが通らなくて無駄に悩んだ。

サンプルは

"XX-XX--
 "-XX-XXX"
  "X-XX--X"
   "X--X-X-"
    "XX-X-XX"
     "-X-XX-X"
      "-XX-XX-"}

となっていて、どの1コマを見ても、その周囲は 2 色で塗れそうに見える。

ただ、2 色で塗っていくと・・・

"XX-XX--
 "-XX-○●○"
  "X-X●--●"
   "X--○-○-"
    "XX-●-●X"
     "-X-○X-X"
      "-XX-XX-"}

と不整合がでるので、3 色目を導入する必要がある。

と気づいた時点で、DFS でやるべきなんだけど、力尽きた。どんな形でも最大 3 色あれば塗れるので、あとは

  • 何もなければ 0 色
  • すべてが孤立してれば 1 色
  • DFS で 2 色で塗れるか確認して、OK なら 2 色、ムリなら 3 色

とすればいけるはずなんだけど、時間切れ。


Challenge ではおかしそうなやつを見つけたけど、落とすサンプルを思いつかず時間切れ。実際、System Test に落ちていたので悔しいところ。

MayTheBestPetWin (Medium)

brute force で書いたらサンプル通らなかった。

まとめ

悲しい・・・。