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部門のコンテスト風景を眺めた。

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


あと、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-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も推定した(離散化してベイズ推定)けど結局使わなかった

結果

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位はそれをやっているみたいなので

結果

2014-06-15

[][] TCO14 Marathon Round2 18:45 はてなブックマーク -  TCO14 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189


問題


ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。

こいつらを平面内に配置して穴を作る。

(穴の個数)^2 * (穴の面積合計) を最大化せよ。


やったこと


大きな穴を1つ作る+小さな穴をたくさん作る が最適になるのはまあ直感的にわかる。

colunさんに倣ってBigHoleとManyHolesと呼ぶ。


ManyHolesに何個の長方形を回すかは、実験してみたらN*0.54くらいが良さそうだった。

ManyHolesを作るときは、BigHoleで使われている長方形も利用した方がManyHolesに寄与する長方形の数を稼げる(その結果穴の数が増える)ので、BigHoleにくっつけて作る。


ManyHolesの領域はできるだけ表面積を小さくした方が良い(N個の長方形から作れる穴の数の最大値はNが大きいとほぼN個なんだけど、領域の外側に出ている長方形の個数分その限界から遠ざかっていく)ので、ManyHolesの部分は丸い感じになるようにする。

そのため、BigHoleの作り方を工夫して一部を外側に張り出すようにした。それでできた空間に小さい長方形を詰めていく。



小さい穴をたくさん作る方法なんだけど、賢い配置を考えて決めるのは泥沼っぽい気がして探索することにした。

長方形を小さい順に取って、既存の長方形の右側か左側に接するところを試す。他の長方形に接する一番端の箇所を見つけて、隙間ができていたらそれを穴ができたと見なす。

      |               |   |
      |               |   |
      |               +---+
 -+   |                 +---+
  |   +----             |   |
  |+----+      や     -+|   |
  ||    |              |+---+
  ||    |              |
  |+----+              |
  |                    |
 -+                   -+

こんな感じだと良い配置。


時間制限いっぱいまで、使う長方形の順序をちょっと変えながらこれを繰り返す。本当はビームサーチしたほうが良いのだと思うけど、実装時間が足りなくて断念してしまった。


あと、BigHoleの内側にManyHolesを作るのではなく外側に作ったら、面積が2%くらい増えるなーと思ってたけど、どうやっても穴の個数が減ってしまってうまくいかなかった。


画像


seed=1の例。


全体:

f:id:tomerun:20140615183106p:image


上部:

f:id:tomerun:20140615183105p:image


ビジュアライザには次の変更を加えた。

  • 穴になった部分が赤く塗られていたけど気持ち悪かったので消した
  • スクロールやズームを可能にした
  • 縮尺を表示するようにした
  • ビジュアライズ部分をテスタと分離して別プログラムにして、テスタ実行時に表示するのではなくスタンドアローンで起動できるようにした
    • テスタではログに出力しておいて、ビジュアライザにはそれを読み込ませる

結果

  • provisional score : 954551.54(各ケースで1位を100万点とした相対スコアの平均)
  • provisional rank : 9 / 170
  • final score : 954969.99
  • final rank : 10 / 170
  • レーティング : 2188->2250

意味のあるスコアを出すまでの実装が大変なのでやっぱり参加者少なかったですね。

2014-05-04

[][] TCO14 Marathon Round1 21:23 はてなブックマーク -  TCO14 Marathon Round1 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132


問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20140424


やったこと


問題読む→はい、いつものビームサーチのパターンですね

2次元グリッド上でなんかゲームやって、1手ごとならビームサーチ、全体を構成するのなら焼きなまし、というパターン最近多すぎて飽きてきた…


ターン数が10000と多くて、評価関数で色々やろうとするとビーム幅小さくなってどうやってもスコア下がってしまうので、評価関数はごく簡単にしてひたすら高速化を頑張った


探索空間


C=4の場合は1手で消せるところ、C=5,6の場合は1手か2手で消せるところを全探索

始めは高速化のため、前回動かしたところの周辺だけ探す、ということをやっていたけれど意味なかった


ビーム幅は、時間をいっぱいまで使えるよう実行中に残り時間を見ながら動的に変える


評価関数の要素


  • 累計の得点
    • 連鎖を全部シミュレートしてしまうのはあまり意味がなく、得点が0か1か2以上か、だけ判定した
  • 2×2のブロック中に3つ同色がそろった箇所・2つ同色がそろった箇所が、盤面内に何個あるか

データ構造と探索方法


struct Board{
    uint64_t f[20];   // 各セルがどの色か。最高6色、番兵として使う無効分も入れて7色なので1セル3bitで収まる。周囲2マスずつ番兵にするので20*20分確保
    uint64_t v[15];   // 各2×2の領域がどのような状態か。15×15個分確保。
                      // 3つ同色のパターン:4個、2つ同色*2のパターン:3個、2つ同色*1のパターン:6個、同色無しのパターン:1個 で合計14個なので1つ4bit
    uint64_t v2[15];  // 高速化用。基本的にはvと同じだけど、一度探索してみた結果1手や2手では消せないとわかった箇所は、
                      // 0(無効を意味する)で上書きして再度調べないようにする
};

探索するときは、たとえばv2が「3箇所そろっていて右下だけ違う色」を示しているときは、次のような状態になっている。

 AA
 AB

下の図のXの箇所を調べ、そこの色がAだった場合、それをBの箇所に持ってくる動きを候補として採用する。

 AA_
 ABX
 _X_

C=5,6でXの箇所が候補にならなかった場合は、次に、2手で揃えられる箇所として、下の図のYの位置も調べる。

 __Y__
 _AAY_
 YABXY
 _YXY_
 __Y__

v2が「2箇所そろっている」の場合も、同じように2手で揃えられるパターンを全列挙してそこに揃えたい色が入っているかを調べる。


反省


  • 同一盤面の除去をやらなかった
  • 評価関数のパラメタ調整をやらなかった

同一盤面の除去を軽く入れてみたら2%くらい上がったので、もっとこの辺をちゃんとやっていたら通過ラインくらいまで行けていた可能性もある。

詰めが甘いです


結果

  • provisional score : 950346.80(各ケースで1位を100万点とした相対スコアの平均)
  • provisional rank : 10 / 333
  • final score : 952155.96
  • final rank : 10 / 333
  • レーティング : 2334->2371 highest更新