Go, Gopher!

Google Code Jam 2018 の予選、C問題。ここから一気に難しくなってきました。日頃からコードを書く行為に慣れていないと、C以降を通すのは難しかったかもしれません。私も正解こそしましたが、この問題については明らかに考察不足です。正確を期すためには、主催者の解説ページを参照してください。

問題

あなたは3×3の太さをもつペンを持っています。このペンは、その9つの領域のうち、ランダムに1つのドットを打つことしかできません。場所が選ばれる確率は完全に均等($\frac{ 1 }{ 9 }$ずつ)で、すでにあるドットの有無とは無関係です。このペンを最大で1000回まで使って、面積200以上の塗りつぶされた長方形を1つ描いてください。1つの長方形の領域以外の場所にドットが打たれていてはいけません。

考察

この問題は Code Jam 初のインタラクティブ問題です。しかも確率が絡みます。このような問題の場合、先に実験環境を構築してしまうのが実は早道だったりします。

シミュレータ

インタラクティブ問題が必ずしもシミュレータが作りやすいものであるとは限りませんが、今回の場合は簡単でした。指定された座標をもとにランダムで場所を選んでドットを打ち、そのドットを管理するだけだからです。

この問題の場合、フィールドが1000×1000とかなり広大なので、このフィールドを管理するよりは、打たれたドットを管理するほうがメモリ的にも時間的にもリーズナブルです。

まず、打たれたドットは重複のないようハッシュテーブルで管理します。そして、打たれたドットの上下左右の端を常に更新し続けるようにします。ここで、上下左右の端をそれぞれ T B L R、ハッシュテーブル内のドットの数を C とすると、

(B - T + 1) * (R - L + 1) == C

が成立しているとき、ちょうど一つの長方形が描かれている状態であるということができます。この条件と面積200以上をともに満たしたとき、シミュレーションを打ち切ればよいのです。

結論

シミュレータができてしまえば、勝ったも同然です。いろいろな戦略を試してみて、おおむね安全な回数で描画が終わるものを採用すれば、まず合格します。私の場合は、8×25の長方形を、空白の多い座標から優先的に選んで描くという戦略をまず試してみたところ、おおむね500回以内に終わる結果がいきなり得られたので、それを提出しました。

しかし想定解を見ると、単に3×69の長方形を端から塗っていくだけで成立していたようです。逆にどんな塗り方だといけなかったのか? よくわかりません。

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

コメントを残す

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

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)