Hatena::Grouptopcoder

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

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

2019-06-27

[] ICFP Programming Contest 2019 02:13 はてなブックマーク -  ICFP Programming Contest 2019 - TopCoderの学習のお時間


https://icfpcontest2019.github.io/

https://github.com/tomerun/icfpc2019


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

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

1日目


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

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


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

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


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


f:id:tomerun:20190627020653p:image


なのでイメージに必要なのは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な解になっていて良かった。


感想


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

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


f:id:tomerun:20190627020656p:image


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


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

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


f:id:tomerun:20190627020702p:image


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

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

2016-08-15

[] ICFP Programming Contest 2016 12:46 はてなブックマーク -  ICFP Programming Contest 2016 - TopCoderの学習のお時間


例年のように会社の人たちと参加した(チーム名:fixstars)。6人で合宿。


やったこと


ソルバ作成

紙を開いていくという王道な方針のソルバは他の人がやっていたので、違う方法を考える。

入力のskeltonを最小の多角形に分解して、それらを1x1の正方形になるように敷き詰める、という方針にした。


2日目の昼くらいには何となく動いて、雑魚問は解けるようになった。

ただ指数オーダーなのでちょっと入力が複雑になると全く無理。

改善しようとしたけどたいして良くはならず、解ける問題のうち最も複雑なのはこの程度でした(problem id 285)

f:id:tomerun:20160813214912p:image


出題用の問題作

2日目の夜に寝ながら考えたら、どうやら問題を解くよりも出題のほうがスコアに占めるウエイトが大きそうなことに気付いた。

その時点で自チームの出題は一応最後の分まで行われていたけど、けっこう解かれそうなので強化することにした。


Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。


このシンプル仕様でも紙を折る実装が難しくて、生成器を作るのに8時間くらいかかってしまった。

ランダムに折りまくって適当に設定した評価関数にかけて良いのを出力する、というものだけど、評価関数だけではあんまり強いのを抽出できず、何十個か生成した中から人目で強そうなのを選別していた。

(でも結局数十個しか作らないのだから、GUIを用意して人力で作るようにしたほうが良かった気もする)


なんとか最後11問は、これで作成した問題に置き換えることができた。


Unagiのものほど強くはないけど、ひとつを除いてUnagiにしか解かれていないし、サイズも1000未満なので、1問2000点以上入ることになっていてまずまずといえよう。

はじめに提出していたやつは20チーム以上に解かれていたので、置き換えたことで2万点ほど得られたことになる。良かった(ただしUnagiに対してはアシスト)。


なんか「いかにUnagi以外には解かれなくてサイズができるだけ小さい問題を作るか」という競争だった気がする。

サイズが小さいと解くうまみが少なくて、人力部隊のターゲットから外れやすくなるという効果もありますね。


ちなみに作ったのはこんなやつ(problem id 5607・5638)。

f:id:tomerun:20160815085141p:image

f:id:tomerun:20160815085140p:image


問題一覧作成

ソルバを作る過程でデバッグ用に問題を画像出力していたのを流用して、各問題がどんな見た目をしているかの一覧を作成した。

f:id:tomerun:20160813223017p:image


ちゃんとデプロイする環境を用意しなかったので、自分以外にはあまり活用されていない感


反省・感想


よかったこと

  • めっちゃでかいホワイトボードがあって活躍した
  • 合宿先からコンビニが近いと便利
  • 朝食がバイキングだったので時間に縛られづらく、朝食を取らない人の罪悪感も減じられた
  • 睡眠時間は1日5時間程度で、集中も続いて削りすぎずちょうど良いくらいだった
  • コンテストの形式が非常に良く練られていて、本質以外の部分でのストレスが無かった
  • たくさんソルバの実装ができた
    • 例年あまりソルバ担当にならないので…
    • 次回はインフラ方面やりたい

よくなかったこと

  • 最後ソルバにバグが残ってることが発覚して、取り切れず諦めてしまったけど、後で考えてみたらそのバグが存在したのは「解答サイズを最小にするため多角形をマージする」という部分なので、必ずしも実行しなくて良いところだった。それに気付いていればバグの影響をかなり抑えられたはずだが…
  • バグが残っていることに気付くのも遅かった。ソルバとしては解が出たら満点のはずなのだから、それ以外になっている時点で即アラートを上げてもらうようにしておくべきだった
  • コンテスト全体としての戦略に対する考察が不十分だった。出題がかなり重要であることにもっと早く気付いていたら、あと5万点くらい違っているはず
  • 会議室の鍵がひとつしかなくて扱いづらかった(一人だけ先に寝ておいて早起きしてくる、みたいなのがやりづらい)

そのほか

  • 「これyowaさん問題専用ソルバあってよいよね」「でも自分らでやりたくないよね」「だれかやってくれないかな」とずっと思っていたら天羽々斬がやってくれていた。ありがとう
  • モダン焼 フジ、学生の頃に気になってはいたけど結局行ったことがないままだ

2015-08-10

[]ICFP Programming Contest 2015 01:58 はてなブックマーク - ICFP Programming Contest 2015 - TopCoderの学習のお時間


例年のように会社の人と合宿して参加した。5人チーム。


やったこと


テトリスAIだったので、まあビームサーチかなということでまずは下に落とすだけのソルバを書いた。

2日目の午前中くらいには回転なし版がそれなりに動いて、あとはライトニングの提出に向けて回転を足して調整したり高速化したりで2日目終了。


3日目には他の人たちもソルバを拡張し始めていて、あまり他の人がコードをいじるようなつもりで書いていなかったのでアッアッ…という感じだったけど、そこで手を出してしまうと同じコードを同時に複数人で変更することになってカオスになるのでソルバの拡張は任せることにした。


公式の順位表が重くて見づらいことに嫌気がさして、ダウンロードしてきて適当にフォーマットして表示するようにした。

公式順位表のデータ部分はJavaScriptで生成されているようだったので、 Seleniumブラウザ起動して取得→重すぎ casperjsでサイレント実行して取得→なぜかcronで実行するとうまく取れない とはまっていたけど、実は https://davar.icfpcontest.org/rankings.jsダウンロードしたら順位表データが全部入っていた…。時間をだいぶ無駄にしてしまった。


あとはビジュアライザのスクリーンショットを順位表と合わせて表示するようにした。どのような盤面はどのくらいのスコアが出ていて、ライン消すのかPowerをたくさん狙うのかどちらがよさそうかなどを判断する情報になってくれたかもしれない。

それと各チームのベスト記録を元にした潜伏なし版ランキングも作っていたので、Unagiチームの強さはだいぶ早いうちから知ることができていた。


最終日はソルバのコードもだいぶ読めない感じになってきていて、Power探しシステムが完成していたこともあり、Powerの文字列候補のネタ出しをしていた。


Wikipediaからクトゥルフ関連の単語を大量に取ってきて投げたけど、その後で 公式Twitterに「Wikipediaからコピペしてんじゃねーよ」みたいなことが書かれているのに気付いた…。

最長のPowerの長さが51文字ということで、ストーリーの文書からちょうど単語区切りが51文字になっている部分を全列挙して眺めてみて、「a new representation for ancient protection schemes (, called davar)」というとてもそれっぽい箇所があるのを発見するものの、「ep」と連なっているところが→,←の順での移動だから活用するのはほぼ無理だね、となって試さなかった(結局全然違っていた)。


時間の最後のあたりでソルバの重複盤面除去が甘いことに気付いて(自分が初期に入れたコード)直したりほかのデバッグの手伝いをしたりしていた。


例年と同じく最後はちょっと慌てたけれど提出完了。


反省


特によかったこと

  • 最初に問題内容の理解を全員で合わせる機会を持った
  • かなり早いうちにビジュアライザができていたので作ったコードの動きが見えてやる気が上がった
  • Power探索がシステム化されて候補を探すのが効率的だった
  • ホワイトボードを有効活用できた
    • 合宿先に4枚もあった
  • (個人的に)食事以外ではほとんど間食せず、それなりに睡眠も取って健康的だった。コードが書けたおかげで体調良くなった

そのほか

  • 早いうちにやっておくべき事に着手するのが遅めだった
    • Power探しは公式ジャッジサーバーに提出して結果が出るまで待たないといけないのでどうしても時間がかかる。2日目の夜はまだPowerの候補を出していなくて公式ジャッジのリソースが遊んでいたのがもったいなかった
    • 順位表データはとりあえず保存しておくだけでも先にやっておきたかった。各チーム、ライトニング終了時点ではその時点でのベストスコアを出しているはずだけど、だいたいその後Power探しになって順位表がぐちゃぐちゃになるので、実際各ケースで最大どれだけのスコアが取れるのかがわかりづらくなってしまった
  • 役割分担をそこまで厳格には決めなかった
    • 本当はAI書く人は最初からずっとそれだけやるのが良いんだろうけど、まあみんなコード書きたいだろうし
    • あんまりぎちぎちにしてしまうのはコンテスト参加の楽しみという点では辛いので
  • AIのパラメタ振り
    • 盤面の特徴がさまざまなので1つのAIプログラムで対処するのが難しくて、ソルバのいくつかのバリアントで実行してベストの物を使えるように…
    • という話はしていたが結局あんまりバリアント作れなかった(実際それで良くなるのかどうかはわからない)。
  • テスタは別途作っておくべきだった
    • 手元での評価用に、正確に実行することだけを考えて作成したシミュレータを用意しておくべきだったように思う
    • サーバーに回答(またはコード)を提出して結果を得る方式だと扱いづらいので。公式がバグってることもよくあるし…
  • 開始前に「プログラムに名前をつけよう」と言っていたのを達成できなかった。特に好きなキャラクターとかないのが難しい

感想


毎回ICFPCは、いくらロジックだけ書けてもそれを人間とのインターフェース含めて有効に活用できる手段も持っていないと威力が半減するのだなあ、というのを思い知らされてたいへん学習モチベーションが上がる機会で。


そういったことを思う存分できた3日間が終わってしまったのが悲しくて、普段の中ではそこまで自由に色々できるわけではないけど、創意工夫を差し込める箇所を探して、できることを増やしていけるよう頑張ろう、