24時間耐久ノンストッププログラミングコンテスト（TCO20 Marathon Final）

Competitive Programming (1) Advent Calendar 2020 11日目の記事です。

Topcoder Open 2020 について書きます。

tco20.topcoder.com

Topcoder Open(TCO) とは

Topcoderが年に1度開催している、世界最強プログラマー決定選手権です。

1年ほどかけて予選が行われ、そこで勝ち抜いた各部門*1の10人ほどが、例年11月くらいにアメリカで行われる決勝に招待されます。

TCO20

今年はパンデミックのせいで例に漏れずオンラインでの開催になりました。かなしいね

まあプログラミングコンテストなのでオンラインでも十分実施可能…

と思いきや、Marathon部門は決勝は例年 10時間コンテスト で、オンライン開催で10時間コンテストやろうとすると時差が困ったねということに。

f:id:tomerun:20201211015838p:plain
これは無理みたいな感じ

色々協議されましたが、24時間コンテストにするのがタイムゾーンによる差が小さかろうということで、24時間で開催されることになりました。日本時間では日曜昼12時-月曜昼12時。タイムゾーン的にはだいぶ有利な時間帯だったんじゃないかと。

「予選が1週間なんだから、決勝もせっかくオンラインなら1週間でいいじゃないか」という提案もしたんですが、不正対策を徹底するためコンテスト中はスクリーン・カメラ・音声を共有してadminが常時監視するもとで競技を行う形にしたいということで、長期間にするのは却下されました。TCOチャンピオンという肩書きはかなり重視されていて、少なくない賞金*2も出るし厳密にやりたいということみたいです。

イベントは、 Hopin というオンラインカンファレンス開催プラットフォーム？を使って行われました。この中で複数のセッションが作れるので、各コンテスタントがセッションを作って画面共有し、adminがそこを見にくる。それと別に全体集合用のセッションがあったりする。

常時監視といっても、トイレ行ったりコーヒー入れたりの2,3分の離席は好きにどうぞということになっていて、10分以上席を立って休憩するような時はチャットで一言入れる感じ。途中で数時間寝てた人もいたのかな？

コンテストの様子

コンテストページ : https://www.topcoder.com/challenges/bac87d23-90d8-4d8a-afc1-a6b8fee3c6bb

問題の内容は この記事 の画像を見てもらうとわかりやすいです。大きな円の中に長方形や円を敷き詰めろという問題。使える長方形や円のサイズのリストと、長方形と円の比率をどれくらいにするのが良いかのパラメタが入力として与えられる。 テストケースによって、円ばっかり使った方が良かったり、長方形ばっかりが良かったり、半分ずつが良かったりする。

コンテスト中につけてたメモを見つつ24時間の動きを振り返ってみます。

  • 11:10
    • 起床。食料の買い出しに行った
  • 12:10
    • 問題を読んだ。この問題で24時間やるの、細かい詰めが必要で神経を削られそう
    • アニメーションもなくてビジュアライザを大きくカスタマイズするのは不要
  • 12:50
    • 入力を読んで1つ置くだけの自明解を作る、テスト用にテストケースの生成を少しカスタマイズする、スコア比較用スプレッドシートの準備など
  • 13:40
    • 一つずつランダムに位置を試して置けるなら置いていくだけの回答を作成、提出
    • スコアは73%くらいで、みんな早いなあとなる
  • 14:40
    • いつのまにかHopinの画面共有が落ちていることに気づいた（やたらHopinがCPU食うので、それを少しでも防げればとブラウザウィンドウを最小化してたので気づかなかった）
    • つなぎ直しても何度も2分くらいですぐ切れてコンテストどころではない感じになりかかったけど、WiFiルータの設定をいじったら改善した
  • 17:50
    • 考察すると、長方形は長方形同士で集めると隙間なくぴったり詰めることができそうだという気持ちになる
    • ということで、長方形は下側から、円は上側から置いていくような埋め方をして、長方形同士、円同士で集めるようにする
    • 大きいサイズの部品を使った方が面積密度高くてよさそうなので、サイズ大きいのから順に試す
    • 一つずつ部品を試していくときに、次に円を使うか長方形を使うかは、これまで置いた部品の合計の面積と入力パラメタによって決める（重要）
    • ここまでやって提出してスコア97%。やっと形になってきた

f:id:tomerun:20201212010913p:plain
ここがスタートライン

  • 18:20
    • 時間10倍にして実行しても0.5%くらいしか増えない。まだまだ高速化に手を出す時ではなくて他にやるべきことがある
  • 21:30
    • 間違いなく解をインクリメンタルに更新していく形式にしないと話にはならないので、実装大変だけどやった
      • 小領域を破壊して埋め直す、という近傍
    • まだ愚直な実装なので1000イテレーションくらいしか回ってないけど1%くらいはよくなって98%台に乗った。
  • 23:00
    • 枝刈りとか頑張って100倍くらい高速化する。99.57 出て暫定2位まできた
  • 23:40
    • 高速化されたので多スタート試してみたがよくならず
  • 24:00
    • なんかOSがメモリ不足とか言ってきて、Hopin（を動かしてるFirefox）がメモリ50GBとか使っていることに気づいた
    • ブラウザ再移動したけど、Hopin動かしている限りメモリ増え続けるので、この後も3時間おきくらいに再起動してた
  • 01:20
    • 細かいバグを直したり調整したりで99.72まで増やして暫定1位！

f:id:tomerun:20201212011028p:plain
記念撮影

  • 01:40
    • 山登りでやってたのを焼きなましにしたけど、効果なし
  • 03:20
    • 変なバグがないのを確かめるため、一度5000ケースでテストを流す
  • 03:30
    • 山登りの途中のスコア評価では真のスコアを使っていたけど、序盤は円と長方形の比率を調整する項の重みを落としておいて徐々にその重みを上げていくことで、まず面積最大になるように詰めてからあとで比率を調整するのが良さそうでは、と考えた
      • 比率の調整よりも面積を詰めるのの方が難しいので、そちらを序盤に先に最適化させたい
    • やってみると0.5%増えた。このスコア分布の中ではこれはかなり大きな進捗
    • もう終了直前まで提出はしないでおこうと決める
  • 05:00
    • 速度3倍にすると0.5%くらい増えることはわかっているので、高速化（または遷移の受理率を上げることでの実質高速化）手段がないか頭をひねるがもうだいぶ搾り取られてしまっていて厳しい…
  • 06:00
    • 初期解は、最初作ったままの上半分に円、下半分に長方形というもののままだったが、長方形は全体の円の上下と左右に置いて、逆に円は対角線上に集めた方がいいのでは、と考える
      • 長方形を対角線上の円周近くに置くと死にスペースが多くできてしまうが、上下や左右だったらまだマシ
      • 円はどの方向に置いても同じ
    • この考察を元に初期解をいじってみたら0.1%くらい上がった
  • 〜11:00
    • その他あらゆる細かい調整を重ねまくって0.3%くらい稼いだ
  • 11:20
    • ほぼ完成版のつもりのものを提出。99.53で暫定3位。まあ提出する前の想定通りくらいだった
  • 11:50
    • その後もすぐ入れられる改善がないか探していて、一つ当たりを引いて0.05%くらい上がったので急いで入れた
    • ら、提出した時に実行時間を9.8sまで伸ばすのを忘れていてすぐさま再提出
      • 手元では6sで動かしていたので
      • いやコンパイルオプションで自動でタイムリミットの定義はローカルとサーバーで切り替わるようにはしているんだけど、微妙な潜伏のためサーバー上も6sで実行するようにしていたのを忘れていた…
    • 1回は再提出できる時間が残っていることを確認してからの提出はしていたので、まあ落ち着いてはいた
    • なんか順位表上は0.05%どころじゃないほど伸びて暫定1位になってしまった
  • 12:00

ということで、長い休憩はとらずノンストップで走り抜けました。終わった後寝ようとしたけど、30時間近く起きてたのに頭を酷使したせいで全然寝付けなくてつらかった

最終結果は予想通り3位でした。これまでのTCO Finalの結果は5位,4位,4位,5位だから最高順位だ。

感想

24時間コンテスト楽しいですね。10時間コンテストだと、考察スピードと手の速さ的にだいぶ不利なので…。とはいえまあ楽しめるのは年1回までかな

体力的には、ICFPCでも同じように24時間連続稼働に近いことはやっているし、そう問題は感じませんでした。

HopinがCPUとメモリを大量に使いまくって、5年ものMacbookAirではだいぶ辛さがありました。ローカルでの実行結果が全く当てにならない。 テスト用に72coreのAWS EC2インスタンスを占有で貸してもらえたので、ずっとそこでテストしまくってました。これがなかったら完全に無理だったに違いない。

500件のテストを1セットとして、それをコンテスト中に130回以上やってたみたいです。

f:id:tomerun:20201212012409p:plain
テスト結果の表

コンテスト終了後に気づいたんですが、小領域を壊した後に円を置けるかどうか試すところの判定がガバガバで、実は置けるのに棄却しちゃってるパターンが大量にあることが発覚…。ビジュアライザは完成系しか見てなくて、遷移中どんな感じで動いているかを見てなかったのがよくなかったか。 実際最終結果のstatisticsでも、円をたくさん置くテストケースの結果が激弱でした。 このビジュアライズをちゃちゃっとできるように意識していこう。

*1:Algo・Marathon・Development・First2Finish・Design・QA

*2:優勝賞金1万ドル