見た感じで付け焼刃実装してみた久留米っぽいプログラムのお話

プロコン2011舞鶴大会に参加の皆様お疲れ様でした。

実は私も参加していました。
競技部門で。
まぁその結果については残念なものだったのですが、プロコンの醍醐味である
「1日目〜2日目の間に、強かったチームのアルゴリズムをパッと見で~~パクって~~リスペクトして実装してみる」
というのを今年も実行してみました。せっかくなのでそれについてもろもろBlogに書いておこうかと思います。

はじめに

とりあえずプロコンとは何ぞやって人は、公式ページでも見てください

そのへんはすっ飛ばして、今年競技部門のルールを簡単に説明しておきます。

今年のレギュレーションは簡単にいえばスタンプ押しゲームです。
とある画像Aが与えられていて、これまた与えれている画像Bになるように、画像Aにスタンプをぺしぺし押しましょうというルールです。

例えば、
初期画像でこんな画像が与えられていて

目標画像にこんな画像が与えられたりします。*1

んで、スタンプはこんな感じのがあります。

さて、ただこのゲーム、スタンプ押しの「演算」がちとひねってあります。
普通に考えるとスタンプで押されると
「黒+黒=黒、黒+白=黒、白+黒=黒、白+白=白」（ただの論理和）
となりそうな気がしますが、今回のレギュレーションでは「スタンプ押し」の演算は排他的論理和(XOR)でやることになっています。
ということで
「黒+黒=白、黒+白=黒、白+黒=黒、白+白=白」という演算になるんですね。

簡単な演算例を紹介すると、
こういう画像の

赤線部分に

このスタンプを押すと

こうなるのですね。

ちとややこしいですけど、まぁ仕方がありません。XORといえば単純ですが暗号化にも使われるような逆解析が難しい演算ですから、、、
噂によると、NP完全問題を意識して作ったレギュレーションらしいですし

久留米高専は強かった

例年通り、今回の競技部門にも有志の方が作ってくださった練習場がありました。
http://procon.knct21.info/
そこで久留米高専らしきチームはほぼすべての問題で良い成績を残していました。
案の定本戦でも圧倒的な強さを誇っていたわけです。

久留米の戦いを見て

久留米高専の方々はハノイの方々と違って、意地悪にスクランブルをかけず、処理結果をそのまま見て取れるような形で提出してくれていました。
見た感じFAXみたいでしたよね。（見た人はわかると思います
如何にも特徴的ー

リスペクトしてみた

とりあえずFAXということなので、つまりは
「2次元の画像を列ごとに解析することで1次元に落としている」ということではないかと考えました。
つまりはスタンプも左端しかほぼ注目していないのではないかなぁと…
ってことで、1列ごとに潰していくアルゴリズムを考えましたとさ。
ただ、いくら列単位でも総当りするのはちと心配だったので、予めスタンプに関する辞書を作ることに。

まぁ辞書といっても単純で、与えれているスタンプの左端一列を見て、一番最初に登場する黒の塊の長さをキーに整理しただけです。
例えば
これは
一番最初に出てくる黒の塊は赤で塗りつぶした部分なので、「長さ1」でリスト入ります。
他には
これは
一番最初に出てくる黒の塊は赤で塗りつぶした部分なので、「長さ2」でリスト入ります。
長さ3だとこんなスタンプとかがありますよね

そんな感じで辞書を作ったあとは、フィールドの方に注目します。
XORを利用したスタンプ演算なので、
「初期画像と目標画像のXORな画像を作り、それが真っ白になるようにスタンプを押す処理を行った場合、その処理と同じスタンプ処理を初期画像に適応すると目標画像になる」
という考えが成り立ちます。
さて、なので「初期画像と目標画像のXORな画像」に注目してみます。
これがXORな画像だとします。
なのでこの画像が真っ白になるようにスタンプを押せばいいのですねはい。
左端一列に注目すると…
これが一番最初に登場する黒のブロックですね。
ってことで長さ1のスタンプを押します。すると以下のようになります。

そんな感じで1列目を潰していって…次は2列目に注目すると、
2列目で始めに登場する黒のブロックは長さ2でした。なので長さ2のスタンプをここに押してみます。