SRM 587 DIV 2にて、ようやくHARD問題が・・

本日は午前10:10からTopCoderのSRM587 DIV2。

今回初めて時間内にHARD問題が解けたので、記念メモ。

 

【Hard 1000 問題文】

H行×W列の格子があります(格子点の数は(H+1)×(W+1)個)。

各格子には”N”か”Z”の文字が与えられ、

”N”であれば格子の左上と右下の点を結び、

”Z”であれば格子の右上と左下の点を結びます。

赤、緑、青の3色を使い、格子点に色を付けていくとき、

隣接する格子点同士で色が異なるように着色可能かどうかを調べ、

可能であれば”Yes”、なければ”No”を返して下さい。

 

【考察】

日本語で要約すると上記のような感じです。

(正確な問題文や、図による例は、実際の問題文をご参照下さい。)

なんとなく図を描いていると、2×2の格子に注目すればいいことがわかりました。

2×2の格子内で、NとZの数が1:3もしくは3:1であるとき、塗り分けることができません。

(そうでないとき、塗り分けることが可能です。)

すなわち、与えられた格子に含まれる全ての2×2の格子について、

NとZの数を数えることで、着色可能か否かを評価することができます。

 

本番では次のようなコードを書いたら無事System Testも通過し、696点貰えました。

嬉しかったです。

 

 

今回bad[][]という文字定数の配列を用意して、着色不可能な全てのパターンを入れて、

と冗長気味なコードを書きましたが、他の方々のコードでNもしくはZの数をカウントすればいいことに気付かされました。

それを踏まえて書き直したコードは次のとおり。大分スッキリしました。

 


コメントを残す

メールアドレスが公開されることはありません。

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">