This is やっつけで書かれた Competitive Programming Advent Calendar Div2013 の記事です。
自己紹介
こんにちは。
snukeです。
いんとろだくしょん
１学期にオブジェクト指向プログラミングという科目を履修していて、その最終課題が「なにか１つアプリケーションを作れ」だったので前日に徹夜して８時間くらいでパズルゲームを作りました。
それがこちらのゲームになります。
ルールは
- ブロックたちをクリックすることによって色を付けて、２つのグループに分ける。
- 色がついているグループを回転させたり反転させたりして、色が付いてないグループに重なるようになっていればクリア。
多分例を見た方が分かりやすいです。
で？
これを作るにあたり、当然問題を自動生成しなければならなかったわけです。
自明な問題を生成しても仕方がないので、分け方が複数あるようなケースを検出して省かなければなりませんでした。
これは愚直にやると「それぞれのブロックをどっちのグループに入れるか」を全部試せばいいのですが、それだと指数時間アルゴリズムなのでサイズが大きくなると大変なことになります。
しかし僕はなんとか多項式時間アルゴリズムを見つけることが出来たのでこと無きを得ました。
アルゴリズム力が実際のアプリケーション開発で役に立ったので嬉しかったです。(小並感)
僕は競プロが実用的かみたいな議論とかはよく分かりませんが、アルゴリズムって面白いなぁと改めて思った瞬間でした。
おわり。
それだけ？
まあそれだけなんですが、せっかくなので問題生成に使用したアルゴリズムについて書きます。
大まかな流れ
盤面生成 → 答えが複数ないかどうかのチェック → 簡単すぎないかをチェック → ダメだったら最初に戻る
盤面生成
答えがあれば良いので、二つのグループの位置関係と向き関係を固定して指定された個数だけランダムにブロックを置いた。
こういうランダムな生成をしても割とすぐ良さげな問題が出来るので問題なし。
答えが複数ないかどうかのチェック
すーぱーあるごりずむ(そんなに大したもんじゃないですが)を用いた。
ちなみに現在僕が出題しているコンテストにこれを問題として出題しています。
Advent Calendar Contest 2013：新作のパズル
(他の問題のほうが面白いと思います。)
(submitが減ってきていて寂しいので解いてやって下さい＞＜)
12/25に解説を書くので解答編はしばしお待ちをー
簡単すぎないかをチェック
■□□□□
■■□□□
□□□□■
□□□■■
みたいな感じで離れ過ぎていると簡単すぎて全く面白くないので、
「片方のグループのブロックたちの重心が他方のグループの矩形中にないとダメ」
みたいなことをしました。
それだけだとまだ微妙なケースが存在したので謎のアルゴリズム(頑張って思い出そう)で除きました。
あと、hardモードでは二つのグループが平行移動のみで重なるケースを除いてあります。
今回はここまで
読んでいただきありがとうございました。
のんのんびより
ひそかにブログにバナーを張って応援していたので、アニメ化されて嬉しいです。
しかも製作スタッフがGJな感じで、にゃんぱすーで、わーいってなってるのん。
(漫画もってるので読みたい人は言ってもらえればどっかの合宿なりに持っていきます。)
