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

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

はじめに

2016/3/5開催の「オフラインリアルタイムどう書くE02」に参加しましたので、そのレポートです。
プログラムの解説もあります。

どんな感じ?

前回、時間内に解けたのがしえるさんだけという高難易度だったので、易しい問題 ( 勝率8割想定 ) に調整したということだったのですが、今回も結構死屍累々。それでも時間をやや延長して勝率5割ということなので、ちょうど良いところだったのではないかなあ、という感想です。何とか私もロスタイム中に解けました!!

今回は自己紹介、「最近あった成功したこと」ということで…。…前回「失敗したこと」でお酒の失敗談があったと思ったら「お酒飲んでも寝坊しなかった!!」とかが成功談になる某社って…。…という突っ込みはしないで行こうと思います。

問題

問題は鍋谷さんのサイトにあります。

内容は次の通りでした

  • 62×62の格子から切り出せる長方形の中で、最大・最小のサイズ ( 面積 ) を計算する。
  • ただし、格子の中には黒いマスが幾つかあり、切り出した長方形が丁度指定の数だけ黒いマスを含むこと。
  • 入力パラメタは、「含むべき黒いマスの個数」「コロン」「黒いマスの座標のリスト(カンマ区切り)」をつなげた文字列
    ※なお、座標は英数 ( 0~9,A~Z,a~z ) 2文字からなる文字列

解説

方針

会場の傾向としては、62×62の格子を、${}_{62}C_2\times{}_{62}C_2$通りに切り出して、その中に含まれる黒いマスの個数が条件を満たすかどうか調べていく、というのが多かった感じです。まあ高々数百万通りですから、それでも現実的な時間で解くことはできます。
※実際にそれを awk(!) で組んで完成させた方もいらっしゃいました。…実行に30分ほどかかったという。「なぜそこでawkなんだ」というツッコミが入ったのは言うまでもありませんが。

しかしここでケースを見てみると、黒いマスの個数はせいぜい数十個。なので、黒いマスに対するループにした方がかなり処理量が減りそうです。なので、次のように考えました。

  • まず串を刺せ!!

f:id:ange1:20160306011951p:plain

まあ、串を刺すって言うのはグルーピングのことですね。こうすると何が嬉しいかというと、切り出す長方形、最大サイズ・最小サイズを目指すそれぞれの場合の「横幅」を決めることができる、ということです。
すなわち、選んだ串の間ギリギリが最小の幅、隣の選ばれなかった串 ( ない場合は格子の端 ) まで目いっぱい広げたところが最大の幅になるということです。

これは、左端の串・右端の串の2本を選ぶだけなので、Ο(串の本数2)のケースで済みます。

  • 違う方向にも串を刺せ!!

横幅が決まれば、横方向へも串を刺して考えることで高さが決まり、長方形のサイズを計算することができます。もちろんこの時、長方形に含まれる黒いマスが、ぴったり指定の個数になるような選び方のみを残して考えます。

f:id:ange1:20160306014740p:plain

ただ、ちょっと気になることがあります。実際に横の串を選んだ時、縦の串で使わないものが出てくるのでは…?? と。この図 ( 黒いマス3個のために串を2本選んだ状態 ) の場合、最初に選んだ4本の縦の串のうち、一番右の串が外れてしまったことになります。

しかし、これは実のところ気にしなくて構いません。一つには、最大を求める場合に重要なのは「選ばない串にどこまで迫れるか」なので、選んだ串を使わなくなっても困らない、ということ。もう一つ、最小を求める場合、どうせ全ての ( 連続する ) 串の選び方を試すので、このケースは計算上無駄ではありますが、答えには影響しないということ。どっちにしても困らないのです。

実装

会場で組んだ版も一応あるのですが…。取りあえず動くようにと組んだのでゴチャゴチャしています。まあ、色々クセが見えて面白い面もあるかも知れませんが ( 保証はしません )。

ということで、書き直したのが次のコード ( Ruby ) です。入力から答えを生成する solve 関数が本体です。

串を刺して考える以上、個々の黒いマスの座標はもはや必要なく、串 ( x座標 ) 毎の y座標のリストがあれば十分です。パラメータをparseして作る hsk というリストのハッシュが相当します。

そして、串の左端・右端の2重ループの中で、横に串を刺して「黒いマスがちょうど n の場合」を調べ、面積の最大・最小を更新していきます。今度横に串を刺す時は、y座標毎の黒いマスの数だけ管理すれば十分で、これがハッシュ vsk になります。
会場では時間の余裕がなくて組みませんでしたが、鍋谷さんの説明された「尺取り法」( 名前は知りませんでしたが ) を実装することは考えていました。

ちなみに、会場では自分のPCで0.4秒 ( user時間 )、書き直したバージョンが ideone上で 0.1秒程度と、まあ良い実行時間ではないでしょうか。

終わりに

皆さまお疲れ様でした。東京で開催するようになって気軽にいけて助かります。…ただ、参加希望者が多いので入れるかどうかは運ですね。まあ、漏れても今回のしえるさんみたいにオンラインで参加しようと思います。
…いや、最速で解いたのが会場にいないしえるさんってのもどうなんだ、って話はあるんですが…。( しかし私は組むのが遅い )