オフラインリアルタイムどう書くE08オンラインで参加しました

yhpg

はじめに

2016/10/1開催の「オフラインリアルタイムどう書くE08」、残念ながら所用で行けなかったのですが、オンラインで参加し問題を解きましたので、その解説です。

問題

今回は松島さん作成の白黒陣取りゲームでした。

囲碁盤めいたマス目の格子点に、碁石めいた白黒の駒を置いたときに、白・黒の陣地の大きさを求める問題です。
陣地の大きさは囲碁とは違う考えで、「自分の駒4個で作られる、マス目に沿った長方形の内、その内側 ( 境界上も含む ) に相手の駒を含まない領域」の合計の面積とします。

詳細は上のリンクから問題ページをご覧ください。

解説

コードは次の通りです。

解くにあたって、このようなポイントがあるだろうな、と考えました。

  • 長方形のリストアップ
  • 相手の駒が長方形に含まれるかどうかの判定
  • 面積の計算

まず、長方形のリストアップに関しては、駒のx座標・y座標のリストだけ先に作っておいて、長方形としてありうる、x座標2個の組み合わせ×y座標2個の組み合わせを列挙、その中から4隅に駒があって、正しく長方形になっているもののみを選択、というようにしています。

続いて相手の駒が含まれるかどうかの判定です。これについては、E02 ぴったり含む長方形でのしえるさんの解法を参考にしました。
コード上では「標高」と表現していますが、「ある駒より左上にある駒の個数」を各座標 ( 端の隣のダミー座標含む ) に予め登録しておいて、対象の長方形の4隅に対して、その登録した個数を足し引きし、長方形内の駒の数を計算するというものです。
このように計算した駒の数が0個でなければ、「含まれる」と判断できます。

最後、面積の計算です。ただ、各長方形の重複具合を判定するのは大変だと思ったので、実際に盤面の中で陣地になったところを塗っていき、最後に塗られたマスを数えるようにしました。

ちょっと無駄があるような気もしますが、実装は非常に素直なんではないでしょうか。…ただ、しえるさんの手法を思い出すときにちょっと勘違いがあって、修正するのに結構時間を喰ったため、解けたのはロスタイム数分の時点になってしまいました。

終わりに

パッと見どうすれば良いのか分からないのですが、順序立てて整理していくと素直に解けるあたり、良い問題だったのではないでしょうか。次回は会場で参加したいと思います。