ICFPC2022 参加記

ICFPC2022に出場しました。
結果は151人中33位でした。(順位表)

ICFPC ソロ参加で凍結前37位でした。凍結後に投げた改善が思ったより大きかったので、30位代には入れてそう?
手動補助ツールで解の方向性にヒントを与える形で、出来る限り大きな四角で埋めていき、c++で情報を復元して、最後に乱択山登りをする方針でした。
楽しかったので参加記でも書こうかな。 pic.twitter.com/1JuNfrbxRd

— 玻璃 (@hari64boli64) September 5, 2022

私が観測した日本からの参加者はほぼ全員私より上ですが、あまりICFPCに関する記事は多くないように思いますし、折角なので参加記を書くことにしました。ためになる内容ではありませんが、楽しんで頂ければ幸いです。

問題概略

Specification等は主にこちらで公開されています。

特に、このpdfが最終版のSpecificationです。

細かい仕様等は省きますが、概要だけざっくり述べると以下の通りです。

• 縦横400pxの画像が目標として与えられる
• 同じく縦横400pxのcanvas(1つの真っ白なブロック)を、以下の操作を用いて出来るだけ少ないコストかつ高いクオリティで目標の画像に近づける
  • Line Cut Move 縦方向もしくは横方向にブロックを分割し、新しいブロック2つにする 基本コストは7
  • Point Cut Move 1点を中心としてブロックを四象限に分割し、新しいブロック4つにする 基本コストは10
  • Color Move ブロックを任意の色で塗る 基本コストは5
  • Merge Move 同じ形の隣接したブロック同士を交換する 基本コストは3
  • Swap Move 同じ辺の長さの隣接したブロック同士を結合する 基本コストは1
• さらにこれらのコストは、操作ごとに$size(canvas)/size(block)$が乗算される(つまり、ブロックのサイズに反比例する形でコストが増えていく)
• 最終的なスコアは、これら操作群によるコストの値と、目標画像との類似関数の値の和で、これを最小化することが目的

(ICFPCは例年仕様の追加や変更が行われるのですが、私はそれらを全く追いきれなかったので、それらは省略します)

与えられた画像の一例は以下のようなものでした。

私の推し画家であるアルチンボルドの絵(下段右)も入っていて、テンション上がりました。
また、中段右の青い画像は、ゴッホの『星月夜(ほしづきよ)』だそうです。よく目にする画像ではありますが、今回初めて名前を知りました。英語では"The starry night"というらしいです。かっこいいですね。

解法概略

私の解法の概略を述べます。

非常に重要な点として、各操作のスコアは$size(canvas)/size(block)$が乗算されるということがあります。具体例をあげると、一辺10pxの正方形は、$ \frac{400\times400}{10\times10}=1600 $ 倍になります。最終的なスコアは大体10000から40000程度になるので、このサイズの正方形に色を塗るだけで、もうほぼその値になってしまいます。
(極めて当たり前のことですが、私は中々この事実の重大性に気付けませんでした)

この性質により、大きいブロックを保持したまま操作していくのが大切なので、
Line Cut Move or Point Cut Move (細分化) → Color Move (色を変更) → Merge Move (元のサイズに戻す)
という操作を繰り返すことで、そのことを達成しています。

特に、Cutのパートに関しては、以下のように2回のPoint Cutを使用することで、任意の矩形領域を塗ることが出来ます。(あえて小さめに矩形領域を表示していますが、先述の通り、このサイズの矩形領域は実際には作りません)

また、矩形領域の辺がcanvas全体の外枠に接する時にはCutの回数を減らすことが出来るので、それらを丁寧に場合分けしながら、上記のCutの種類やMergeの順序などを適切に試すことで、出来る限り少ないコストで矩形領域を塗る関数を実装しました。(これの実装にはかなり苦労しました。)

そして、この関数を使用する上で、どの矩形領域を塗っていくかということは本問において本質的になります。

ランダムな矩形領域を試して、最もスコアが改善するものを貪欲に選択していくというアルゴリズムを最初に試しましたが、それでは色々と無駄が生じます。

例えば、以下の画像が入力の場合を考えてみます。

直感的には外側から白色→黒色→灰緑色→モナリザの部分と塗っていくのが最適そうに思えますが、このような単純なアルゴリズムでは先に形としてまとまっているモナリザの方を塗ってしまったり、灰色と黒色の中間色で部分を塗ってしまったりします。

特に、以下のチェス盤を、白と黒の中間色である灰色で塗ってしまうという実行結果が多発しました。

このことを改善する案を色々考えましたが、私にはどうにも思いつかず、結局手動ツールを作成して手動でその矩形領域を決めるという方針をとりました。

矩形領域の決め方は、モナリザの例のように外から中へということも注意すべきですが、後から上書きされるなら出来るだけ大きな矩形領域の方が良いという事にも注意する必要がありました。

以下がその一例です。

上段では、ロボットの足をそのままの形で塗っていますが、下段では足をもっと長く描いて、その後胴体部分を上塗りすることにより、小さい矩形領域を扱うということを避けています。

このことによって、操作にかかるコストをより抑えることが出来ます。

(また、この手動解を作成していく中で、さらなる改善に気付いてしまいました。上位陣がとっていたDP解と似た方針です。手動でやっていく中で、「うわー、こういうアルゴリズムを上手いことを実装すれば良かったのか…」となりましたが、流石にそれをする時間は全くありませんでした。)

そして、更にその手動解を乱択山登りで改善していきます。

例えば、手動解では当然ブレが存在するので、先のチェス盤などだと線が少しズレるということが発生してしまいます。人の目では完全に一致しているように思えても、類似関数の値は0でないということが良くありました。

そこで、手動解自体にランダムな変形を加えてスコアがどうなるかを見るという、乱択山登りを行いました。また、山登りと言っても、手動解には先程述べた貪欲アルゴリズムをプラスしているので、各実行にも少しブレがあり、かなり楽々と局所最適解は抜け出してくれているようでした。

これらを合わせると、チェス盤の出力は以下のようになって、スコアは20596でした。

ちなみに、参加者全体のベストスコアは5013らしいです。エグ…

なお、手動解を改善する乱択山登りには、色に関するランダム性も追加しています。
例えば、以下のTheの部分が一番分かりやすいと思うのですが、この部分は目標画像の色よりも少し薄くなっています。(他の色も、スポイトツールで見ると実はかなり違います)
色を背景まで考慮して塗るようにすると、よりスコアが改善されました。

私の方針としては以上です。

結果

問題は全部で40題ありましたが、その内私が主に取り組んだ、1日目の時点(Lightning Divison)で公開されていた25問に関しては、以下のスコアが得られました。

seed	score	seed	score	seed	score	seed	score	seed	score
1	20596	6	9301	11	36070	16	27219	21	25295
2	5627	7	22274	12	10016	17	42179	22	27297
3	15575	8	22337	13	14043	18	41435	23	31036
4	18468	9	13964	14	26174	19	33774	24	23799
5	18823	10	31342	15	30649	20	24900	25	34244

これらの合計値は606437です。

ICFPC Lightning Divisonお疲れ様でした〜、残り48時間!! pic.twitter.com/DHMImlMtHw

— Takuya Akiba (@iwiwi) September 3, 2022

iwiwiさんのこのツイートにある画像によると、どうやら1日目時点における6位相当のスコアだったようですね。それ以外の問題がボロボロでしたが、善戦できた方では? と思っています。

同時に、Unagi(Chokudaiさんやwataさんのチーム)のヤバさも伝わってきますが…
(1日目で401296って何???)

他の方々の解法

優勝したUnagiのレポジトリは以下で公開されています。DP解などが紹介されていますが、流石すぎるといった感想です。

また、これはICFPのDiscord上で共有されていた話で、(ネットリテラシーの関係上)直接載せることはできないのですが、26問目から35問目までのグリッド状の問題に対して、非常に上手いブロック同士のマージの方法が紹介されていて感心しました。

これらの問題は一度全てのブロックをマージする必要があるのですが、あえて途中で切断を挟みながらマージしていくことで、小さい矩形領域を扱うのを避けられ、より少ないコストで操作を達成していました。

全く考えもしなかったことですが、これが出来ているとスコアに対する影響が大きいので、もっと順位も上がっていたかも知れません。悔しい。

[追記]
そのチームによる解説記事があがっていました。
こちらから見ることが出来ます。

マージ方法以外にも、色々なるほどという内容が記載されていました。

その他感想など

今回は問題の提出をAPI通信で行う事が可能だったので、それをしようと思ったのですが、整備が大変でした。説明がその時点では公開されていなかったので、TypeScriptを使って手探りでやったらうまく行かず(ファイル読み込み時のasync/await関連でかなり詰まりました)、結局Pythonを使ったらすんなりいきました。また、入力もpngやJSONでtxtではないので、それをデータ化するのにもPythonを使用するなど、思ったよりもPythonやBashを使用しました。

また、TypeScriptのサンプルコード的なものをC++に導入する際に、structの型変換で詰まりました。

export type Instruction =
  | NopInstruction
  | CommentInstruction
  | ColorInstruction
  | PointCutInstruction
  | VerticalCutInstruction
  | HorizontalCutInstruction
  | SwapInstruction
  | MergeInstruction;

こういう型定義がTSのファイルにあり、「確かにTSではこういうコードをよく書くけど、C++でどうやって書くんだ...?」となり、std::disjunctionが(実際に関数で使用する上では)それに近いのかと思って調べていましたが、結局まだよく分かっていません。(参考)

TypeScriptは結局のところJavaScript、つまり動的型付け言語なので、asやanyでどうにでもなるのですが、C++は流石にそうもいかず、virtual(仮想関数)とoverrideで何とかなるかと思いきや、なりませんでした。(StackOverFlow曰く、私のやろうとしていることは不可能だと書いてありました。別の方針もあるのかも知れませんが…)

この辺のグダグダは、かなり反省点です。公式のコードもあくまで参考程度に留めるべきだったかも知れません。

ビジュアライザに関して言えば、公式のPlaygroundにあるのを、自分側のReactに移植しました。8月に自作ビジュアライザを準備した甲斐が少しはあって良かったです。特に、公式のコードがエラーメッセージの部分でJSON.stringify()を忘れていて(?)、その部分を正確なエラーメッセージが出せるように直せたのは良かったです。
尤も、仕様が変わってしまったので、このビジュアライザは結局殆ど使用しませんでした。
めちゃくちゃアニメーション機能的なのも欲しくなりましたが、それは用意しておらず、準備不足でした。

なお、実際に多用した手動補助ツールは、もっと作成に時間がかかるかと思っていましたが、案外2日目の夜の3時間くらいでサクッと作れて、「ちょっとは自分も成長したな~」ってコンテスト中で一番ニマニマしてました()

Reactではコンポーネント間の情報の受け渡しが少し難しいので、このくらいの規模感だったら素のTypeScriptの方が速いとなり、ゼロから実装したのですが何とかなってよかったです。(逆にこれが出来ていなかったらもっと破滅していました)

GitHub Pagesで今は公開しているので、もしよかったら遊んでみて下さい。(補助目的なので、スコアも何も出ないのですが…)

ソースコード等はこちらです。

---

以上です。
お読みいただきありがとうございました。