オフラインリアルタイムどう書くE08に参加してきた

tech

問題を解きたい方向け注意：ネタバレを含みます。

yhpg.doorkeeper.jp

RubyKaigiで昼飯を同席した方に教えていただいた「オフラインリアルタイムどう書く」に参加してきました。1時間で課題の問題を解いてそれの解説をする、というイベントです。プログラミングコンテストのTLE/MLE*1を気にしなくていい版、といった感じ。

今回の問題はこちら：mtsmfm blog - オフラインリアルタイムどう書く E08 の問題 - 白黒陣取りゲーム

私の解答

gist.github.com

言語は問題を見るまではElixirで解こうと思っていたのですが2分くらい問題を見てこれはダメだと判断しRubyで解いた。最終的なコードの見た目は他のRubyで解いた人とはかなり違っていた（具体的にいうとeachで回して外に用意したメモリに書き込むスタイルvs配列にmapとかを繰り返すスタイル）。

解説

入力のパース

30行目がそれにあたります。入力をカンマで2つの文字列に分け、それぞれを文字列→配列にmapします。その際に正規表現で各点ごとの文字列に分け、それをまた内部でx座標・y座標を持つHashに変換しています。

長方形の形成チェック

22行目と、その中に出てくるis_rect?が該当コード。

is_rect?は2点と同じ色の点の配列を引数とする関数で、

  • pt1のx座標とpt2のy座標を持つ点が同じ色の点の配列内に存在する
  • pt1のy座標とpt2のx座標を持つ点が同じ色の点の配列内に存在する
  • pt1はpt2よりも左上に存在する（pt1のx・y座標はそれぞれpt2のそれよりも小さい）

…という条件で、「pt1・pt2を対角線とする長方形」が生成できるかどうかのチェックを行います。「長方形」は「左上-右下の対角線」と1対1に対応するので、これにより長方形の数え落とし・重複は生じません（最後の条件を落とすとその限りではない）。

これを、自分の色の点列から2つの点の組み合わせ（combination(2)で得る）に対して実行することで自分の色の点列上に存在する長方形の一覧を得ることができます。

その中に相手の色を含むかどうかのチェック

23行目とis_valid_rect?が該当コード。

is_valid_rect?は2点と相手の色の点の配列を引数とする関数で、相手の色の配列に

  • (左上のx座標) =< (点のx座標) =< (右下のx座標)
  • (左上のy座標) =< (点のy座標) =< (右下のy座標)
  • つまり、「辺上もしくは内部に含まれる」ような点

が存在しないことを確認します。

これを22行目で得られた長方形の一覧に対してfilter（Rubyだとfilterじゃなくてselectなんだ…）することで面積の計算対象になる長方形のみを残します。

面積のカウント

さて、最初は面積計算でやろうとしたのですが（24〜25行目、9〜11行目）、これは実行したところ問題がありました。重複する領域を二重に計算してしまうのです。

そこで、「面積1の正方形」を「左上の格子点」に対応づけて数えることで、重複する格子点を数えないようにすれば重複せずにカウントすることができます。格子点の列挙が13〜19行目、その列を取得した後にuniqしてcountしているのが26行目。

…以上を、白と黒それぞれに対して行うと今回の問題の解答が得られます。

実際どれくらいかかったか

  • 重複ありの面積計算まで：35分
  • 重複の除去に気づいて面積を対応づけて正解を得るまで：50分

Erlang/Elixirで解く場合、Listに対するcombinationを自前で実装する必要があります。none?はall?(Erlangのall)の反転、include?はmember?(Erlangのmember)があり、mapとflat_mapとfilterは関数型プログラミングでできなかったら困るので残りは解けるのでは？といったところです。

…というわけで移植した。combinationだけなんとかすれば解けることは確認した。 やっぱりElixirはよいですね…こっちのほうが実行速度速いし（微妙な差だが…）、何よりタプルがあるおかげでx座標・y座標を取り出すところがシンプルに書けているのがでかい。

gist.github.com

*1:Time Limit Exceeded/Memory Limit Exceededのこと