全国高等専門学校プログラミングコンテスト舞鶴大会

競技プログラミング 高専プロコン

(この記事はCompetitive Programming Advent Calendarの24日目の記事です。)

日本全国の競技プログラマのみなさん、こんばんは！
今日はTopCoder SRM→Xmas Contest→Codeforcesとコンテストが目白押しでしたが、調子のほどは如何でしたか？
頭をフルに使った後はこの記事でも読んで休憩をしていただくと良いかと思います（ ＾ω＾）

さて、突然ですが、先日行われた高専プロコン舞鶴大会の競技部門において、私@、@、@の3人による久留米高専チームが優勝を飾ることができました！
この記事では、高専プロコンの説明、今回の競技についての久留米の解法、競技全体を通しての所感について、簡単ではありますがまとめさせて頂こうと思います。諸事情あり時間があまり取れず文章の推敲が行えていないので、全体的に読みづらいかと思いますが、ご理解とご容赦の程宜しくお願いします。

高専プロコンとは？

皆さんは高専プロコン(以下、プロコン)という大会をご存知でしょうか。恐らくここを見ている高専生ならば一度は耳にしたことがあるでしょうし、選手として出場した経験のある人も多いと思います。反対に高専生になったことのない方には馴染みの薄い大会かも知れません。
高専プロコンとは全国高等専門学校プログラミングコンテストの略称で、まぁ簡単にいうとロボコンのプログラミングバージョンです。毎年10月中頃に日本のどこかの高専が主管校となって開催されます。出場権を持つのは高専生(本科・専攻科)のみですが、国際大会が併催されるので外国の大学も参加します。開催回数も22回を数え、高専生対象のコンテストとしてロボコン・デザコンに並ぶ知名度を持っていると言われています[要出典]。

プロコンは大きく以下の3つの部門に分かれています。

自由部門

5人以下のチームで自由にソフトウェアを開発し、デモンストレーションやプレゼンテーションを行なって審査します。6月頃に書類による予選審査があり、それを通過した全20チームのみが本選に出場することが出来ます。1高専最大2チームです。

課題部門

基本的には自由部門と同一ですが、与えられたテーマに沿ったソフトウェアを作成する必要があります。テーマは2年毎に変わっており、去年及び今年のテーマは「旅とコンピュータ」です。

競技部門

3人以下のチームで、与えられた問題を解くプログラムやゲームAIを作る部門です。問題は4月の時点で公開されるので、10月の本選までじっくりと開発することができます。1高専1チームです。本稿はCompetitive Programming Advent Calendarの記事ですのでこの部門の話がメインとなります。

例年の競技部門

さて、ここで競技部門の雰囲気を感じ取って頂く為に、幾つか例年の競技部門の内容を紹介します。

2006年(米子大会)

640×480ピクセルのカラー画像1枚と、その画像の一部を加工した画像100枚が与えられます。加工画像は、元画像の一部を切り出し、拡大・縮小・上下左右反転・回転・色調変更を施し、ハート型に切り出したものです。ダミーも含まれています。加工画像が元画像を加工して作られたものなのか、そうであるならばどの位置を切り出したものなのかというのをできるだけ多く時間内に答えたチームが勝利となります。優勝は久留米高専でした。

参考：育代が行くよ！　Ｓｐｅｃｉａｌ　プログラミングコンテストに，黒船が飛び込んできた！（2）：ITpro

2009年(木更津大会)


最大20×20の大きさの盤面が与えられ、各マスには最大8種類の色がついています。この盤面に対して、マスの頂点を中心とした、一辺が偶数の正方形の領域について、90°・180°・270°の回転操作を行うことが出来ます。出来るだけ少ない回転操作で、全ての同じ色のマス同士を隣接させたチームが勝ちとなります。例えば右図の左の状態が初期状態として与えられ、これに回転操作を施し右の状態に変えれば完成です。この大会では大阪府立高専が優勝しました。

参考：高専プロコンリポート：「最強最速」を見せつけた浪速の高専生 - ITmedia エンタープライズ

2010年(高知大会)


一辺が20の大きさの六角形の盤面を舞台にした陣取りゲームです。6チームが同時に対戦し、それぞれ3台のコマを動かします。青いマスが水汲み場で、ここでまず水を汲んでから他のマスに配水することで自分の陣地とすることができます。配水は同じマスに複数回重ねることが出来、時間はかかりますが他のチームに乗っ取られにくくなります。自分の配水マスで閉曲線を作った場合、その内部も全て自分の陣地として数えられます。この大会は3Dのビジュアライザの完成度が非常に高く、観客もリアルタイムに楽しく観戦をすることが出来ました。優勝校は石川高専です。

決勝戦の動画

第22回高専プロコン舞鶴大会

さて、本項以降は今年の高専プロコンについて、書きたいと思います。
例年10月中頃に本選が開催される高専プロコンですが、今年は震災の影響*1で開催が12月の下旬となってしまいました。
自分は21日に舞鶴入りで、24日に帰ったのですが、ほんと舞鶴は遠いですね…。京都からさらに1時間半。久留米より少し暖かく過ごしやすいように感じました(2日目は霰が降りましたが…。)

課題内容

今年の競技部門の問題内容について簡単な説明を行います。

  • 最大640×480の大きさの二値画像が2つ与えられる。それぞれ、初期画像・完成画像とする。
  • 最大128×128の大きさの二値画像が最大128枚与えられる。スタンプと呼ぶ。
  • 初期画像の任意の位置に任意のスタンプを"押す"ことができる。スタンプを押すと、スタンプの黒マスの位置に対応する初期画像のマスの白黒が反転する。すなわち、初期画像とスタンプを任意の位置でXORすることが出来る。
  • 1×1で黒色のスタンプが必ず与えられることが保証されている。
  • 競技時間は1分以上10分以下。

例えば、

この画像の左下の所に、

このトナカイのスタンプを押すと

こうなります。スタンプは画像から一部がはみ出す位置に押すことも出来ます(この場合はみ出した部分は無視されます)。

勝敗の判定は以下のようになります(nで勝敗が決まらなかった場合はn+1で勝敗を決めます)。

  1. 最終画像との不一致数が少ない
  2. 手数が少ない
  3. 提出時間が早い
  4. じゃんけん

一度の競技では2つの問題セットを解くことになります。1問目の制限時間が終了した直後に2問目が始まります。不一致数・手数・提出時間について、それぞれ2問分の合計値で上記の基準による勝利判定が行われ順位が決まります。

次節で自分たちが考え、実際本番に用いた作戦やアルゴリズムについて、本邦初公開しようと思います。

久留米高専の作戦 1. 問題分析

まず簡単な考察により、問題を簡略化します。

  1. 初期画像を最終画像に変えることは、初期画像と最終画像のxorを取った画像を真っ白な画像(以降「盤面」と呼びます)に変える作業に等しい。
  2. 1×1で黒いスタンプが必ず与えられるので、実質勝敗判定の1は考えなくて良い。特徴的なインプットでない限り手数が全く同じになることはほぼ無いので、勝敗判定の3や4もそこまで考えなくて良い。つまり、手数を最小化することのみを目的とすれば良い。

これはパンフレットを見る限り、ほとんどどのチームも行なっている方法でした。

次に、この問題の種類を2つに大別しました。

  • 盤面とスタンプどちらも何かの形のシルエットである等、白黒の領域がはっきりと分かれている場合
  • 盤面やスタンプのどちらか一方がノイズである場合

おそらくこの2つは問題の性質が大きく異なります。しかしインプットの作成方法が全く公開されていないので、どちらか片方に注力し他方を蔑ろにするのはあまりよくないと考えました。
本戦で用いられるインプットについて、本戦1週間程前にtwitter上では

@colun 競技練習場にある全問題が、実は本選の出題と根本的に違うんじゃないかという気がしてならない。練習場の様なノイズ的スタンプではなく、直径10ピクセルの中黒スタンプとか、アルファベットを模した大きめのスタンプとかが出題されたら、練習場の上位は、総崩れなのでは？ #procon2011

という感じの議論があり、それに対して

@natrium11321 @colun 高専プロコンの運営がアップロードしている簡易競技システムの使い方動画があるのですが、これを見るとスタンプはノイズのように見えます。　http://t.co/onU33YEd

というツイートをしてあたかもノイズ以外のインプットを想定してない雰囲気を醸し出したり

@nikollson 大きすぎるスタンプはノイズと性質が変わらないと思っている

ととんちんかんなことを言ってみたりしたのですが、実はシルエット入力は完全に想定して、対策を練っていました。

久留米高専の作戦 2. すごく小さいスタンプ対策

tokura

今回の競技では、釧路高専OBの方が作って下さった高専プロコン2011練習競技場で、競技前から多くの高専生がお互いにスコアを競い合うことが出来ました。
このうち、問題1や4のような非常に小さなスタンプしか存在しないような入力に対しては、焼きなまし法(以下SA)で解を出すようにしています。具体的には、縦5×横5の正方形のマスのビットパターン2^25全てにおいて、それを全て0にするような厳密な最短手数を幅優先探索を用いて求めます。ただしこの時正方形からスタンプがはみ出ないようにします(つまり、5×5に収まるスタンプしか使うことが出来ません)。盤面のあるランダムな5×5領域において、その領域にすでに置かれているスタンプを全て除去し、先ほど求めた厳密解をそこに当てはめ、近傍界とします。解評価は置かれているスタンプの数+黒マスの数で、後は通常のSAと同じです。この方法だと、練習競技場の問4で3000程度の解を出すことが出来ます。この解法にtokuraというコードネームをつけています*2。

sakura

tokuraを進化させた方法で、最後の解評価を置かれているスタンプの数+左上から5×5の正方形を敷き詰めてた時の手数に変えたものです。競技練習場問4で2900程度の解になりました*3。

久留米高専の作戦 3. シルエット対策

ikura


tokura→sakuraと進化した次はikuraになりました。おいしそうですね（ ＾ω＾）
ikuraはsakuraの進化というよりは、sakuraを下請けとして使うアルゴリズムなのですが、盤面・スタンプ共にシルエットが多いインプットにおいて、盤面の黒い領域にうまくスタンプを組み合わせて押していくアルゴリズムです。上下左右に微妙に動かしたり、スタンプを削除したり、別のスタンプに変える近傍界生成を用いるSAを使っています。このSAを十分に回した後、サッと貪欲法を回し*4、その後にsakuraを回します。SAを多重化する等他にも多分なんかいろいろやってると思うのですがikuraは主にnikollsonが開発したので自分はあまり詳しく知らないのです……ごめんなさい。
右の画像はikuraを回してみた(貪欲やsakuraはまだ回していない状態の)盤面です。(水色は無視して下さい)

久留米高専の作戦 4. ノイズ対策

loli

競技練習場の問11や12等の、sakuraを回せそうなスタンプが存在しない、大きなノイズスタンプが多い入力に対して強いアルゴリズムです。縦1×横22〜26くらいの長方形のすべてのパターンの厳密解をtokuraと同じ方法で求め、左上から右下方向に適用していきます。パターンを作るときは、スタンプの左上の部分のみを使い、長方形の右下にのみスタンプがはみ出るようにします。これがなんか普通に強くて、練習競技場問12で9500くらいの解が出ます。*5

mädchen

loliを進化させた解法です。幼女が少女になりました。*6
基本的にloliと同じなのですが、loliのように単純に左上から1×w (wは22から26くらい)で割り当てていくのではなく、各行について組み合わせのDPを行うようにしています。ある行について、dp[i]を、左からi番目のセルまでの手数の最小値を表す配列だとすると、dp[i]はmin dp[i-j]+(左からi-j番目のセルから、i番目のセルまでのjマスを0にする最小手数)で求まります(1≦j≦w)。当然本当の意味の厳密解には遠く及びませんが、割と改善します。競技練習場問12で8000程度になります。
あと細々とした点として

  • 左上からのみ試すのではなく、「左上から1×w」「左上からw×1」「右上から1×w」…など8パターン全て試して最適値を取ります。
  • 中央に大きな空白がある場合、その空白を中心として四隅に向かって埋めていくと効率が良いので、中に黒マスを含まない最大の直交凸包(通称ロリ包)を頑張って求めて良い解が出るか試します。ロリ包を求めるアルゴリズムは盤面の一辺の長さをnとするとO(n^4)のものしか思いつかず、計算に時間がかかってしまうためある条件を満たしたちょっと悪いロリ包をO(n^3)で求めて使うようにしています。
  • ロリ包の四隅に向かって埋めていくアルゴリズムを1×wからw×1に変えたものも解が改善するかどうか試します。
  • 本番での作戦は、まず速攻で終了するw=20の解を前述の10パターン全てについて求めて、その中で最も良かったものについてwを少しずつ大きくしていきながら順次解を作成しました。

久留米高専の作戦 5. 基本操作の高速化

盤面にスタンプを押す操作は全解法の基本です。これを高速化することはひいてはプログラム全体を高速化することに繋がります。(パターン生成に時間がかかるloli系は異なりますが…。)
マスの01をビットで管理すると1バイトに8個のマスの情報を載せることができますが、スタンプを押す操作をビット毎のループで処理するとものすごく遅いです。これを高速化する方法としてまず考えられるのは、64ビット型整数のxor演算を用いて一気にxorすることです。スタンプを押すx座標が8で割り切れない場合はビットシフトとか色々面倒なので、最初に0〜7マスだけ右にずらした画像を作成します。
64ビット整数型のxorは最初に比べて速いといえば速いのですが、まだ速度が足りません。今時のIntel CPUにはSSE拡張命令という素晴らしい命令があり、なんと128ビットのビット列に対して1命令でxorが行えます。SSEのxor命令(pxor)はSSE2で対応しているため、ほとんどのIntel CPUで動きます。1度に横に連続する128セルxor出来るということは、x座標が8で割り切れない場合でも最大で2回の命令で1行のxorを完了することができます。これを実装すると最初のループによるxorよりだいたい70倍くらい速くなりました。素晴らしいね！

次に、スタンプを押したときの黒マスの数の増減を知るという操作を考えます。これもおそらく使う機会が多いと思うのですが、黒マスの数の増減を知るにはビットのpopcountが必要になります。ビットのpopcountはAND演算とかシフト演算を駆使した闇魔術的コードが知られていますが、実はSSE4.2の中に64ビットのpopcount命令が含まれています。つまりたったの1命令で64ビットの中の1の数を知ることができるので、具体的な速度比は計測していませんがものすごく速いです。しかしSSE4.2はCorei7系以降のCPUでしかサポートされていないので、i7系のCPUを搭載したPCを使う必要があります。

その他OpenMP使って並列化したりとかいろいろしました。L3キャッシュは全CPUで共通なのが嫌ですね;X

久留米高専の作戦 6. 人力操作

人力で解きやすいインプットが出るかもしれません。その場合に人力で解くチームに負けてしまうことが考えられます。
これを憂慮した久留米高専チームは人力ソルバーを開発し、最強人力選手TKNGを養成しました。これにより練習競技場の問13や14において驚異的に手数が少ない解を手動で生成することが可能となりました。

競技本戦

今回の競技は、(1日目)予選→(2日目)準決勝→決勝 という順番でした。結果から言うと、久留米チームは全ての競技において1位*7をとり優勝することが出来ました。
実際に競技を行なって自分が最も驚いたことは、与えられるインプットが盤面・スタンプ共に全てノイズ形式だったことです。他の高専は、競技練習場の問4のようなスタンプがとても小さいインプットに対して強かったり、そのようなインプットでないと計算時間が爆発するような解法を使っていたところがほとんどだったようでした。PCを2台まで持ち込むことができるので、片方のPCでikuarを回しもう片方のPCでmädchenを回すという作戦を取っていたのですが、mädchenが火を吹いて優勝に導いてくれました。可哀想なikura…(と盤面を目の前に呆然としていたTKNG)。
決勝戦のustreamの録画はこちらから見ることができます。一問目(「絆」の文字)の久留米の修復手順が若干変なのは、中央に大きなロリ包を作り、そこから四隅に向かって修復を行なっている為です。

最終的にloli系と同じような方針で解いていたのは久留米、ハノイ、宇部の3校だけだったように思います(有明はよくわかりません)。ハノイや宇部に対する久留米の差はやはりloliとmädchenの差に尽きると思います*8。

感想

元々今回の高専プロコン競技部門のモチベーションは前年度の競技部門で準々決勝敗退したところから始まります。前年度の問題は前述の水撒きゲームだったのですが、割と強い(と思っていた)プログラムを本戦に投入して1回戦快勝したのに準々決勝でまさかの敗北を喫してしまいました。今考えるといろいろと反省するべき点はあるのですが、翌年(=今年)優勝したいという強い気持ちを明確に持ったのはこの辺が理由だと考えています。
じゃあ問題が公開されてから必死にやったのかと言われるとそうでもなくて、実際結構やり始めたのは11月に入ってからだったりします。もちろんそれ以前にも問題の分析等は行なっていたのですが・・・。
なにはともあれ、リベンジを果たすことが出来非常に嬉しいく思います。

以下に、私から見た今年の問題の良い点と悪い点について箇条書きにしてみました。

  • 良い点
    • 他のチームに集中的に妨害されない。強いプログラムを組めば高い確率で結果に反映される。
    • 練習用サーバ等が積極的に公開されており、本番に近い環境を構築し動作テストを行うことが出来た。
  • 悪い点
    • 入力の作成方法が公開されていない。勝ちを確実に取りに行くには様々な種類の入力に対応する必要が生じ、開発期間がいたずらに伸びる。
    • 観客から見て去年のような躍動感がない。
    • ルールを簡単に説明しにくい。
    • フルサイズの問題セットが決勝でも出ない。制限時間が1〜10分ならば、決勝では10分の問題を出題するべきだと思う。

おわりに

これを見ている出場経験のない高専生の方は、来年是非挑戦してみましょう。「私ちょっと競技系苦手かも…」「マラソンが苦手でなにも出来ません」と思っている方もいるかも知れませんが、高専プロコン競技部門は開発期間が非常に長いことが特長です。実に半年の期間があれば最初の能力差など完全に覆ってしまうことも考えられます。
また出場経験のある高専生の方は、来年も是非出場して、自分と優勝争いしましょう。
高専生以外の方は、来年は10月に有明高専*9で開催予定なので、是非ustream等で観戦して頂けると嬉しく思います。
それでは、主催の高専プロコン実行委員会の方々、舞鶴高専の方々、一関高専の先生方、練習競技場を提供して下さった釧路高専OBの@さん、その他応援して下さった方々へ感謝の意を示しつつ、本稿の締めくくりとさせて頂きます。
ご精読ありがとうございました。

*1:元々今年の高専プロコンの開催地は一関でしたが、こちらも震災の影響で舞鶴に変更になりました。

*2:ドグラ・マグラが語源…らしい(nikollson命名)。

*3:語源は謎。

*4:時間がやばいときは、スタンプと盤面の黒濃度からそこにスタンプを押したときに減る黒マスの数の期待値と標準偏差を求め、中心極限定理に従いこれが正規分布していると仮定し標準化変換して閾値と比較したりして枝刈りします。

*5:loliって名前だけどマリオのスター状態で力押しで突っ切っていく感じで全然loliっぽくないよねむしろgoriだよね by nikollson

*6:ちなみに、さらに改良アルゴリズムが出来る場合にはloli→mädchen→woman→babaaと進化する予定でした。babaaにならなくてよかったね。

*7:1回戦第6試合の1問目は、久留米は39手で1位だったのですが、タッチの差で沖縄が38を出せたものの時間内に送信することが出来なかったようです。

*8:宇部は1日目の夜に久留米の解法を研究して、1晩でloliと同じようなコードを組み上げ全体順位第3位まで上り詰めたそうです。すげぇ。

*9:久留米から電車で30分ほどの場所です。