Tue Jul 13 2021

ICFPC2021 に参加した

negainoido というチームで参加し, 凍結直前の最終スコアボードでは 12 位だった.

今のチーム構成で参加するのは4,5年目くらいなので大体誰が何を担当するかが決まってる. なにせ三日間あるコンテストなので, 初日からゲーム AI (solver) を書き始めるのは二人程度いたら良くて, 二日目以降に人のをフォークして自分の AI を書くというスタイルでやってる. ICFPC は自分たちでビジュアライザを作ったり, 解を管理するといったインフラの整備も同様に大切. プログラムではなくて解を提出するというスタイルなので, 各問題に対する解を全部データベースに貯蔵しておいて, 裏で動いてるバッチがその中から最良のものを数分おきに提出させる仕組みが必要だった. また, 解ければ何でも良いので, 手で解いてしまうのもバカにはできない手段だ. 今回の問題も根気(と, よく出来たツール)さえあれば手で解けてしまうような問題が含まれていた. AIと人間が上手くお互いの欠点を補って作業する, みたいな, そういう用語があるよな. 今回の問題は特にそういった傾向が強く感じた.

というわけで私は初めから, ビジュアライザ兼エディタを初日から作り始めることにした. 結局私は最後まで AI は書かずにずっとエディタの機能追加と手で解くことを交互にやっていた.

問題概要

連結単純グラフが与えられる. 平面上にこれを配置せよ.

\(\epsilon\) は大抵十分小さいので, 隣接点から円を描いてその重なる点に置くしか無い. しかもそれは整数座標である必要がある. そして次で表される dislikes という値を最小化したい.

雰囲気を伝えるためだけにわざと大雑把な説明に済ましたが, 実際には全て整数だけで計算可能なように, \(\epsilon\) は 1e6 倍でスケールされていたり, 距離は平方ユークリッド距離(平方根をとらない)だったりする.

元ネタ

エディタできた

ここ最近色々フロントエンドフレームワークを触っていて, Svelte というのが良さそうと教えてもらった. 今回のエディタも Svelte を使って web アプリとして作成した. 見た目は使い慣れてる Bulma という css フレームワークで作ったので適当にやってもまあまあ良さげになる.

いくつかの問題は

といった性質があり, 人間の直感と美的センスをうまく使って解くことができた.

元問題 (#68)

エディタによって得られた解

とくに周囲から置いてくのが大事.

上の例のように初めに与えられるグラフはぐちゃぐちゃに折りたたまれているので, これを上手に「ほぐす」必要があった. 初めは, 頂点同士にいい感じに斥力を与えたり, エッジをバネのようにしたりなど物理シミュレーションをエディタに実装し, それをなんとか使っていたのだが, 三日目にしてチームメンバーの autotaker さんが graphviz を使うことを思いつき dotsolver が生まれた. graphviz は, 最強. Svelte も最強.