Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2017-12-16

[] 北大日立新概念マラソンでやった高速化色々 23:59 はてなブックマーク -  北大日立新概念マラソンでやった高速化色々 - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 16日目の記事です。


北大日立新概念マラソン、1回目も2回目も、Simulated Annealingの良い近傍を適用できた人が上位になったという結果でした。

僕はこの手の良い近傍を見つけるという問題があまり得意でなく、かわりにナイーブな方法を頑張って高速化して対抗しようとしてしまう悪い癖があり、いろいろな高速化をやりました。その内容について、多少一般化した形にしながら書いていきます。

なお別に高速化のプロではないので、CPUのパイプラインを埋める…とか先のキャッシュラインをプリフェッチ…とかの話はしません(できません)。アルゴリズムのレイヤ中心です。


動的メモリ確保しない(影響度:☆☆☆☆☆)

とにかく動的なメモリ確保は取り除きます。

たとえば、小さな規模のBFSを何回もやるというシチュエーションはよく現れます(今回では、第2回で1ノードを取り除いたとき残った同じ番号のノードが連結かどうかを判定するのに使いました)。

void bfs(int pos) {
    vector<int> que = {pos}
    for (int i = 0; i < que.size(); i++) {
        // queにpush_backしたり
    }
}

毎回vectorを作るのが遅いので、十分なサイズのバッファをはじめに確保しておき、そこを使い回します。

int bfs_buf[2048];
void bfs(int pos) {
    int que_size = 1;
    bfs_buf[0] = pos;
    for (int i = 0; i < que_size; i++) {
        // bfs_buf[que_size++] = next_pos; とかでキューに追加
    }
}

「十分なサイズ」がとても大きくて全テストケースでその量のメモリを確保するのが嫌な場合は、グローバル(または関数スコープのstatic)なvectorにしておいて、毎回clearして使うのも可。


除算・剰余算を取り除く(影響度:☆☆☆☆☆)

除算・剰余算は遅いのでできる限り取り除きます。


その1:焼きなましの受理判定のときに発生する温度での除算は逆数の乗算にする

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff / temperature);
}

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff * temperature_inv);
}

その2:N点の中から動かす位置を決めるときは、乱数に対してNでmod取るののかわりに、順番に選んでいくようにする

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = rnd.next_int() % N;
        // selected_pos を動かしたりする
    }
}

void simulated_annealing() {
    int selected_pos = 0;
    for (int turn = 0; ;turn++) {
        selected_pos++;
        if (selected_pos == N) selected_pos = 0;
        // selected_pos を動かしたりする
    }
}

または、候補になる位置をvectorに入れておき、要素を重複して入れることでそのvectorのサイズを2のべき乗にする。

選択される位置に偏りはできてしまうし、メモリアクセスの局所性は悪くなるものの、これで速くなって結果が良くなることもある

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = cand_pos_list[rnd.next_int() & (cand_pos_list.size() - 1)];
        // selected_pos を動かしたりする
    }
}

スコア差分計算のために現在の値を保持(影響度:☆☆☆☆)

第1回では、ランダムな2点を交換するという近傍を採用しました。

このとき、スコア変化を調べるため「交換後に得られるスコア - 交換前のスコア」を計算する必要があります。

交換前のスコアは何度も同じ値にアクセスするため、事前に計算して保持しておいた方がよいです。

int calc_score_diff(int pos1, int new_val) {
    int ret = 0;
    for (int i = 0; i < 8; ++i) {
        ret -= graph[node[pos1]][node[pos1 + DIFF_POS[i]]];
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

int calc_score_diff(int pos1, int new_val) {
    int ret = -pos_score[pos1];
    for (int i = 0; i < 8; ++i) {
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

ビット並列化(影響度:☆☆☆☆)

1bitの情報はできるだけbitset的データ構造で持って、64bit分(またはSIMD使って128bit, 256bit分)まとめて処理できるようにします。

たとえば第2回では、元のグラフGでノード間にエッジがあるかどうかと、現在のキンググラフに埋め込んだ盤面上でノード間にエッジがあるかどうかをどちらも(オレオレ)bitsetで保持して、スコア変化を V/64 回のループで計算できるようにしました。

https://beta.atcoder.jp/contests/hokudai-hitachi2017-2/submissions/1867989 の823行目あたり


メモリサイズを減らす(影響度:☆☆☆)

メモリアクセスは遅いです。

プログラミングにあまり慣れていなかった頃、「exp関数遅いし、細かく離散化してテーブルに入れておけばアクセス1回で値を引けて速くなるんじゃないの」と思ってやってみて、逆に遅くなったという経験をしたことがある人はそこそこいるんじゃないでしょうか(僕はあります)。

できるだけ使っているメモリがキャッシュに乗るよう、でかい配列はデータ型をコンパクトにします。

第1回では、元グラフでの辺の重みを保持する500*500の配列が大きかったので、はじめint32_tで持っていたのをuint8_tにしました。これだけで1割くらい速くなった記憶があります。

ただし何でも詰め込めば良いというわけでもなく、値が最大で15なのをいいことに1要素4bitで詰め込もうとしたら、今度は大幅に遅くなりました。さすがに自前でマスクしてシフトして、という処理があちこちに入るとそのオーバーヘッドの方が重かったようです。

状況によっては、頑張って詰めた方が良い場合もあるとは思います。



座標を1次元に潰す(影響度:☆☆☆)

普通はフィールドのデータは field[x][y] で持つと思いますが、座標を1次元に潰して field[(x << 6) | y] で扱うと速くなりました。

座標をxy別々に扱わずに済んで、いろいろ簡略化されるからだと思います。

おなじみの

int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int DN[8] = {-65, -64, -63, -1, 1, 63, 64, 65};

になります。


番兵で条件判定を取り除く(影響度:☆☆)

盤面の端をはみ出たかの条件をif文で書く回数を減らせるよう、盤面を64*64分確保して、実際のデータはxyそれぞれ1ずらした位置に置き、外周1周分を番兵として使えるようにしました。


焼きなまし受理判定の枝刈り(影響度:☆☆)

exp関数は遅いので、スコア差分が圧倒的に悪くてほぼ受理されなそうなら、exp関数を呼ばずに棄却します。

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    double v = score_diff * temperature_inv;
    if (v < -6) return false; // 枝刈り
    return rnd.next_double() <= exp(v);
}

ループアンローリング(影響度:☆☆)

回数が固定されているループで、呼ばれる回数が多い箇所はループ展開します。

for (int i = 0; i < 8; i++) {
    int next_pos = pos + DN[i];
    // next_pos を使って何か
}

int next_pos = pos + DN[0];
// next_pos を使って何か
next_pos = pos + DN[1];
// next_pos を使って何か
(中略)
next_pos = pos + DN[7];
// next_pos を使って何か
}

また、必ず1回以上実行されることがわかっているループはwhileではなくdo-whileにする、とかもこれに含めて良いかと。

やり過ぎると命令メモリが増えることによりアクセス局所性が悪くなって遅くなっちゃいますが。


BFSで来た方向に戻る移動をしない(影響度:☆)

上でも書きましたが、第2回で同じ番号のノードの連結性の確認のためにBFSを使いました。

シンプルに書くと、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    for (int j = 0; j < 8; j++) {
        int next_pos = pos + DN[j];
        if (node[next_pos] == n && !visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
    }
}

まず、各点で隣接するそれぞれのノードが自分と同じ番号かどうかを、1bitずつ計8bitの値で持っておきます。

すると、BFS内での同じ番号のノードかどうかのチェックが削除できて、隣接位置すべてを見るループも削減されて、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    int bits = surround[pos];
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

さらに、BFSでキューにpushしたときに、自分に戻ってくる側の移動は見なくて良いはずなので、それを教えてあげると、さらに少し速くなります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i]; // queに入っている値は、上位16bitが探索する方向の候補、下位16bitが位置を表す
    int bits = pos >> 16;
    pos &= 0xFF;
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            int next_bits = surround[next_pos] - (1 << (7 - dir)); // 自分にすぐ戻る移動を抑制
            que.push_back((next_bits << 16) | next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

0〜N-1 の中から異なる2つをランダムに選ぶときのテク(影響度:☆)

ナイーブにやると次のようになります。

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % N;
while (v2 == v1) {
    v2 = rnd.next_int() % N;
}

よく知られているテクとして、次のようにすれば乱数呼び出しが確実に2回で済みます。

(ただし分岐予測は効きにくくなるので速くなるかどうかは場合によるかも…)

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % (N - 1);
if (v2 >= v1) v2++;

2017-12-02

[] マラソンマッチは役に立つ 18:29 はてなブックマーク -  マラソンマッチは役に立つ - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 2日目の記事です。

近年のAdvent Calendar執筆ハードル上昇に対抗するため簡単な記事にします。

皆さんご存じのように競技プログラミングは役に立ちませんが、マラソンマッチやってるとたまに役に立つので役に立ったことを書きます。


人間を意識したコーディング

短時間コンテストでは自分でクラス作ったりすることはそんなに無いかもしれません。一方、マラソン系コンテストで実装が重めのやつは1000行超える規模になって、ある程度は関心事の分離ができた構造になっていないと扱いづらく、なかなか死ねます。

また、整理されたコードを見るのは気分的にも良い。何度も同じコードを見ることになるのでこれは重要です。


計算量の感覚

短時間コンテストだと最悪計算量しか気にしませんが、実データで最悪ケースが来ることはそうそう無く「実際はどんなデータなのか?」を計測・分析して、実用上速いデータ構造・アルゴリズムを使うことになります。

プロコン以外のプログラミングでもこういうのが大事なところは多いかと。


ビジュアライザ

解答やテストデータの様子を確認するためにHTML+JavaScriptでツールを作ることはよくやります。場合によってはちょっとしたwebアプリ立てることも。


高速化

高速化やったところで最終的なスコアにほとんど意味ない場合も多いですが、わかっていてもついやりたくなっちゃうんだよね〜、ということを身をもって実感できます。

また、いざ高速化やるぞと取り組むときにはプロファイラ使ったりアセンブラ眺めたりして、これはこれで相当実用的な経験になります。


パラメタ最適化

マラソンマッチの終盤には、最適な答えを出すパラメタの探索をやります。これは機械学習のモデル作成でも課題となってくるところであり、ノウハウ知っておくのは良さそうです。

(僕はグリッドサーチしかやったことないですが…)

また、計算の実行にクラウド使うことも多いので「クラウド環境の活用経験あります!」と言えるようにもなりますね。


英語を利用する機会

英語に慣れなければという気持ちはあるものの、でも慣れていないので英語を実用で使う機会が得づらい、というスタートアップ問題がありますが、forumに書き込むのは自由なので貴重な機会になります。

他の書き込みを見ていると「文法無茶苦茶じゃねえか!」みたいな投稿がわりとあって勇気づけられることも。


まとめ

マラソンマッチをやろう!

2016-12-01

[] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク -  AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calender 2016 1日目の記事です。


先日、Twitterでこのような発言を見かけました。

AtCoderの過去問が今の基準だと何点になるのか知りたい

https://twitter.com/hogeover30/status/785894012716654593

やってみました。


一応、背景を書いておきます。

以前のAtCoder Regular Contest(以下ARC)・AtCoder Beginner Contest(以下ABC)では、基本的にそれぞれの問題は100点満点でした。

2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。

そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。


AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。


結果はこちらにあります。

https://tomerun.github.io/atcoder_statistics/estimated_scores.html


  • どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
    • 逆に、新しめのものはそこそこよさげに見える
    • こういった状況は他の機械学習案件でもありそうなんだけれど、うまく扱う方法あるんだろうか
  • ABCのD問題にもけっこう難しいのが紛れている
    • あまり出てないので知らなかった
  • 難易度順が逆転してしまっているところはあんまりない
  • これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
  • 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
    • おおまかには、強い人がコンテストに出ていて解けなかった場合に推定スコアが高くなるという仕組みなので、あまり強い人が出ていなかった場合、推定スコアが高くなりようがない


実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。

  • 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
    • 対象ユーザーは236人でした
  • 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
  • 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
    • 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い


せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。


Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに!

2015-12-01

[]すごいサブミット 00:42 はてなブックマーク - すごいサブミット - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calendar 2015の1日目の記事です。


Advent Calendarの基本に返って、すぐ書ける記事にします。

これまでにコンテストで見た、印象に残ったサブミットを列挙します。

他人のコードを勝手に紹介することをお許しください。


SRM436

https://community.topcoder.com/stat?c=problem_solution&rm=300564&rd=13698&pm=10336&cr=10597114


想定解がFFTの問題だったのですが、インラインアセンブラで気合いで通しています。

1発ACを要求されるSRMで、36分でこのコードを書いて通すのは、当時の界隈にかなりの衝撃をもたらしました。


2010 TCO Marathon Round 2

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10989&rd=14273&cr=22696357&subnum=8


このマラソンマッチは完全なる高速化ゲーでした。

というわけでJITです。


Marathon Match 78

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=12444&rd=15570&cr=21688563&subnum=13 (重いので注意)


圧勝した人のコードです。

皆が焼きなます中、Pythonで遷移パターンを列挙して埋め込んでDPしたみたいです。


NSA Marathon Match Event 1

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10676&rd=14176&cr=7462740&subnum=3


これはコードよりも 順位表 を見てもらった方が良くて、訳が分からない点差が付いています。

これは暗号解読の問題だったのですが、どうも一人だけまともに解読できたらしいです。

コードで何をやっているか読めた方は来年のAdvent Calendarのネタにでもすると良いのではないでしょうか。ぜひしてください。


AtCoder Regular Contest #030

http://arc030.contest.atcoder.jp/submissions/286413


コードを見ても何をやっているのか分からないと思いますが、見るべきは提出時間で、コンテスト開始3秒後にサブミットされてACを取っています。

サンプルから解答を推測するプログラム、なのでしょうか??


お誕生日コンテスト

http://birthday0410.contest.atcoder.jp/submissions/128080

http://birthday0410.contest.atcoder.jp/submissions/127943


これも順位表を見てもらった方が良くて、WA回数が大変なことになっています。

問題の性質的に、インプット解析でがんばれてしまったのですね…。


なおこのようなひどい(褒め言葉)問題であるにもかかわらず、まともな方法で満点を得ているサブミットもあってこちらもすごい

http://birthday0410.contest.atcoder.jp/submissions/127561


おわりに

ほかにも興味深いコードがあったら教えてください!!

2014-12-01

[][] MarathonMatchトレーニングのための過去問レビュー 01:01 はてなブックマーク -  MarathonMatchトレーニングのための過去問レビュー - TopCoderの学習のお時間


これは Competitive Programming Advent Calendar 2014 1日目の記事です。


MarathonMatchで成績を上げていくには、他のスポーツと同じく実践が不可欠だと思います。

しかし、最近は通常の(=TCO予選みたいな組み合わせ最適化を問う)MarathonMatchの開催回数が少ないのでなかなかその機会が得られません。

信じられないかもしれませんが、2008年ごろは月1回以上のペースでMarathonMatchが開催されていたんです…。


ならば過去の問題ストックを使って自主練するしかない!

ということで、過去に自分が参加したMarathonMatchについて、問題をジャンルわけしてコメントを付け、オススメ度を☆で表しています。

ジャンルわけは便宜上という側面が大きく、この方針ではないとダメ! というわけではないです。

あと、ネタバレありなので要注意。


リンク先はPracticeの問題文です。

Practiceが存在しないものがいくつかあって、それらにはリンクを張っていません。

なお、Practiceにないものも含めて過去のMarathonMatchの一覧を見るには、Match Winners のページがよさそうです。


焼きなまし


ざっくりいえば焼きなましをするんだけど、もちろん焼きなましただけではだめで、その適用形態は多彩です。

  • TCO14 Round3 CollageMaker [☆☆☆]
    • そもそも、焼きなまし(というか、逐次的改善)可能な形にできたかどうかが上位との分かれ目といった感じでした
    • 解の探索以外でちょっと面倒な要素が多いので、練習するなら他の問題の方が良いかなぁ
  • TCO13 Round3 CirclesSeparation [☆☆☆]
    • 良い近傍の取り方がとても難しい
    • 僕は本番でまともな方法を実装できずに撃沈しました
  • Marathon Match 78 FixTheFence [☆☆☆☆☆]
    • 良い近傍の取り方が難しい
    • 問題としてはシンプルなので練習によさそう
    • ところで本番1位の人の解法は焼きなましではなく他の人たちと全然違う方針でした。かっこいい
  • TCO10 Round2 CellularAutomaton [☆☆]
    • 完全に高速化ゲー。高速化の訓練としては良いかもしれませんが…
  • TCO10 Round1 Planarity [☆☆]
    • これもかなり高速化ゲーの印象(12時間しかやってないけど)
  • Marathon Match 56 EnclosingCircles [☆☆☆☆]
    • よくMarathonMatchの問題例として取り上げられる、理解しやすい問題
    • 本番の結果は意外とばらけていて、焼きなましの職人芸スキルで差がついた、という印象
  • Marathon Match 54 TilesPuzzle [☆☆☆]
    • 本番で自分が焼きなましでやったのでここに入れましたが、forumを見る限りは焼きなましてる人は少数派っぽい
    • いろいろなヒューリスティック探索ができそう

ビームサーチ


最近ビームサーチばかりやってる気がするけど、挙げてみたら思っていたより少なかった。

  • TCO14 Round1 SquareRemover [☆☆☆]
    • 高速化寄り
    • アルゴリズムにやらせると、人力で遊んだ場合より遙かに良い点数を出すのが面白かった(どうでもいい)
  • TCO13 Round2 FragileMirrors [☆☆☆☆]
    • 良い評価関数を作ることがもちろん大切なんだけど、もっと重要な要素がひとつあって、それを見つけられないと勝負にならない感じだった
    • 問題の性質をよく考える訓練になって良い
  • TCO12 Round1 BlackAndWhiteGame [☆☆]
    • 探索が可能な形をつくるのが全く自明ではなくて大変
    • 正のスコアを出すまでちょっと遠いので練習としてやるにはつらいかもしれない

マルチエージェント系


複数のユニットを動かして、協調して何かやらせる問題。

実装が難しくなることが多いです。

  • TCO13 Final GatheringResources [☆☆☆]
    • 実装ゲーに近かったと思う
    • とはいえ12時間しかやっていないのでもっと時間かけたときにどうなるかは未知数かな
  • Marathon Match 55 CoalMining [☆☆☆]
    • あまり印象に残っていない…。オーソドックスな問題だったと思います

パターン決め系


良い解では全体がどのような形になるかを見出すことが最重要になる問題たち。

後はそのパターンの中で細かく探索をしたりする。

他人の解をビジュアライザで見ると面白いことが多い。

  • TCO14 Round2 RectanglesAndHoles [☆☆☆]
    • パターンを想定するまではできても、それを実装するのが難しい問題だったと思います
  • Marathon Match 74 AntiTravelingSalesperson [☆☆☆☆]
    • 格子点にしか置けないという制約がある中でうまいパターンを作るには、適当にやってもダメでよーく考えないといけない
    • これも1位の人は違った方針でやっていてかっこよかった
  • TCO09 Round2 Gearing [☆☆☆☆]
    • 逐次的な改善が可能な形でパターン決めてあげないと良いスコアにはならない
    • 本番に自分が参加したときは、greedy的な方針で決めうちしてしまってイマイチな結果でした
  • Marathon Match 49 MegaParty [☆☆☆☆☆]
    • 問題の性質をよく考えて、全体の形を作る事が最重要。教育的です
    • 本番に自分が参加したときは、何も考えず単純に焼きなましただけだったのでイマイチな結果でした

不完全情報・確率評価系


初めに情報が全部は与えられないタイプの問題。結果の期待値を評価しながら次の一手を選んでいくプログラムになる。

個人的にはこの形式はけっこう好き。

  • TCO12 Final PolygonEstimation [☆☆☆]
    • 本番で方針が大きく2つに分かれて結果も拮抗していたのが面白かった
    • なかなか実装Hardです
  • TCO11 Round1 ImageScanner [☆☆☆]
    • colunさんがガチ確率評価をやって圧勝したことで有名(?)な回
    • 問題テーマとしては、情報科学的な観点でもとても面白いものではある
    • 外部のデータファイルを処理しないといけないので少し取っつきづらいかな?
  • TCO10 Final CollapsingMaze [☆☆]
    • 確率的に即0点になってしまうという大味な問題。どこまで攻めるかの調整が肝
    • Practiceではテストケース数が限られるから運ゲー要素が強くなってしまいそう
  • Marathon Match 65 CuttingFigures [☆☆☆☆☆]
    • ある手を指したときの期待値をしっかり評価することが求められる
    • ルールもシンプルだし、良い練習になりそうな問題です
  • Marathon Match 53 TilesMatching [☆☆☆☆]
    • とにかく良い評価関数を作れるか勝負
    • これもう一回やりたいのだけどなんでPracticeにないんだ…
  • TCO09 Round1 ReliefMap [☆☆☆☆]
    • 取れる選択肢の自由度が非常に高くて、次に何をするかをどうやって決めたら良いか難しい
    • 実装も大変で、Round1(当時ルール)にしておくにはもったいない良問でした

その他・ノンジャンル・総合力


  • TCO11 Round2 QualityPolygons [☆☆☆☆☆]
    • いろいろな方針が考えられて、まさに総合力といった感じ
    • がっつり練習したかったら、ここに挙げた中で一番オススメです
  • TCO10 Round3 SubgraphIsomorphism [☆☆☆☆]
    • ヒューリスティック枝刈り探索勝負。もう一度やってみたいがこれもPracticeにないの残念
  • TCO09 Round3 BounceOff [☆☆☆☆]
    • まず、ある程度まともに動作する解を作れるかどうかが難しくて、Round3(当時ルール)に進んだ人たちでもかなり苦労していた
    • この問題は特に、SRM的な発想では全く方針決められない気がします。その意味では良い例題
    • ビジュアライザが楽しいです
  • Marathon Match 48 WatermarkSequence [☆☆☆☆]
    • Marathon史上最良問との呼び声もある問題。僕が初めてMarathonに参加した回でもある
    • めちゃめちゃ面白いけどだいぶ難しいので、練習にやってみるなら覚悟して

特殊・非推奨


ちょっと特殊なところがあってあまりお勧めできない問題たち。

  • TCO11 Round3 StringCompression [☆]
    • あまり最適化という感じではなくてつらかった
  • NSA Marathon Event 3 BrokenClayTile [☆]
    • テストケース生成リバースエンジニアリングゲーでつらかった
  • Marathon Match 66 DigitsPattern [☆]
    • 最良解を出せてしまう人大量発生でつらかった
  • Marathon Match 58 IsolatedPrimes [☆]
    • 数学ゲーかつ埋め込みのためのローカル計算でつらかった

やったことないやつら


問題文を読んだだけでコードを書いたことがない回もたくさん残っていました。それらの中で面白そうなのを列挙します。

自分が練習会をするとしたら、この中から選ぶことになります。

(この記事の公開と同時に練習会を始めようかとも思っていましたが、CodeVSKaggleが出てきたのでまたいずれ)