私のスコア問題評価環境

スコア問題の解答の評価を行う環境をAWSで組んでいます。どのようなシステムになっているかを紹介します。

費用はそこそこ抑えられていると思っていて、AHC031での実績は 1000ケース*2秒のテスト実行を165セット行って$5くらいのコストでした。

概要

AWS Batch で実行してます。

処理の詳細を順に説明します。

1. Dockerイメージをpush

採点環境となるDockerイメージをbuildしてECRにpushしておきます。

どういう環境にするかは、AtCoderの 言語アップデートのスプレッドシート を参考にするとよいかも。

イメージのエントリポイントとして、「S3から $(環境変数で指定される提出ID)/solver.zip をダウンロードして展開し、その中にあるrun.sh を実行する」というシェルスクリプトを指定しておきます。

これはコンテストごとには行わず、共通のイメージを使います。そうできるよう、エントリポイントを汎用的なものにしています。

2. テストケースをS3にアップロード

コンテスト開始時に、採点に使うテストケースを生成し、zipにまとめてS3にアップロードしておきます。

3. ソースコードをS3にアップロード

テスト実行ごとに、解答のソースコードと、テスト実行時に呼ばれる run.sh をzipにまとめてS3にアップロードします。

S3のパスは $(コンテストID)/$(日時のDDhhmm)/ としてます。日・時・分をIDにしているので1分間に複数回実行できないですが、数十秒待てばいいだけだし視認性を高める方を取りました。

run.sh の例 : https://github.com/tomerun/AHC031/blob/master/run.sh

• 環境変数で指定された値を元に、実行するseedの範囲を定める
  • AWS_BATCH_JOB_ARRAY_INDEX は、AWS Batchの配列ジョブで設定される、自分が何番目のジョブかを表すインデックスです。これを使って、ジョブ0はseed1000~1099、ジョブ1はseed1100~1199、のように実行するテストケースを設定します。
  • だいたい 100ケース * 10並列 くらいで実行してます。
• S3から 2. でアップロードしたテストケースをダウンロードして展開する
• ソースコードをコンパイルする
• 実行して log.txt にスコアなどの情報を出力する
• log.txt をS3にアップロードする

4. 5. 6. テスト実行

aws batch submit-job のコマンドで AWS Batch にジョブを投げます。

AWS Batch は内部で自動的に適切な数のEC2インスタンスを立ち上げてジョブを実行し、終了したらインスタンスを終了してくれます。

3.でアップロードした run.sh が実行され、テストケースのダウンロード・解答の実行・結果のS3へのアップロードが行われます。

この内容は、一つ前の3.と一緒にひとつのスクリプトで実行できるようにしてます。

AWS Batchについて色々

• コンピューティング環境の設定で、インスタンスタイプはc系のスポットインスタンスが使われるようにしてます。
  • スポットインスタンスなのでまれに強制終了されることもあるのですが、かなりまれなのであまり気にしてません。
  • どうしても防ぎたければ、オンデマンドインスタンスを使用するコンピューティング環境も作っておいてそっちに切り替えれば問題ないです。
• EC2インスタンスを立ち上げるのに数分かかるため、その分の実行時間が余計にかかります。
  • 前回のテストが直前に実行されていればそのインスタンスを再利用してすぐ始まってくれたりはします。
  • コンテスト終了間際などで数分待つのも惜しい場合は、コンピューティング環境の設定を変えてインスタンスが常時立ち上がっているようにすることもできます。当然その分EC2の費用はかかりますが。
• 各ジョブには2vCPUを割り振ってます。
  • 以前実験したとき、1vCPUだと実行時間が単に遅いだけでなくだいぶ不安定になっていたため、少々もったいないですがシングルスレッドでも2vCPU使ってます。
• 同じインスタンスタイプでも、どうしてもインスタンスガチャ要素はあるようです。同じソースコードで実行しても、はっきりとした結果の優劣が出ることがたまにあります。

パラメタを振ったテストを行いたいとき

例えば焼きなましの初期温度を 1,3,10 のそれぞれで試したい場合、環境変数で INI_TEMP=1, INI_TEMP=3, INI_TEMP=10 のようにそれぞれのパラメタの値を渡したジョブをパラメタの数だけ作り、投げます。 run.sh でコンパイルするときに -DINI_TEMP=$INI_TEMP のようにして解答に反映します（コンパイル定数ではなく、解答にも環境変数で渡すようにするのもアリです）。

S3のパスは $(コンテストID)/$(日時のDDhhmm)/$(パラメタの値)　のように、パラメタごとに別々のパスになるようにします。

7. 終了通知

ジョブが終了したら、そのイベントをトリガーにEventBridgeから slack webhook へリクエストすることで、ジョブの成功または失敗が自動で通知され、終了したことがすぐわかるようにしてます。

8. 結果のダウンロード

ジョブが終了したら、S3にアップロードされた実行結果をダウンロードしてきます。

aws s3 sync コマンドを使ってます。

9. 結果の分析

8.でダウンロードした結果をcutコマンドとかでなんやかんやしてスプレッドシートに入れ、好きに分析します。

スプレッドシートの例

結果はDBに入れていい感じのフロントエンドを作るとか、Google Sheetsに自動で入れるとか、手作業を減らせる方法はあるとは思うのですが、分析はアドホックに色々行いたいと思うので柔軟性を最大化したくてこうなってます（あとは普通に開発が面倒というのももちろんある）。

あと、結果はJSONLとかの構造化データになっていた方が扱いやすいとは思うのですが、解答をC++で書いたときに標準ライブラリではそういった形式に出力できないので、プレーンテキストを文字列処理する形にしてます。

補足：実行環境をAWS Lambdaにすることについて

AWS Lambda で実行すればインスタンス起動のオーバーヘッドはかなり減り、並列度を大幅に高めることもできる（AWS BatchはEC2インスタンスの起動・終了のオーバーヘッドがあるので1000ケースを1000並列で1ケースずつ実行するようなことは非現実的だが、Lambdaだとそれができる）のですが、

• ICFPCなど、コンテストによってはLambdaの限界である15分より長く実行したい場合がある
• インスタンスガチャ要素がAWS Batchよりさらに高そう（実験したわけではない）
• 対vCPU時間でのコスパはAWS Batchに比べて悪い

といった理由で、採用しませんでした。

短期コンテストで使用するにはLambdaの方が良さそうではあるのですが。

BFSを繰り返すときに訪問済みかを記録する配列を毎回初期化しなくて良くするアレ

あまり広まっておらず知る人ぞ知るテクみたいになってる気がしたので。

グリッド上でBFSをするときに、単純に書くとこのような感じになると思います。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    vector<vector<bool>> visited(H, vector<bool>(W));
    visited[r][c] = true;
    int qi = 0;
    while (qi < queue.size()) {
        auto [cr, cc] = queue[qi];
        for (int i = 0; i < 4; ++i) {
            int nr = cr + DR[i];
            int nc = cc + DC[i];
            if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
            if (visited[nr][nc] || grid[nr][nc] == WALL) continue;
            if (grid[nr][nc] == GOAL) return true;
            queue.emplace_back(nr, nc);
            visited[nr][nc] = true;
        }
        qi++;
    }
    return false;
}

とりあえず、毎回メモリ確保するのを避けるため visited を毎回作らないようstaticにしましょう。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    static vector<vector<bool>> visited(H, vector<bool>(W));
    for (int i = 0; i < H; ++i) {
        fill(visited[i].begin(), visited[i].end(), false);
    }
    visited[r][c] = true;
    // 以下略
}

同じBFSを何回もやるのだけど、ほとんどのケースではグリッド全体を見ることなく探索が終了するというシチュエーションがしばしばあります。
そのような場合、 visited の初期化に無視できない時間がかかり、削減したくなります。

「今回が何回目のBFSか」（下のコード中でいう bfs_cnt ）を保持して、 visited を「今回のBFSで訪問したかどうか」のboolではなく、「直近で何回目のBFSで訪問したか」のintで持つようにすると、BFSのたびにH*Wの配列を初期化する必要がなくなります。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    static vector<vector<int>> visited(H, vector<int>(W));
    static int bfs_cnt = 0;
    bfs_cnt++;
    visited[r][c] = bfs_cnt;
    int qi = 0;
    while (qi < queue.size()) {
        auto [cr, cc] = queue[qi];
        for (int i = 0; i < 4; ++i) {
            int nr = cr + DR[i];
            int nc = cc + DC[i];
            if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
            if (visited[nr][nc] == bfs_cnt || grid[nr][nc] == WALL) continue;
            if (grid[nr][nc] == GOAL) return true;
            queue.emplace_back(nr, nc);
            visited[nr][nc] = bfs_cnt;
        }
        qi++;
    }
    return false;
}

HACK TO THE FUTURE 2022 本選 参加記

HACK TO THE FUTURE 2022 本選 に参加して、2位になりました。

このコンテストで高いスコアを取っていた参加者の多くが、「右手法や左手法を実現するコマンド列を作って、その繰返し回数の組合せを探索する」という解法でした。

• c7c7さん
• terry_u16さん
• chokudaiさん

一方、自分は右手法・左手法は作れず違う方針をとったので、どうやったのかを書き残しておきます。

天才パズルみたいに右手法左手法を賢く構築するなんて無理でしょ、という人への参考になれば。

スタート〜開始3時間時点（23376682点）

さすが本選の問題、一目ではどうやるのか全然見えないので、ビジュアライザにいろいろコマンドを打ち込んで動かしてみる。

大抵はすぐ同じ場所を動き回るだけになってしまって、繰り返しにあまり意味が無い。ただ、たまーに数十個のマスを訪問してくれるのも出てくる。

ちょっと考えて良い感じに動く一般的なコマンドを構築しようともしたけれども、すぐにはわからなかったので、 ランダムにコマンドを生成してたくさん動き回ってくれるのを探す 感じかなあ、と考える。コンピュータの計算パワーに期待しよう。

盤面サイズが20x20と小さめなのと、移動回数が5000回と少々余裕があることもあって、きっといけるだろう。

コマンドの生成方法は… 既存のコマンドの一部を変更して山登りするような方法は、途中の動きが少しでも変わるとそれ以降が全然別の動きになってしまうから、意味がなさそう。 独立にランダムに生成するしかないだろう。

繰り返しのネストを4段階まで、移動回数が指定した回数以下になるようなランダムなコマンドを作って、シミュレーションして何箇所のマスを訪問できるかを調べ、一番多いものを採用、とする。 なかなか実装が大変で、生成したコマンドの移動回数が思ってるのと微妙に違っていたりして、かなり苦しんだ。

1回のコマンドでは400マス中せいぜい320マスが訪問できる程度だったけど、そこから継続してまた別のコマンドを作ってシミュレーション… を繰り返せば、残っている未訪問マスをだんだん潰していけることもわかった。

結局、最初の解答としては次の貪欲法になった。移動回数が5000を超えないように気をつけつつ。

• コマンドをランダム生成（移動回数1500回以下）してシミュレーションし、訪問マス数/コマンド長 の効率が最大のものを採用
• 移動回数が4500回以下、かつ未訪問のマスがある間次を繰り返し
  • コマンドをランダム生成（移動回数200回以下）してシミュレーションし、訪問マス数/コマンド長 の効率が最大のものを採用
• 残っている未訪問マスに1つずつ移動
  • 巡回セールスマン解くべきかもしれないけど、実装大変だし、そもそもこの部分に頼らずランダム生成だけで全マス拾えるようになるべきだして、BFSで1つずつ取っていくので十分だろうということでそうした

この時点の出力はこんな感じ（seed=0 265652点）。わけが分からない感じですね。

6(FL5(7(llFFRF)FFr)RF5(RR))8(LrlFL7(Fr)F)7(RrF6(lFFR)R)5(RFLF5(rrFL)4(rFF)FFL)30(FRll)24(Fr)6(F4(lrr3F)r)9(3FL)7(3(Ll3FR)FRF)9(FRl3FLF)9(llFFr)8(7(FFr)R)6(lL8(LrF)F)7(r6(FLFR)F)25(lFRl)7(RlLL9(FL))9(4(rFLrF)FF)8(8FL)9(RrFrF)25(lFRlF)9(4FRll)7(Rl5(lFR)R)5(F7(FlRFl)F)6(LrFFrlFr)

開始3.5時間時点（29612229点）

コマンドをランダム生成するときのパラメタをいろいろ変えて試していると、繰り返しはネストさせずに、1階層だけが一番良い結果になることがわかった。

頑張って任意階層ネストを実装していたのは一体…。

この時点の出力はこんな感じ（seed=0 276643点）。シンプルな形式になりました。

50(FFr3FLr)38(FRFLr)33(FFLFrr)22(rFrl4Fl)25(r3FLrF)38(LrRlF)38(FrllF)49(llFR)39(FLFRl)35(FlFRl)32(lFrrRF)35(FFlrr)36(lLrFR)42(RlrF)38(rFRFL)36(rrFLF)26(FFLFFrR)13(RFLllRRFLl5F)28(rFFRlFL)21(rFRRFrRrF)3(LF)24(RFlLr3F)16(RFRr3FRFFLL)54(rF)RFLFLFR5FLFR2FRFLFRFRFL2F

開始5時間時点（43527432点）

いろいろと最適化

• コマンドの生成では n(XXXXX) の形を生成してからシミュレーションしてたけど、n回の繰り返した場合だけしか調べないのはもったいない。 XXXXX 部分だけ生成して、繰返し回数は1〜99まで全部試すようにした
  • 繰り返しのシミュレーションの途中で、一度来た場所に戻ってきたらその時点で打ち切る
• 高速化のため、毎回コマンド生成するのではなく、最初に10000個くらいコマンドを生成しておいて使い回す

この時点の出力はこんな感じ（seed=0 442878点）。

72(Rl4FLrF)69(lFFRlFRlF)85(FlrFRll)48(R3lrFF)56(FlLr3FR)97(RlFLF)51(lFRlFLFR)44(3RrFrF)19(FrFlrRl)11(3FRll)23(rr5Fl)41(lFL3FR)

開始6時間時点（失敗）

これまでは乱択greedyなので、当然の拡張としてビームサーチにしてみた、が、遅くなるばかりで弱い…。実装頑張ったのに…

開始7.5時間時点（49205425点）

最初に手でコマンドを作って試してみてたときの事を思い出すと、10000個コマンドを生成してシミュレーションしてるけど、ほとんどのコマンドはゴミのような動きしか出来ず全然役に立っておらず、 採用されうるコマンドは偏っているのでは 、という仮説を立てた。 強そうなコマンドだけ候補として生成できれば、実質の探索速度を向上できる。

そこで、もう1つ次の仮説を立てた。

いくつかの盤面で広く動き回れるようなコマンドは、他の盤面でも有用な可能性が高い

ということで、配布されている seed=0〜9 の10個の盤面を使って、コマンドを生成・選別した。

• ランダムにコマンドを5万個生成する
• 10個の盤面それぞれで、 N*N 通りの各位置からスタートしてシミュレーションする。訪問できたマス数の合計を評価値とする
  • 各スタート位置について4方向それぞれでやりたかったけど、ちょっと遅すぎたのでランダムな1方向だけでやった
• 評価値の高いほうから1万個を採用する。それらのコマンドを解答の中に埋め込んで使用する

埋め込んでる様子は コード の18行目をご覧ください。

この時点の出力はこんな感じ（seed=0 472098点）。

72(Rl4FLrF)96(rFr3lFL)78(lFLrrFRl)57(FLrFR)95(lFLrrFRl)70(FRlFRlFL)28(Frr5FL)30(FLFRrFLr)22(LrFFrFF)17(rFRFlFlr)

開始8時間=コンテスト終了時点（58758892点）

各コマンドについて繰返し回数は1〜99で試してたけど、もっと増やした方がよかった。999回まで試すようにするとスコアが跳ね上がった。数百箇所移動しないといけないのだからそりゃそうだ。

この時点の出力はこんな感じ（seed=0 555956点）。

226(FLrrFRll)39(FRlFl4F)87(FLrrFRll)55(LFrr4F)46(FLrFlrR)85(lFLrrFR)33(FFlrFRll)

感想

本選らしく、最初はどうやれば良いかわからないところ、コンテスト中の間じゅうどんどんスコアの天井が上がっていって「そこまで縮むのか」となり続けるのが面白かったです。

あとから振り返ると8時間中3時間くらいは無駄な実装に費やしていたことになるけど、やってみないとわからない部分が大きかったから何ともなあ。

ただ、最初から任意階層ネストのコマンドを作ろうとしてたのは良くなかったようには思う。まずはシンプルに始めて、良さそうな方向を見極めつつ肉付けしていくのが理想。

AHC（β）で赤（仮）になるまでにやったこと

画像は AtCoder Marathon Rating History より

AHC 001〜005 の5回連続で1桁順位を取ってレーティング（β）が2800を超えました。

各コンテストでどういったことを考えて方針を定めていったのかを書きます。

AHC001 5位（長期）

焼きなませるので焼きなます。

賢く構築するみたいなのがあるかもしれないけど、どっちにしろ最後には焼きなますし、それに勝てるような構築パターンがあるともあまり思えない。

焼きなまし、汎用的なメタヒューリスティクスとして強すぎて、よほど近傍の計算が重くて数千回しかイテレーション回せないとかじゃない限りとりあえず選んじゃう。

長方形の数も少なくてたくさんイテレーション回るから、変に自分で賢く考えようとするよりは計算パワーに任せた方が良い。計算パワーが正しい方向に向かうようにすることを考えていく。

焼きなましではできるだけ小さい変化の（評価関数がなだらかになる）近傍を取るというのが基本なのだけど、この問題で「ひとつの長方形を選んで、辺の位置を1ずらす」をやってもほとんど良い方向の遷移にならないのは、ビジュアライザを見てイメージすればわかる。 ひとつの長方形を縮めて空いたスペースに他の長方形を広げる、といった事をやりたい、のでそれを実装する。

ルールベースで「L字型に接している部分を…」みたいにすることもできるかもしれないが、それだと実装が大変なことになりそうなので「一部を破壊して再構築」の方針でやる。こういう近傍はTCO20 Finalでもやった。

壊すフェーズの後の広げるフェーズはgreedyにやりたいが、どういう方針で置くのが妥当かというと… 基本良い解では長方形がぎゅうぎゅうになるので、ひとつずつ長方形を取って、縦か横にできるだけ広げる、とする。 ただし多様性も確保するため、常にできるだけ広げるのではなく、一定確率でランダムな位置までしか広げない、とする。

長方形を後から縮めるのは簡単にできるので、スコア関数をいじって目的の面積以上の場合は目的面積ちょうどと同じ評価とした。これもこの近傍の妥当性に寄与している。

AHC002 3位（短期）

とにかく詰まないようにできるだけ盤面全体を回れるようにすることが一番大切。そうすればスコアも勝手についてくる。

適当に経路を取って一部を破壊してつなぎ直し、というのが典型的な考え方としてまず見えるが、この問題の制約の下でつなぎ直して経路を育てていくのがどれくらいできるものなのか、やってみないとわからない。

実装めんどいなーと思って、まずはgreedyに伸ばしていくのを書いてしまった。各方向に1歩進んだ後、モンテカルロ的にランダムウォークして最大何歩まででいけるかを求めて、それが最大な方向に動く。 そうすれば即詰みは回避できる。

しかし試してみたらかなり弱い。ビジュアライザを見ると盤面全体を大局的に見れてないから中期的に詰んでしまってるのだと思い、盤面の上の方を優先するとか開始位置に近い所を優先するとかいろいろやったけどだめ（こういう評価の方法も典型感はある）。

ここまでで1時間くらいで、時間的にもこれ以上引っ張ると他の方針が実装間に合わなくなるのでこの辺で転換して、観念して最初の破壊・つなぎ直し遷移を実装した。したら強かった。

遷移は、ランダムウォークして切ったところまでたどり着けたら候補とする、だったけどもう少し工夫の余地はあったっぽい。 たぶん多くのケースで元々の経路と同じになっちゃってるし。

AHC003 9位（長期）

インタラクティブ問題が多腕バンディット問題っぽくなるのはよくあることで。

通った経路の情報をフィードバックしつつ、未知の辺を使って情報を集めていく感じにしかならんなあとなった。

• 未知の辺を使いやすくなるように序盤は辺を使った回数に応じたボーナスを付ける
• フィードバックの計算を逐次更新ではなくて頻繁に履歴の情報を使って最初からやり直す
  • これは改善するのが非自明だけどやってみると良い結果になった
• 隣接する辺に情報を伝播させるようスムージングする

といったアドホックな調整に終始する感じだった。

あまり時間がなかったという事情もあるが、もっとデータサイエンス力があれば、モデルを作ってそのパラメタを最適化…みたいなしっかりした方針でやれたのだろう。

AHC004 7位（短期）

すべての基本は貪欲なので、わかりやすい貪欲を考えると…とりあえず縦に揃えるのを無視して横1行ずつ貪欲に揃えていけばどんな悪くても50%は超えるだろう。60%強はいくのでは？　と見積もった。

ただ完全解が達成できるものかはよくわからず、最初は完全解を出せるかもしれない方針で行ってみる。

各文字列を盤面内に撒いて、その位置を変更すると言う遷移で焼きなまし。各セルの文字の分布がひとつに集中している方が良い。

そんなに筋の良い解法では無さそう感はあったけど、計算パワーを信じてみた。が全くダメだった。 「各セルの文字の分布がひとつに集中している」の評価も難しくて、単純にやるとそのセルを使う文字列が1つだけしか存在しなくて1/1で完全に集中してるとみなされる、というケースが最強になってしまう

6時間中1.5時間くらい経ったので、完全解は諦めて1行ずつ貪欲の方向に移行する。

計算時間には余裕があるので貪欲というかビームサーチ。文字列ひとつ使うのを1ステップにすると、文字列をひとつ置いたときに盤面がどこまで埋まっているかが統一されないのをどう評価するかとかいろいろ大変なので、1行分を作るというのを1ステップとした。1行分作る中にランダム性を持たせて多様性を出す。

縦側を完全に捨てているのをなんとかしたいなと思い、縦1列分だけ先に作ってその後横を1行ずつやるようにしたらけっこう上がった。1列じゃなくて2列にしたらさらに良かったのでそれで。 横を作るときは先頭が固定されていてもそこまでスコアに影響はなく、縦で稼げてる分有利になるということでしょう。

文字列を先頭2文字で分類して保持したことがけっこう高速化に効いてそうだった。

完全解解法は、短期の時間の中でやるのは自分には無理っぽい…。 短期AHCは企業コン予選を想定してtop10に入れる確率最大化を目指しているので、まあ良いでしょう。

AHC005 8位（短期）

全マスを使った経路と捉えると難しいが、交差点間を移動する問題と考えると何も犠牲にすることなく問題空間が大幅に小さくなる。 そして交差点をいくつか選んだらTSPすればよい。

重要な点を抽出してTSPするというのはまあ典型ではある。この問題は短期にしては実装が重かったが…。

使う交差点の集合というシンプルな情報で解を表現できるので、これをちょっといじってスコアを再計算することで山登りできる。

思ったよりもこの交差点の選択でのスコアの変化が大きく、TSP部分は最近傍法だけで済ませる形にした。最後だけちょっと2-optをかける。

実行のたびのブレが大きい感じだったので多スタートをした。ビジュアライザで眺めてみても、よい局所解同士が遠いところにありそうだし。

最後のほうで、交差点ベースじゃなくて辺ベースで情報を持った方が実装楽だったかなと思った（書き直す時間はもうなかった）けど、スコア的にもその方が良かったみたい。 たしかに辿るべきは交差点ではなくて辺だからか。

[0,n)の整数の集合を管理する定数倍が軽いデータ構造

しばしばマラソン（ヒューリスティック）コンテストで使うやつです。 値の追加・削除・存在確認が、最悪時間計算量が定数倍の軽い O(1)、 空間計算量が O(n) でできます。 入っている値を他の値で置き換えるとか、入っている値からランダムに1つ返すとかも簡単にできます。

仕組みとしては単純で、集合に入っている値を保持する que と、 [0,n) の各整数が que の何番目に入っているかを保持する pos の2つを操作します（queと言いつつキューではない）。

エラー処理は入れてないので必要に応じて。

struct IndexSet {

  vector<int> que;
  vector<int> pos;

  IndexSet(int n) : pos(n, -1) {}

  void add(int v) {
    pos[v] = que.size();
    que.push_back(v);
  }

  void remove(int v) {
    int p = pos[v];
    int b = que.back();
    que[p] = b;
    que.pop_back();
    pos[b] = p;
    pos[v] = -1;
  }

  bool contains(int v) const {
    return pos[v] != -1;
  }

  int size() const {
    return que.size();
  }
};

AtCoder（ヒューリスティック）で何らかの色になれませんでした

これは 色変記事 Advent Calendar 2020 19日目の記事です。

色変できませんでした

第17回あーだーこーだー にて 「（ヒューリスティックの）ratedコンテストは年内にやります！」 という発言がなされたのを見て色変記事アドベントカレンダーに登録しましたが、色を付けることはできませんでした。

原因はratedコンテストが開催されなかったことだと思います。 来年こそは色が付くよう精進していきたいです。

いかがでしたか

いかがでしたか？　2021年のヒューリスティック系コンテストにご期待ください！

おまけ

これだけで終わるのはさすがにアレなのでアルゴリズムのレーティンググラフを貼ります。

2884->2464

この勢いで年内に黄色になって見事色変、ということも想像していましたが、こちらも達成できませんでした。

ここ1年半でhighestから400以上レーティングを落としているわけですが、ここまで落としている人はそんなにいない（黄以上だと10人くらい？）のではないでしょうか。理由を考察してみます。

• 全体レベルが上がっている
  • といっても同じくらい落ちている人が多いわけではないので…
• 練習不足
  • 練習の量・質はとくに前から変わっていないと思います
• 老化
  • 実装力や考察の深さは体感で変わっていない（実際マラソンは別に弱くなってない）と思いますが、考察の速さは落ちている気がしています
• 出題傾向の変化（writerの代替わり）
  • これはあるかも？　定量的に測れるものはなにも持ってませんが
  • 以前はアドホックに分類されていたが典型化が進んで高速処理が要求されるようになったという問題が出てきている？

こうしてみると、できるだけ考察をせずに済む領域を増やすことが大事そうですね。

このようにガンガンレーティング落ち続けている中ではありますが、まだ過去問のうち橙は1/3、赤に至っては3%しか埋まっておらず伸びしろは大きいと思うので、赤に戻れることを目指して精進していきたいです。

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時間コンテストやろうとすると時差が困ったねということに。

これは無理みたいな感じ

色々協議されましたが、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%。やっと形になってきた

ここがスタートライン

• 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位！

記念撮影

• 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
  • 終了。blackmathさんとPsyhoさんのインタビュー 見る

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

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

#tco20 seed=6 pic.twitter.com/LSssDEA2Yd

— tomerun (@tomerun) 2020年11月19日

感想

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

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

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

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

テスト結果の表

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

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

*2:優勝賞金1万ドル