第22回高専プロコン競技部門参加記

12月22日から2日間にわたって開催された全国高等専門学校プログラミングコンテストの競技部門に参加してきました．

結果は準決勝敗退という悪い成績でした（人権ない）．
今回の府立高専の方針と敗因について書いていきたいと思います．

・方針
1.問題の読み込みと差分画像（初期画像と最終画像のxor）を生成する．
2.スタンプのすべての押し方を試し，そのテーブルを生成する．
3.１ｘ１のスタンプを用いて自明な解を生成する
4.解からある矩形範囲に影響のあるスタンプの適用を取りだす．
5.4で取り出したスタンプをランダムで数個取り出し，全て0の画像に適用する．
6.5で生成した画像を新たな問題だと思って貪欲法で解き，短い手数になっていればこれを置き換える．
7.4〜6を時間が許す限り繰り返す．

これだと局所解に落ちるのは目に見えてるので，4〜6は別スレッドで別々に行い，1周するごとに解を併合している．
取り出すスタンプの範囲はスレッドで別々にし．画像の左上から順に少しずつずらしている．

＜解の併合について＞
2つの解をそれぞれ解１、解２とし，併合した解を解３とする．
1.解１，解２に共通するスタンプの適用を解３に追加する．
2.解１から解３に含まれている物を取り除く．解２についても同様にする．
3.解１から適当に１つのスタンプの適用を取り出す．
4.取り出したスタンプの適用に影響のあるスタンプの適用を解１と解２から取り出す．
5.4を繰り返し，取り出すスタンプがなくなったら取り出した個数の少ない方を確定し解３に追加する．
6.解１，解２が空になるまで3〜5を繰り返す．
幅優先チックな解のマージ方法です．割と良い感じに解をマージできます．

・敗因
上で示した方針は，最初に最低限の解を出力し，時間が立つに連れて良い解に収束していくけれど，競技時間が予想よりかなり短かい上に問題サイズが大きくて，解が収束する前に競技が終わってしまいました．
貪欲法で上から順に確定するだけの方が時間内に良い解が出せたようです．

競技終了後，優勝の久留米高専のチームにお話をする事ができました．
アルゴリズムや高速化の話が聞けたり，ソースを少し見せてもらった，レベルの違いに驚かされるあまりでした.
自分は今年で最後ですが，久留米高専の彼らは来年も出場するそうです．
来年もアルゴリズムの問題だったら久留米高専が強豪になることは間違い無いでしょう．
府立高専の後輩たちは，直前まで何もしない癖を何とかしましょう..orz