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万ドル

2019-06-27

■ [ICFPC] ICFP Programming Contest 2019 02:13

https://icfpcontest2019.github.io/

https://github.com/tomerun/icfpc2019

一人で参加した。一人でフル参加したのは何気に初めて。

• 2009: 途中で萎えた（同時に開催されてたマラソンマッチに移行した）
• 2010: 休み取ってなくて2日しか参加できず
• 2011: 問題読んで本格的な関数型の知識を要求されてそうで怖じ気づいた（同時に開催されてたマラソンマッチに移行した）
• 2012-2018: チームで参加

1日目

会社で問題を読んで、帰宅して環境整備から取りかかった。

最低限の目標として、コンテストの順位は二の次で、快適に解答を実行できる環境を整備することに置いていたので、ライトニングは無視です。

AWS Batchで並列実行できるようにすることをもくろむ。そのためにDockerイメージを作る。

Crystalで書くつもりだったのでCrystal公式イメージをベースに作った。

実際の動作はソースコードに同梱したシェルスクリプトを実行して行わせるので、Dockerでやることはs3からソースコードとテストデータを落としてきて、ソースコードを解凍して中にあるスクリプトをたたくだけ。パラメタ的なのは環境変数で渡す。

なのでイメージに必要なのはawscli（とそのためのPython）くらい。

けど入れてみたらイメージサイズが700MBくらいになってECRへのアップロードがメッチャ時間掛かっていたので一旦停止して、Alpine Linuxのイメージから自分で作ることにした。

だがCrystalがすんなり動かず、依存パッケージを自分で色々入れないといけないらしい。

https://github.com/sam0x17/crystal-alpine/blob/master/Dockerfile

これを参考にしたけど、最新より一つ古いバージョンの0.28.0で試したものっぽいし、結局これらインストールしてたらイメージサイズも別に小さくなってないしで、結局最初の方針通りcrystal公式イメージから作った。だいぶ時間ロス…

あと結果を入れるためのRDSも立ち上げて、テーブル定義しておく。

ややこしいエンティティ間の関連があるわけじゃないし保守性の制約も緩いから、RDSじゃなくてDynamoDBのほうが適切そうな気もするけど、NoSQL本格的に使ったことないのでとりあえずRDBで。

2日目

イメージの準備ができたのでAWS Batchでジョブを定義していく。

初見では概念が色々ややこしいけど、クラスメソッドさんのブログを熟読してとりあえず動くレベルで設定をした。

昼過ぎぐらいにはジョブを投げて並列で実行されることを確認できた。初回はEC2インスタンス立ち上げからなのでジョブの実行が始まるまで数分かかることを知った。

入力パーサを書き始める。ソルバで使うことを考えて情報を色々リッチに持たせていたらだいぶ時間かかってしまった。

各テストケースを画像化しようかと思ったけど、Crystalに良い感じの画像ライブラリがなさそうだったのであきらめた。

このあたりで開始から24時間が経過して、仕様が出そろった。けど最後に出てきた追加仕様は弱小一人チームでは手が足りなすぎて無視するしかないやつで、はい…という気持ちになった。

ライトニングの順位表凍結が解除されたので、とりあえず順位表情報を10分おきに取得しておく。これはLambdaを使って定期実行した。コンテスト中には何も使わなかったけど、グラフ化でもしてみるつもり。

ひとまず正の得点を出すべく、単純に直近のまだ塗っていないところを塗りに行くグリーディーソルバを書いていく。

3日目

最初は単純なソルバからと思っていたのと相反して、Extension of the Manipulator使ったり、直近3歩だけは全探索して一番塗れるパターンを探したり、などいろいろやり始めてしまい、動かせるものになったのはこの日の21時くらいだった。

これで実行環境に投げて実行されている間に、DBからベストな結果を取ってきて提出用のzipにするスクリプトを書き、出てきた結果を提出してみた。

するとちゃんと点数が出て、しかも想像していたよりだいぶスコアが高く、一人で盛り上がった。

テンション上がってきて、Fast Wheels使うのとか、ブースターが近くにあったら優先的に取りに行くのとか、小さな非連結成分を塗り残していたら優先的に塗りに行くのとか、5時近くまで実装やってしまった。

Extension of the ManipulatorやFast Wheelsは取ったら即使うように決め打ち。

Manipulatorの追加位置は、本体から遠い箇所が選ばれやすいようなランダムで。

4日目

引き続きテンション上がっているので9時過ぎぐらいから活動開始。

ビジュアライザで見ると明らかに塗り残しがあるまま先に進んじゃっているのが見られるので、これをなんとかしたいと思う。

直近のまだ塗っていない所を探すときに、現在位置からの距離が直近な場所ではなく、ボットに「ベース位置」みたいなものを決めて、そこからの距離が近い場所を塗りに行くようにした。

あまりにも遠いところになってしまう場合は、現在位置をベース位置としておき直す。

本当はもっと大局的に、盤面をざっくりとグラフ構造としてみてTSPで経路最適化、とかをやりたかったが、シンプルに実装する道筋が見えず、アドホックな改善を積み重ねる形になってしまった（初日の環境整備に使った時間がなければ…）。

Fast Wheelを使ったときの探索がバグりまくって苦しかった。スピードアップしてると細い道から脱出できずに行動できないことがあるとか、最初想像できていなかった…。

自前チェッカのようなものは準備していないので、公式のビジュアライザでちまちま動かすのつらい。

残り5時間くらいで、まだDrill,Teleport,Cloneを使えていない状況で、それらを実装するか、ブースターは捨てて探索を賢くするのを頑張るか迫られた。

が、せっかくある仕様はできるだけ実装しておきたく、ブースターを実装するほうを選択した。

まずDrill。これは取ったらすぐ使うわけではなく、近い位置に塗り残しがなくて次にどこを塗るかBFSするタイミングで、Drillを使ったとした場合の探索も行い、時間が短くなるようなら使う、とした。

Drillを使うことにどれくらい効果があったかはよくわからないが、プラスの意味はあったと思う。

そしてClone。これはLambda Coinガン無視チームにとっては80ケースしか影響しないのであまり気は進まなかったが、やらないとその80ケースが壊滅的になるのは明らかなので、仕方なく実装した。

本当は分裂したBotたちを上手く協調させることをやらないといけないんだろうけど、各Bot独立にこれまでのアルゴリズムで動かしただけ。

それでも目に見えて結果は良くなったので、さすがにやって良かったという気になった。まあトップのスコアから見たら、ひどいゴミが多少マシなゴミになったくらいの変化ですが…。

Teleportは上手く使えそうに思えなく、時間もなかったので無視することになった。

終了1時間前に、最後の実行としてジョブを投げまくっていたら、インスタンスがkillされることがちょこちょこあってちょっと焦った。スポットインスタンスでやっていたので、リザーブドインスタンスの環境も急遽立ち上げ。

それでも一部ジョブの実行がなかなか始まらなくてやきもきさせられた。

これ、実行開始のレイテンシが気になるときは、Minimum vCPUを大きめの値にして常時インスタンス立ち上がっている状態にしておくものですね…（学び）。

手元で十分なバリデーションができてなくて、提出したらFailedになるのが怖いので、実行途中で何度か提出して様子を見る。無事最後まで全部validな解になっていて良かった。

感想

ちゃんと環境作れたのは大変良かった。手元でスクリプト一つ流したら勝手に実行して結果を保存してくれるのは最高だ。

これ、マラソンマッチとか他のコンテストでも役立ちそうなので使えるように整備しておこう。

今回は画面は何も作らなかったので、次回はダッシュボード画面を頑張りたい。まあ一人チームでは自己満足にしかならなそうだけど、楽しいのが重要。

ソルバーのほうは、仕様を実装するので精一杯という感じで、全く詰められた感じはしないなあ。

探索ロジックはだいぶアドホックになりすぎたきらいはあって、最初からもっと大局的に考えられれば良かったのかなあという感じ。未実装仕様が残っていることによる実装プレッシャーがあると、じっくり考えるの難しいが…。

クラウド費用は1800円くらい。ソルバ実行をガンガン動かしたのは最後だけだから、こんなもんか。

全部東京リージョンでやってたけど、計算サーバーは別に東京である必要なかった。リージョン変えたら多少節約はできる。