TopCoder部トップ最新の日記ユーザー登録ヘルプnodchipのTopCoder日記<前の日2017-08-07ICFPC2017ICFPC2017の参加記録です。以下、nodchipの主観で書いているため、事実と異なる点がある可能性があります。今年は現在の同僚・前職の同僚・コンピューター将棋関連の知人の計6名で参加しました。fof会場提供・通信ライブラリ・アルゴリズム担当nodchip基本データ構造ライブラリ・アルゴリズム・インフラ担当periaインフラ・テスト担当Qhapaqアルゴリズム担当t-suzuki通信ライブラリ・ヴィジュアライザ・アルゴリズム担当ynasuアルゴリズム担当(辞書順・敬称略)問題概要periaさんのTweetを引用します。·グラフのエッジをターン制で取っていくn人ゲーム·いくつかのノードはλのラベル付き·自分のエッジだけ見て、各λから距離dにあるノード毎にd^2点。あまりにも豪華な会場だったためメンバー全員ビビる。21:00~コンテスト開始。問題文が公開されない。翻訳している間に他のメンバーが問題を読み終える。翻訳が面倒になったため放置。他のメンバーに問題文を教えてもらう。グラフ上のエッジを取っていって、ラムダ鉱山からの道を引いていくゲームらしい。勇み足ぎみにゲームのデータ構造を書き始める。コンピューター将棋い精通したメンバーが多かったため、命名パターンはやねうら王に似せた。鉱山から拡頂点までの最短距離を求めるダイクストラ法が一発で通らなかった。nodchip「だってダイクストラってだいたいこんな雰囲気じゃないですか...。」チームメンバーにソースコードを見せながら...。基本データ構造「Position」が完成。Positionを指し手データ構造「Move」に従って更新するPosition::do_move()を実装する。評価値を計算するEval::evaluate()を実装した。全計算しているので遅い。プレイヤーに取られていないエッジの集合を表すデータ構造を実装。大分前のマラソンマッチで使ったデータ構造の流用。00:00~連結成分をの管理にUnionFindを使った。指し手を一手戻すPosition::undo_move()を実装するためUnionFindのundoの方法を調べる。縮退をさせず、unionSet()したときに更新された値を全てスタックに保持しておけば良いらしい。03:00~基本ライブラリのパフォーマンスベンチマークを作った。CodeXLを使ってパフォーマンスプロファイルを取ってみた。ベンチマーク自体が一番遅いことが分かった。メンバーのアドバイスのおかげで、Eval::evaluate()の差分計算の方法を思いついた。追加するエッジeの両端srcとdstについて、srcを含む連結成分内の全ての頂点とdstを含む連結成分の全ての鉱山の直積集合をとり、それぞれについてスコアを足していけば良い。srcとdstをひっくり返して同様に計算する。各プレイヤーが取ったエッジからなるグラフを追加で持たせてやれば、時間計算量はならしでdo_move()一回につき鉱山の個数になる(はず)。08:00~データ構造が色々とバグっているので修正した。undoをしなければならないデータ構造ってバグりやすい気がする...。これっていちおう永続化データ構造と言えるのだろうか...。メンバーがオンラインモードの出力をゲームサーバーとつなげる仕組みを作ってくださったのだがWindowsで動かなかった。仕方なくC#で再実装した。自己対戦フレームワークを実装した。m4.16xlargeインスタンスを1台スポットでレンタル。WCSC27でElmo瀧澤さんに教えていただいた、入札化価格をオンデマンド価格にするというテクニックを実践してみた。オハイオデータセンターで1時間0.45$くらいで借りられた。EC2インスタンスにJenkinsを導入した。selfplayブランチにpushするとJenkinsで自己対戦が走り、終了後にチームのSlackの#Jenkinsチャンネルに通知が飛ぶ仕組みを作った。09:00~仕様変更...。Moveデータ構造を変更し、splurge・optionに対応できるようにした。12:00~Moveデータ変更に伴うビルドエラーの修正をした。15:00~AIのリファクタリングメンバーが作ってくださったヴィジュアライザをWindowsでも動かせるようにした。18:00~ヴィジュアライザで遊ぶ。optionが正しく処理されていないバグを発見...。21:00~option関連のバグが終了後に修正された...。最後に重大なバグが発覚したのが痛かった。次回参加するときはQA体制を充実させたい。https://topcoder.g.hatena.ne.jp/<前の。