Hatena::Grouptopcoder

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

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

2017-10-29

[][] TCO17 Onsite 20:44 はてなブックマーク -  TCO17 Onsite - TopCoderの学習のお時間


10月20日(金)


16時の飛行機で成田から出発。空港に着いたのは2時間弱前で、サンドイッチ食べるくらいの余裕はあった

こういう話があるので今後はもっと早く行った方が良さそう http://www.afpbb.com/articles/-/3148112?cx_position=34


12時間かけてワシントンまで行き、そこから乗り継いでバッファローまで。

乗り継ぎの間は1時間40分で、入国審査のカウンターが一つしか開いていなくて、列がなかなか進まず出発時間ぎりぎりだった。空港内をリアルマラソンしてなんとか(5年前と同じ…)


飛行機内では、機内誌を読んだりiPadで本を読んだり。仕事しようかとも思ってたけど、照明落とされるのでPCを開く気になれなかった。

機内誌にスタンディングデスクの広告が2つ載っていた。流行りか…。


現地時間の17時頃にバッファロー到着。Topcoderの手配でホテルまで送ってもらう。mugurelionutさんと一緒だった。

やっぱりホテルの部屋が一人には広すぎで落ち着かない。


ホテル近くのスポーツバーで夕食。サンドイッチやハンバーガーを頼んだところ、やっぱりアメリカンサイズのが出てきてワイルドだった。


10月21日(土)


朝食はホテルのバイキング。食べ物の種類は少ない。飲み物の種類が多く、持ち帰り用のカップがあるのは良い。


この日は夜にWelcome Receptionがあるだけなので1日オフ。chokudaiさんとりんごさんはナイアガラの滝に行っていたが、僕は体を休ませたいのと英語キーボードの練習をしたいのとでホテルに残る。

持参したキーボードでAOJの軽い問題を解いたりしてた。

昼食はホテル近くのdomino's pizzaで。焼きたてのピザおいしすぎる…。


19時からWelcome Reception。会場はホテルとは別で、大学?研究所?のキャンパス。そこが今年のTCOのメインスポンサーでもある。ホテルから徒歩15分くらいで、シャトルバスも出ている。

バスがいつ来るかよくわからず、歩いて向かっているグループについて行った。


会場について参加賞をもらう。なんかノベルティ少なめだ。5年前に会った他のコンテスタントの人たちに挨拶する。

Marathon参加者の人たち、すでにデスクで各自準備を進めている。本来はコンテスト開始30分前からなんだけど、やっちゃっていいのかなあ…と思いつつ自分もやる。まあ、やることはそんなに無いのだけど。JDKが入ってなかったのでインストールしたくらい。英語版Windowsは普段使わないのでPATH通すのに手間取ったりしてた。


デスクの環境はこんな感じ。

f:id:tomerun:20171022082643j:image


MilaninさんがMM95の画像を表示していた。

f:id:tomerun:20171021201906j:image



10月22日(日)


朝は会場まで徒歩で行った。空気が気持ちいい(気温は東京と同じくらい)。

9時-19時でコンテスト。昼食として自席で食べられるサンドイッチを用意してもらえるのは大変ありがたい。

最初数分問題が開けなかったりしたけど、まあこういうのはよくあることなので慌てず待つ。

だいぶオーソドックスな問題だった。とりあえず問題を読んで、テスターのコードを読んでカスタマイズ(別プロセスではなく直接自分の解答を呼び出す・マルチスレッド化・出力に情報を追加)して、空解答を作って動かすまでが40分と、なかなか順調にいった。

10時間ではあまり難しいことできないので、基本的には近い所を取りに行くgreedy。それに評価関数の要素をいろいろ加えていく感じだった。ただ最後2時間くらいは、1位とはかなり差があったのに細かいパラメタ調整に終始することしかできず不毛だった。もうちょっと攻めるべきだった。

インタラクティブ形式でありつつ隠しパラメータがほとんど推測可能なので自分でシミュレーション可能という重要な特徴があるのだけど、それに最初気づいていなくてこの特徴を解答に取り入れることができず、残念。

やっぱり慣れないキーボードだとかなりタイピング速度が損なわれるので、次回は自分用のキーボードを持ち込もうと思った。


終了後は会場で夕食を取りつつAlgo Semifinal1を見る。

ホテルに戻ってからはTopcoderスタッフの方に連れられて2日前に行ったのと同じバーで軽く飲み。


10月23日(月)


さすがに前日は疲れたのでゆっくり目(8時半くらい)の起床。

一人で座って朝食を取っていたら、mugurelionutさんとmarek.cyganさんがやってきて、それからPaulJefferysさんも来て会話していた。途中からヨーロッパにおける政治事情の話になってまったくついていけず置物と化していた。

コンテストの問題についてとか、トピックが限定されていてなじみのあるものならまだなんとかコミュニケーション取れるのだけど…。


昼からナイアガラの滝を観に行った。会場からシャトルバスが出ており、25分ほど。

時間そんなにない&お金それなりにかかるということもあって、滝の下までは降りずに上を歩いて回っただけだけど、カナダ側は一帯が水しぶきで覆われていて、雨が降ってないのにずぶ濡れになる感じで満喫した。

f:id:tomerun:20171023145050j:image


帰りのバスの時間がわからず2時間待つ羽目になり、AlgoとMarathonの人は参加してね!と言われていたData Science Workshopには参加できなかった。


会場に戻り、UI PrototypeとDevelopmentのコンテスト風景を眺めた。みんなハッカソンガチ勢っぽい。使われているエディタが、Atom,VSCode,Sublimeなど様々に分かれていて、Developmentでは使われている言語も様々で面白かった。


10月24日(火)


翌日の飛行機が早いので、この日は早め(6時)に起床。

朝食後に会場へ。UI Design部門のコンテスト風景を眺めた。

このへんのコンテストの種類について書いておくと、こんな感じ。

  • UI Design
    • アプリケーションのコンセプトが与えられるので、画面のグラフィックデザイン案を作る。Photoshopとかワイヤフレーム作成ツールを使う、デザイナのコンテスト。
  • UI Prototype
    • アプリケーションのデザイン・ワイヤフレームを元にHTMLCSSJavaScriptを書いてそれを実現する、フロントエンド実装コンテスト。
  • Development
    • アプリケーションのテーマや使うAPIが与えられるので、何か作るハッカソン風コンテスト。

あと、TCOブロガーであるgorbunovさんがたたずんでいたのでいろいろ話した。


午後からAlgo Final。りんごさんの応援をしつつ観戦する。

その後閉会式・結果発表。ニューヨーク州の副知事が来ており、挨拶がいかにも政治家という話しぶりだった(ちなみに開会式にはバッファロー市長が来ていた)。


移動してバー的な店でclosing reception。

Nickolasさんにマラソン問題を作るときに考えていることについて聞いたり。

タコス食べたら相当おなかいっぱいになった。

f:id:tomerun:20171024195228j:image


10月25日(水)


飛行機が朝7時発なのでホテル出発が5時。眠い…

空港で軽い朝食を取って、まずはシカゴまで。

シカゴで4時間待ち。空港をうろついたりサンドイッチ食べたりだらだらしたりしていた。

その後成田まで13時間。本読もうとしたがなんかもう目が乾いてダメだった。半分寝ていた。


10月26日(木)


16時頃に到着。いったん会社に立ち寄って雑務やってから帰宅。

この日はまだ興奮してたのか6時間弱しか寝れなかったけど、次の日に13時間寝てしまってだいぶ疲れてたのだなあと。


また来年参加できるようがんばろう。もっとコミュニケーション取れるように英語も(生きていて英語使う機会がTCOしかないので、これを逃すと一生習得できない)。

2017-10-27

[] Marathon Match 95 CirclesMix 16:10 はてなブックマーク -  Marathon Match 95 CirclesMix - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959


1日目(木曜)


問題を読んだ


2日目(金曜)


テスターをカスタマイズ(いつもの)

  • マルチスレッドでのバッチテスト
  • 結果の出力を良い感じに
  • 問題パラメタを自分で指定できるようにする

3日目(土曜)


テスト画像をwikimediaからクロール

(イラストとか本のページとかの画像は弾くのだけど、基準に主観が入るので迷うのが多かった)

1000枚取ってきたけどそんなに要らなかったかな…


greedyに円を一つずつ置いていくのを実装

  • ランダムな位置・半径で円をたくさん作る
    • すでに生成したものと近すぎる円は生成されないようにする
    • 半径は徐々に小さくする
  • それぞれの円に対して、最適な色にしたときにペナルティがどれだけ減るかを評価
  • ペナルティ減少が一番大きい円を選ぶ
    • 選ばれたやつと重なるもの以外の円は保持しておいて再利用する

また、選んだ円に対して、位置と半径を動かす山登りを実装


4日目(日曜)


高速化色々、SSEも使う

円の最適な色を決めるために、円の内部のピクセルに対して中央値を取る処理が重いので、かわりに円の中心にある7*7の正方形範囲の中央値を使う、という大胆な近似を取り入れたり

最終的に、greedyフェーズでは各ターンで 10000/sqrt(N) 個の円を生成し、選ばれた円に 10000/sqrt(N) イテレーションの山登りを行った。所要時間は6,7秒くらい?


5日目(月曜)


まだまだ高速化


円を置いてしまった後に、時間いっぱい使って繰り返し山登りで改善するのを実装(高速化を頑張っていたのは、これをやる時間を作るため)

山登り対象になる円をランダムに選ぶと、評価のためにその円の上に重なっている円をすべて再描画しないといけなくなって受け入れられないほど遅そうで、そうならないよう1つめの円から順番にひとつずつ山登りした。

各ピクセルごとに、未来側に円が何枚重なっているかと色の和を覚えておけば、再描画無しで評価できる。

  • まずN枚目〜2枚目までの情報を計算して、それを使って1枚目の円を山登りする
  • 未来側の情報から2枚目の円の寄与分を取り除いて、2枚目の円を山登りする
  • 以下同様

この問題は、とにかくいかに逐次改善可能な形に持って行くかが勝負だと思ったので、ここが一番の重要ポイントだった


6日目(火曜)


調整色々


前日実装したものが山登りになっていなかった(良い解になっても状態を更新しておらず、初期状態の近傍しか調べてなかった)という致命的なバグを修正


7日目(水曜)


パラメタ調整やる、が、ほとんど変わらず

AWSで36coreマシン借りて35スレッドでテストを実行したら、めちゃくちゃ遅くなってまともにテストできなかった。16スレッドに減らすと普通だったので、コア数もったいないがそれで。

原因は追ってないけど、テスターで画像を読んでるからだろうか?


やらなかったこと


  • はじめは画像を縮小して処理することで高速化
    • やったけど良くならなかった
  • 画像から円をパターン検出
    • seed=1を見るとそういうことを考えてしまいたくなるが、実装も実行もコスト高過ぎそうでやめた

結果


1位とだいぶ差があった。

最終日にしか提出しなかったのは、戦略のつもりではなくて、単に何度も提出するのがめんどいからです

2017-07-02

[][] TCO17 Marathon Round2 20:55 はてなブックマーク -  TCO17 Marathon Round2 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928


準備フェーズ


とりあえず、感覚をつかむために次の2つの自明解を作った。

  • 毎ターン一番近い敵に攻撃
  • 990人まで貯まったら一番近い敵に攻撃

これだけでもそこそこ勝てている。前者が強い場合と後者が強い場合がだいぶはっきり分かれていて、勝ちやすいケースは前者が強くて、最終的に負けてしまうケースでは後者の方が強い。

これらをうまく組み合わせていく感じかなー、と考える。

スコアが順位ベースで決まるので、何もしない解に負けてしまうと大ダメージだからそれだけは無いようにしないといけない。


敵の方がPowerが高いことから、基本的には不利なんだけど、この不利を緩和したい。端数がたくさん切り捨てられるような攻撃をするといい、とかそういうのがありそう

…と考えていたら、6人以下で攻撃すると1:1でロスなし対消滅できて最もおトクであることに気づいた。速攻で連打するとそこそこ勝てるのは最初実装したやつで分かっているので、簡単に勝てるケースはこれをどこまで最適化できるかのゲームになるんだと理解する。

…で、そこではそんなに差がつかなさそうだからやっぱり難しいケースをどう賢くするかだなあ、という雰囲気になる。


モンテカルロシミュレーションやったりするのかなあと思いつつ、何やるにしても敵のパラメータ(power・attackT・locality)やTroopの行き先推定は必要なのでそいつらを実装していく。


実装フェーズ


そして実装していたら1週間経ってしまったので絶望する https://twitter.com/tomerun/status/864889052826288128

ついで、速攻ケースのシミュレーション+倒すbaseの順番での山登りを書き上げて、ある程度の高速化・パラメタ調整をやる。

この時点でまだ本丸(勝ちにくいケース)に手がついていないのに、もう2回目の週末が終わっていて絶望する https://twitter.com/tomerun/status/866298649680027648


とにかく、速攻で勝てないケースの戦略を作っていく。

とりあえず、全滅させられてしまう直前の逃避戦略を実装する。これはまあやるだけ

最序盤ですぐ倒せるところだけは速攻で倒しておくとして、基本は980まで貯めてから攻撃する。攻撃先をどこにするのかが考えるところ。

単純に一番近いところを攻撃するのは、すでに倒せるのが確定しているところに集まりすぎで損、というのはこれまでの結果から分かっている。

すでに倒せることが確定したbaseへは攻撃せず、他を狙うようにするとそれなりに良くなった。

あと、980貯まっていても、敵の攻撃が向かってきていて、攻撃で人数が半分になった状態では全滅させられてしまう場合は、攻撃せず待つようにしたり。

ここまででもう終了前日になってしまったので、全然細かい調整できてないんだけど観念して提出したら93万点とか出てびっくりした。

最後に、他の敵から攻撃されづらい位置にあるbaseを優先的に攻撃する、というのを入れようとしてみるが、良くならなくて終了


ビジュアライザ

f:id:tomerun:20170702204626p:image


カスタマイズした点は以下の通り。

  • 早送り・巻き戻し可能に
  • growRateに応じてbaseの形を変える
  • baseのindexも表示できるように(デバッグ用、普段はoff)
  • playerごとの合計人数を表示

そのほか


  • 今回は実装が難しそうで、そこまで高速化勝負にはならなさそうだったのでJavaを使った。結果的に、やっぱり実装がボトルネックだったのでこれは正解だった
  • 仲間同士で人数を1箇所に集中させて成長速度を増やすのはちょっとやってみようとしたが、あまり効果が感じられなくてやめた
  • 敵のlocalityも推定した(離散化してベイズ推定)けど結局使わなかった

結果

  • 暫定スコア 927281.55(100ケース)
  • 暫定順位 6位
  • 最終スコア 942086.41(5000ケース)
  • 最終順位 3位
  • レーティング 2491->2566 highest!

2017-05-11

[][] TCO17 Marathon Round1 01:11 はてなブックマーク -  TCO17 Marathon Round1 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903


やったこと


3段階で焼きなましをした。

  1. 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は、各辺について目的の長さと実際の長さの差の絶対値
    • 点の位置の重複は許す
    • 終わったら、各頂点をグリッド内の20*20のどこかにばらまいて700*700にする
  2. ランダムな頂点をランダムな近傍に動かす遷移。現在の辺の比の最大/最小の少し内側を目標にして、そこから外れた辺にペナルティがつく評価値
    • ペナルティは、(外れ量+0.5)^8 とか外れ具合に応じて大きく傾斜をつける
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
  3. 比が最大/最小の辺に属した頂点をランダムな近傍に動かす遷移。真のスコアが評価値
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
    • どの辺の比が最大/最小かを管理するのに、辺を比の値でバケットに入れて扱った
      • 各辺が自分のバケット内で何番目かを覚えておくと更新がO(1)でできる

最後の仕上げとして山登りをした。遷移は、比が最大/最小の辺に属した頂点を微少に動かして、他の辺が最大/最小を超えたら再帰的にその辺の頂点を動かす、というのを一定深さまでやる。

一応無意味ではないかな…くらいの効果はあった(結果のBestsが多かったのはこれのおかげだと思っている)


焼きなましの3フェーズの時間配分は 0.39:0.16:0.45 だった。これと別に最後の山登りに50ms使う。

焼きなましのイテレーション回数は合計6000万回くらい。SSEも使った(高速化の恩恵は1割程度)


時系列で


とりあえず真っ先に思いつくのは比が最大/最小の辺をいじることだけど、最大/最小だけ見てたら評価がハードすぎて一瞬で局所最適にハマりそう。もっとソフトな感じに評価したい。

一瞬バネ物理シミュレーションが浮かんだのだけど、その手の問題は以前ぼろ負けした(TCO13R3)のでひとまず考えないことにする。

というわけでまず焼きなましPhase2だけを作った。これが初日の48万点。


で、いろいろなケースの結果を出力して眺めていたら、長い辺がボトルネックになりがちなことが分かる。

長い辺は後から微調整が効きづらいので、最初の方でだいたい良い感じにしておかないといけない、と考える。

そこで焼きなましPhase1を作った。比で評価すると短い辺の重みが強くなってしまうので、差で評価。これで70万点超え。


ちょこちょこ調整した結果が3submit目の76万点。


ここで満を持してPhase3を追加すると4submit目の78.5万点。

https://twitter.com/tomerun/status/855468636860891136 ここで言っていた「伸びしろ」はこれのこと)


このあとはほとんど焼きなましの調整と高速化だけだったと言ってよい。

最終日の1日前の段階でアルゴリズム的な改善は打ち止めにして、ここで有給休暇を取って細かい高速化をまとめてやり、最終日に会社行っている間にクラウド使ってパラメタ調整、というのが最近の試合運びのトレンドになっている。

EC2のc4.8xlargeを24時間ほど動かして$17くらい使った。35スレッドだと1000ケースのテストが3分で終わるので良い。


もうちょっと探っておくべきだったかなーというところは、

  • 多スタート
    • 難しいケースでスコアが0.1くらいぶれることがあるので、その安定性のため
  • 辺の目標長を最初から短めに設定しておく
    • ちょっとやってみたら良くならなかったので捨てたのだけど、実際最終状態が短い方に寄るケースが多いし、Psyhoさんはこれ入れるとめっちゃ伸びる(余裕で1位超えるくらい)らしいし、もっと時間をかけて見ておくべきだったかも
  • 頂点の移動先はランダムじゃなくて辺の向きを考えて選ぶ
    • 1位2位はそれをやっているみたいなので

結果

  • 暫定スコア 790914.54(100ケース平均)
  • 暫定順位 6位
  • 最終スコア 797343.97(1000ケース平均)
  • 最終順位 3位
  • レーティング 2410->2491

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が出てきたのでまたいずれ)