はじめに
この記事は 東京高専SPC同好会/プロコンゼミ老人会 Advent Calendar 2022 4日目の記事です。
本記事の目的
本記事では、私が高専時代に参加してきた全国高等専門学校プログラミングコンテスト競技部門の問題・解法などを振り返っていきたいと思います。
懐古のために書いている記事ではありますが、この記事が後年の参加者の助けになれば嬉しいです1。
procon28（2017年 大島大会）
この年はprocon27に引き続いて木工パズルを解く問題で、「画像認識でパズルのピースを埋めるパート」「探索でパズルの解を探すパート」のそれぞれの処理を上手く行う必要がありました。また、得点の低下と引き換えにヒント情報を得る事ができ、ピースの形状情報ヒントを得る事で前者のパートを省略する事が可能でした。
僕はそれぞれのアルゴリズム部分には特に触れていないのですが、前者は木工パズル特有のカット時誤差・スキャン時の測定誤差などがあってかなり厳しく、後者のパートはビームサーチ等で解けたそうです。
当時は高専1年で入学時点ではプログラムもロクに書けない状態だったのですが、2つ上の @_nosita 先輩に誘われてチーム「Cult of the Part Parrot」で参加する事になりました。（本選メンバーには含まれていません）
QtとC++での開発で、僕や他の一年生はビジュアライザを書いたり問題の自動生成をしたりしていました。リポジトリは これ です。
大会では産技品川の方が画像認識パートの輪郭抽出・エッジ検出等を高精度で行った結果唯一ヒント無しで問題を解き優勝、2位以下は形状情報を使ってパズルを完成させており、僕たちは決勝5位で特別賞となりました。
procon29（2018年 徳島大会）
この年も競技部門に参加しました。チーム「人間の力」のチームリーダーをして、アルゴリズム・ビジュアライザ等諸々を書きました。 リポジトリは これ です。
今回の競技はグリッド上での2人対戦陣取りゲームです。各マスには得点が振ってあり、プレイヤーは複数体のコマ（エージェント）をターン毎に動かしながら陣地（タイル）を確保していきます。
自分が確保した（エージェントが踏んだ）マスの得点に加えて、自分のタイルで囲んだマスの得点ものチームの点数となるため、基本的に高得点のマスを踏みつつ要所要所で囲んでいく戦略が重要になる、という展開が想定されていたと思います。
と、ここまで書くと良いゲーム問題のように感じてしまいますが、実態は大きく異なりました。
まず、このゲームですが、会場に1マス50cm程度のグリッドが物理的に存在し、その上でグリッド上に紙製のタイルを置いて戦います。競技部門は例年3人チームで参加するのですが、そのうち1人が司令塔としてグリッド外でパソコンを操作、残りの2人は実際にグリッド上でコマとして動きます。
また、司令塔はエージェントに次の行動（移動・タイル削除など）を指示する必要があるのですが、この情報伝達には音声やその他通信を使う事ができず、A4サイズのトランプを用いて行う必要があります。
ターン毎に盤面は変化していくのですが進行中の盤面状況は与えられないので、コマとタイルの動きを目視して盤面の変化を確認し、パソコンを操作して手元のソフトウェア上に盤面を反映する必要があります。一度でも盤面入力を失敗すると手元と実際のフィールド情報に齟齬が発生してしまい悲惨な事になります。
各ターンでは「前ターンでの4人分の行動の確認」「手元のパソコンへの入力」「次の手の決定」「味方コマへの行動指示」を全て行う必要があるのですが、ターン間の猶予時間は10～15秒程度しか存在せず、ほとんどのチームは盤面の入力すらままならないまま、アルゴリズムの段階にも辿り着けずに競技を終える事となりました。
大会2日目になると上位チームは操作に慣れてうまく通信・盤面反映ができるようになったのですが、それでも相手の動きが簡単に分かってしまう事やそもそもパソコンを触っている余裕がない事などが原因で、人間がその場その場でアドホックに考えて行動する方が強いという結論となってしまいました。
募集要項に「メンバー間の頑健かつ効率的な通信方法が勝利のカギになります。」と書かれている通り、運営の想定では相手のトランプの札から移動方向を推測してメタを張ったり、それができないように分かりやすく突破が難しい暗号化方法を構築したりすることを考えられていたようなのですが、たかだか15秒の間にそんな芸当ができる訳もなく、適当に選んだトランプを持って腕を移動方向に大きく振るような方法で通信をするチームが上位を含めほとんどを占めていました。
見栄えを良くするために導入したであろう人力要素でしたが、各タイルの得点が競技者以外に見えない事からそもそも試合中はどちらが優勢なのかすら分からないような有様で、講評では審査委員長の神沼先生から「競技部門は何をやっているか分かりづらかった」という感想が飛び出したりしました。
私達のチームは夏休みに産技品川と模擬試合をやったり直前に部屋を借りて人力操作の練習をした結果「これどうせまともな試合にならないんじゃね……？」という結論に辿り着き、盤面の手入力が簡単なUIの整備に力を入れたりしていました。その甲斐あってか予選時点でそこそこまともな試合ができて決勝トーナメント進出、2日目は対戦相手が操作に慣れた事もあり少し厳しい試合もありましたが無事決勝までたどり着く事ができました。
決勝ですが、自分がQRコードで読み込んだ盤面を誤って180度回転させた状態で戦ってしまい、仙台名取にボロ負けしてして準優勝でした2。
ちなみに使用したアルゴリズムは簡単なDP・DFSをベースにしたもので、陣地を囲むと手に入る領域ポイントはアルゴリズム上では無視していました。アルゴリズムは人力の補助として運用し、半年間かけて鍛えた人間の判断力を活かして戦っていきました。
この年は問題が凄くて最早アルゴリズムで戦うとかそういうレベルではなかった印象です。 今後はこのような問題が出ない事を願っていますが、もし出題された場合はアルゴリズムによる解決に固執せず、早い段階で人力に振りきってしまうのが良いと思います3。
procon30（2019年 都城大会）
この年もチームリーダーとして参加しました。チーム名は「独立行政法人国立高等専門学校機構東京工業高等専門学校」です。今回も昨年と同じくアルゴリズムやビジュアライザをゴリゴリ書いていました。 リポジトリは これ です。
今回の問題は前年と同じ陣取りゲームで、物理的な要素がなくなりサーバーを使って通信するようになった所が大きな変更点です。 得点に関する基本的なルールはほぼ変わりませんでしたが、扱うエージェント数が増えたりターンの間隔が短くなったりといくつかの細かい変更が行われました。
今回の問題では物理要素がなくなったため純粋なアルゴリズムの要素が強くなると考えられ、実際に様々なアルゴリズムを実装して性能確認を行ったりしていました。 コードを書いていく中で領域ポイントの判定（タイルが囲んでいる領域の判定）が非常に重い事が課題となりました。 これは領域ポイントを考慮するアルゴリズムでは避けられない問題であり、かなり厳しいです。
結局この課題は10月頃まで解決できず決定的な手法も見つからないような状態だったのですが、ここで「別に人力でどうにかすればよくね………？」という結論に至り、その方針で考え直す事にしました。
その結果、去年と同じくDPやビームサーチをベースとしたアルゴリズムを用いて（領域ポイントを考慮しない）自分と相手の行動を求め、盤面を見ながら人間計算機の力で適宜修正していくという手法に落ち着きました。
人力を混ぜる都合上UIは極力使いやすいように整備し、サーバー関連の動作確認も念入りに行いました。特にサーバーとの通信は失敗しているチームが多く、予行演習の段階では7割程度のチームが通信できていませんでした。
大会では順調に勝ち上がり、予行演習から決勝まで意図的な敗北を除けば全勝で優勝する事ができました。また、同時に参加していた課題部門・自由部門についても東京高専の他チームが最優秀賞を獲得し、全部門で最優秀賞という結果になりました。
余談ですが、NAPROCK国際プログラミングコンテストという（高専プロコンと運営が同一の）プログラミングコンテストが存在しており、例年は10月の高専プロコンと同時開催されていました4。 今回はNAPROCK国際プロコンが初の国際開催となり、私達を含む高専プロコンの上位チームは2020年にベトナムのハノイで開催される予定であったNAPROCK国際プロコンに招待される事になりました。
procon31以降
当時～2022年現在の東京高専プロコンゼミでは3年生でプロコンから引退する慣習が存在していたため、2020年以降は高専プロコンには参加していません。
一応覚え書き程度に記しておくと、2020年3月から流行した新型コロナウイルスの影響でNAPROCK国際プロコンは中止となり、procon31はオンライン化、競技部門はその都合で中止となりました。
また、その翌年は競技部門が復活したものの完全オンラインでの開催となりました。
競技部門の問題はprocon25を元にしたスライドパズル+画像復元問題であり、強い競技プログラマの方が優勝・準優勝されていました。
おわりに
高専プロコン競技部門について振り返りました。
高専プロコンの問題は例年
- 問題中の定義が不明瞭だったり
- 人力要素を入れた方が強かったり
- 実際に解けない最悪ケースがルール上存在したり
- テストプレイされているとは思えない内容だったり
- 参加者のレベルと問題の難易度に大きな差があったり
するので、現役の方は苦しんでおられると思います。頑張ってください。
競技の問題については酷いものは本当に酷い（僕の参加分だとprocon29など）のですが、
近年は毎年ちゃんと考察して良いアプローチを取ったチーム（いわゆるアルゴ勢のいるチーム）が順当に上位に来ているような印象があります5。
また、老害的なアドバイスですが、現役の方は
- ルールに関する質問はドシドシ投げる
- サーバーを使う競技の場合は事前に十分テストする
- 操作パートが快適にできるようUI部分を整える
- 人力を入れた方が強い場合を考慮する
- 終盤の限界開発をしない
などをしておくとよいと思います。
カスみたいな問題に対してキレながら実装していた事も今となっては良い思い出と言えなくもない気がします。開発期間中は苦しいと思いますが是非頑張ってください。
- 高専プロコン競技部門では過去問題のリメイク再出題がされる事が多く、僕も先人の参加記を読んでアイデアを貰ったりしていました↩
- 操作ミスを言い訳にするの本当に負け惜しみっぽくて嫌なんですが、実際にこのミスが原因で数百点差がつきました。決勝後に教員に「これ誰が悪いんですか」みたいな事を言われてつらい気持ちになったのを思い出しました。↩
- コンテストとしてどうなんだ……という気持ちにはなりますが、過去に何度も前例がある以上人力とどうにか向き合うしかなさそうです↩
- 海外チームがオープン参加のような形式で参加していたり表彰式で2回同じ表彰をしたりしてるアレです。僕の入学前のタイミングでは国内の他大学も参加可能となっており、procon25では東大チームが優勝していたそうです。↩
- こう書くと自分の事を褒めてるみたいでかなり微妙なんですが、特にここ数年 (procon32,procon33) はアルゴリズマーの方がちゃんと競技をされていて凄いです↩
