ACM-ICPC 2016 国内予選 参加記
チーム結成
hadroriさんからDMが飛んできてよすぽ&dnkチームに空きがあるからどう？と誘われたので参加した。
僕が最年長だけど競プロ的には最弱なのでつらい。
あと、自分だけJavaを使うので若干デバッグで不利かもしれない。
チーム名がなかなか決まらず「po」になった。
http://icpc.logic.cs.tsukuba.ac.jp/team/279830
模擬Bとそれとは別に練習1回やって国内予選へ。
国内予選
まずBを読んでBを解いた。
ICPC特有の事情によってJavaはテンプレが必要だが、ちゃんと準備してなくて焦った。
難しく無い問題の割に時間をかけてしまった。
次にCの解法が降ってきたのでそれを実装した。
降ってきた解法がやや間違っていたが勘違いだったのですぐに修正できた。
D,Eをチームメイトが実装している間にFを考えた。
前半パートの時点で既に実装が重そうでつらい。
No.348 カゴメカゴメ - yukicoder
を思い出した。
後半パートは(根付き)木の同型判定になることが分かった。
木の同型判定は、部分木の同型判定を行ってマッチングを使うと可能なのは知っていたが、つらそうだと思った。
Fは実装が重そうなので後回しされることになった。
Gの解法を聞きながら「合ってるんじゃない？」とか言ったら不完全で結果爆発炎上した。
結果的にABCDEの5完でアジア地区予選に進めそうなので頑張ります。
予選後
懇親会に参加してチーム内反省会をするなどした。
帰って一人二次会(お酒を飲むだけ)をしながらこれを書いている。
CODE VS 5.0 決勝に出場しました
結果は、Bリーグで1勝2敗のリーグ3位で敗退となりました。
応援して下さった方々ありがとうございました！
悔しさはありますが、実力相応の結果だと思います。(むしろ決勝に来れたのが奇跡的です)
一方、自分が工夫した部分が決勝でうまく働いているシーンがあってそれは嬉しかったです。
CODE VSが来年も開催されればチャレンジしたいです。
各対戦振り返り
vs D0
oxxooxoxx 4-5 負け
予選終了から本戦までの間、本戦AIからリスキー行動*1を外したAIを戦わせていたのですが、1-6という厳しい結果でした。
敵分身も使ってくる相手だったので、本戦版でも相性はそれほど良くならないはずです。
ソウル回収効率で言うとほとんど互角に見えます。
私のAIが回転斬に消極的な一方、D0さんは回転斬に積極的に忍力を使うので、D0さんがうまく回転斬を使うかが勝敗を分けていたように見えます。
また、要所要所で敵分身を使ってくるのも効いていました。
ラウンド8では、こちらが回転斬準備で犬に囲まれた時に敵分身を使ってきたので、こちらの分身油断モードが発動しなくなりました。
また、トドメも敵分身でした。
ラウンド9でも、回避困難な状況で敵分身を使われて負けたので、この辺りはキッチリやってくるなあと思いました。
ラウンド1はD0さんが回転斬で忍力を使いきり、なにもしなくても2手詰みとなったので、超高速反復横跳び→移動なし回転斬りが発動しました。
誰にも気づかれてなさそうです。
vs togatoga
xooxxooo 5-3 勝ち
予選終了から本戦までの間で15-26でした。
togatogaさんは回転斬のプロですが、超高速は使わないので、超高速低コスト回転斬高コストを引けば勝率は上がります。
本戦では回転斬り高コストが多かったので、そこは運に恵まれました。
ラウンド1では、早くから分身油断が発動していて、最後は犬に囲まれた時に回転斬が低コストにも関わらず使わずに負けてしまいました。
ラウンド7でコスト7高速移動を使っていることに対するコメントですが、より正確に言うと、まず妨害警戒で防御系忍術を使わざるを得ない状況だったはずです。
そして、その中で超高速だけ獲得できそうなソウルが多かったため、超高速を使ったのだと推測します。
ラウンド8は、見応えのある試合になったと思います。(自画自賛)
AIに搭載した機能のほとんどが使われている、自分のAIを象徴する試合です。奇跡か。
まず、敵分身を使われないまま犬30を超えたので、分身油断モードが発動し、左下で犬をすり抜けながらソウルを回収しています。
中盤からは回転斬りで追い上げました。2ターン目に回転斬りを発動した時、出来るだけ多くの犬を巻き込めるような動きをするようにしています。
犬で互角になった後、近くに取れるソウルが無くなり困っているシーンでは、評価値が3ターン連続で悪化した時に発動する分身連打モードで左上に強引にすり抜け、勝利を確実にしました。
最後は2手詰めの落石+ドヤ顔回転斬で締めてます。
私のAIは回転斬の条件が厳しく、コスト6でも4体巻き込めないと積極的に使いません。
他にも、使用後の残り忍力や、このソウル差で犬の差をひっくり返せるかなどを考慮します。
vs colun
xoxxooxox 4-5 負け
予選終了から本戦までの間で4-14でした。
一切妨害をしてこない相手なので、リスキー行動を解除した時には相性のよい相手になるはずです。
それでも勝てなかったので、colunさんのAIがとても強いと言えます。(バグってるのに・・・)
本戦の試合でも強引な分身を使って勝っている試合がいくつかあるように見えます。
恐らく、超加速のコストの低さよりも、自分身のコストの低さの方が勝率に寄与しています。
自分身コスト2をもっと引ければ分からなかったかもしれないです。
リーグを2勝まみれにしたかったなあ・・・
ラウンド8で詰ませたかのようなコメントをしていましたが、完全に嘘でした。(画面が見えていない)
詰ませが発動したのではなく、相手がスキル無しだと詰むときに、初回とりあえず妨害してみるやつです。
刺さったのはたぶんcolunさん側のバグです。
私はステージで自分の試合結果見るのめちゃくちゃ緊張してました。
冷静なコメント入れられる人々すごい。
雑感
結論として勝ちたかったしか出てこない・・・
懇親会では予選の思い出を語れて面白かったです。逃げ切り狙いトークとか。
ゲームについての感想
CODE VS 4.0の時は折れたけどCODE VS 5.0はやれたのは、最初にやるべきことが分かりやすいからということと、オンライン対戦でモチベーションが上がったことだと思います。
最初は犬避けてソウル集めるだけで勝てる→オンライン対戦で強い人の戦法を(可能な限り)パクるで結構行けます。
積極的に攻撃するAIはそうでないAIに比べて難しいので決勝に攻撃AIが少ないのは仕方ない気がします。
さらに、安全志向AI＞攻撃AI＞リスキー行動AI＞安全志向AIみたいな相性があり、
リスキー行動AIは予選だとシルバー～ブロンズの超攻撃AIにレーティング持ってかれるので、決勝に進出するのが難しい状況でした。
それにより安全志向AI優勢の流れが更に強くなった気がします。
繰り返しになりますが、後半リスキー行動取りまくりAIで決勝環境勝てなかったのホント悔しいです・・・
とはいえ、攻撃強くしすぎると殺伐詰み探索勝負になってしまうのでもしかしたらワザと避けているのかもしれません。
CODE VS 3.0とかそんな感じだったのだろうか・・・？
もっと特徴的な戦法も考えたことはあります。
例えば岩の配置を整備し、うまく犬の最短経路を切り替えることで犬を往復させるとか、
忍者に時計回りにグルグル移動することを強制させると実は強いんじゃないかとか。
CODE VS 5.0は本当に楽しめました。恐らく最後？の春休みのいい思い出になりました。
AIをこっそり公開しています
実行可能jarとソースとreadmeが入ってるzipです。
jarをCODE VSクライアントと同じフォルダに置いてreadmeにあるコマンドをコピペすれば多分すぐに動かせます。
本戦のAIより少し強くなっているので是非戦わせてみてください。
ソースはめちゃくちゃ汚いので見る価値は多分無いです。
https://dl.dropboxusercontent.com/u/264857305/pirozAI_v6.zip
(そのうち消えると思います)
*1:敵の忍術使用によって負ける可能性のある行動
CODE VS 5.0 でやったこと
決勝用AIの提出が完了しました。
提出完了後TLで感じたのですが、マラソンなどで経験を積んでいる人はやはり違うなあと感じました。
僕が試行錯誤で進んでいる所を当然のこととして一瞬で先に行っているのだろうなあと思います。
なのでここに書いてあることは相当筋が悪いです。
最終的にできたもの
- 幅100ビームサーチで3手探索。1手目のみ敵味方の忍術を考慮。
- 忍者2人を別々に考えたりはしない
- 序盤は再優先に取得するソウルを変えながら深い探索をし、最も良いものを採用。
- 落石や分身の危険・チャンスを察知し、相手の反応を伺う。
- 最初の落石・分身チャンスはとりあえず攻撃してみる。
- 「落石油断モード」「分身油断モード」
- 相手が分身を使ってソウルを強引に取っていると判断した場合、ソウルに敵分身する。
- 評価値の悪化を検出し、様々な評価関数を試す。
- それでも悪化が続いたら、「分身連打モード」
- 回転斬のために移動する「回転斬準備」
- 相手のソウルが尽きた時、詰み手順探索
- 二手詰みが見つかる程度
- 勝ちを確信したときにダンス💃
評価関数
n手先の盤面は、n個の移動経路の評価値の和と、最後の盤面の評価値を足して算出する。
- 盤面の評価
- 忍力(x100)
- 最も近いソウルまでの距離(x-1) (岩のあるマスは重みをつけて算出)
- 忍者同士が近すぎる時のペナルティ(距離3以下で-2)
- 経路の評価
- 獲得するソウル(x300)
- 回転斬で撃破する犬(x100)
- スキルを使われると即死する場合のペナルティ(状況により-10^5～-0.1)
以下、gitの履歴を見ながらひたすら振り返ります。
自分のモチベーション維持にAI名にバージョンを入れるのをやっていました。
v1～
とりあえず動かそうという段階。
- 犬が隣接していないマスに移動
- 岩は動かせないものとする
- ソウルまでの距離を計算し、最も近いソウルに移動
v2～
オンライン対戦での反省を活かしながら実装を進めた。
- 真面目なシミュレータを作る
- 1手探索。評価関数はソウルまでの距離と、端ペナルティなど。
- 詰んだら回転斬
- 詰んだら超高速
- 移動を落石によって妨害されて犬に捕まりそうな時、自雷撃
- 相手がスキル無しだと落石で詰む場合、敵落石
- 相手に2回回避されるまでやる。相手が防御系忍術を使えない場合は必ずやる。
- 詰んだら自分身
- 詰んだら自雷撃
v3.0～
作り直し。確かシルバーに居て、追い上げるぞという感じだった気がする。
気にするべき妨害は落石と分身。雷撃は即死にはならない。
分身は、自分身を使っていないときは即死にはならないので、考えないことにする。
評価関数は
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 壁付近のペナルティ
- 忍者同士が近すぎることのペナルティ
- 忍者周辺4マスに障害物や犬が多すぎることのペナルティ
- スキルを使われると即死する場合のペナルティ
を入れた。
1手探索で、高速移動、自雷撃、自分身、回転斬を試す。
自雷撃は忍者からの距離3まで。落石対策に関わる範囲がこれくらいなので。
自分身は四隅・犬の出現ポイント・忍者の居るマスを試す。
相手のスキルは、忍者の移動経路上の落石を常に考慮する。
自分身を使う場合は、忍者からの距離2までの敵分身と、分身上の落石を考慮する。
相手が妨害スキルを使ってこない場合にそのスキルへの警戒を緩める、「落石油断モード」や「分身油断モード」を実装した。
「分身油断モード」は実装が悪く、ほとんど機能しなかった。「落石油断モード」は妨害をしないAIにまあまあ刺さっていた。
v3.8～
ビームサーチを実装した。実行速度の関係で、2手目以降はスキル使用なし敵の妨害考慮なしにした。
最初は幅5深さ5とかを設定している(※まるで意味が無い)
評価関数は、盤面の評価と経路の評価を分ける必要性を感じたので、分けた。
盤面の評価は、
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 忍者同士が近すぎることのペナルティ
経路の評価は、
- 獲得するソウル
- 回転斬で撃破する犬
- スキルを使われると即死する場合のペナルティ
が該当する。
そして、複数手先の盤面の評価値は、経路の評価値の和+最後の盤面の評価値となる。
v4～/高速化
ビームサーチを実装したことで実行時間の問題が出てきたのでv3のAI部分を一旦消して、シミュレーション部分の高速化に取り組んだ。
ここで最後の方に実装したのも含めて高速化の話をしてしまいます。
AIはJavaで書いていたのでJavaの話です。
高速化をする上で役に立ったモノ・テクを列挙してみます。
オブジェクトプーリング
二次元配列のnewの時間がヤバイのでプールを作った。
ターン毎にほとんどの情報を捨てるので、ターン終了時にインデックスをリセットし、最初から順に取り出すということをしていた。
キャッシュ
犬の行動をシミュレーションするのに、忍者からの距離をBFSで求める部分がボトルネックになっていたので、岩と忍者の位置を入力、距離の配列を出力としてHashMapに突っ込み、必要に応じて取り出すようにした。
忍者が岩を動かさなければキャッシュにヒットしまくりなのでかなりの短縮になった。
バケツソート
犬を忍者からの距離順・id順にソートする部分に標準ライブラリを使っていたが遅いため専用のソート関数を自作した。
距離は0から100程度までしかない(本当?)ためバケツソートを使う。id順にソートする部分は挿入ソートを用いた。
配列を初期化する時間をケチるために、タイムスタンプを使って、バケツから出し入れするときに有効なデータか判定した。
並列化
移動を全パターン試すという処理がよく出てくるので、パターンをいくつかのブロックに分けて突っ込む。java.util.concurrentパッケージ大活躍。
色々高速化して結局一番遅いのはやっぱり犬の移動シミュレーションでした。
おおよそO(犬の数)になったと思うのですがう～ん
v5～
v4で高速化が済んだのでv5とした(バージョンの上げ方が適当過ぎる)
高速化が済んだ分探索できる量が増えたので、色々実験をしてどこに計算時間を割けばいいか色々検証する。
ビームサーチのパラメータ調整をした。
パラメータ調整に関する知見が全く無かったので、眺めてみたり自己対戦を重ねた。
色々試した結果、幅15深さ1か幅100深さ2くらいが適当だなあと思った。
深さや幅をこれ以上増やしてもあまり効果が得られなかった。
同一局面除去しないとビームサーチが貪欲と化すので気をつけましょう😇
— ぴろず (@p_shiki37) 2016年3月22日
評価関数が最も近いソウルまでの距離を利用しているからビーム内が似たり寄ったりになると思ったのですが、そもそもの原因はこっちだったかもしれない・・・
つまりビームサーチというよりは枝刈り全探索に近い？
探索が改良された分、評価関数のペナルティ項の多くを消した。
評価関数、特に何も考えずに忍力1につき100点、ソウル取ることは100点(つまりソウル獲得で合計+300点)
としていたが、忍術を使ってでもソウルを取る方が良い場面の方が多いので、ソウルを取ることの点数を300点にし、ソウル獲得は合計500点になった。
したがって、コスト5未満の忍術を使ってソウルを取れるなら積極的に忍術を使う。
結構動きが良くなるが、コスト高めの高速移動を使いすぎる傾向が出た。
普通のビームサーチの後、ビームに残ったものから追加の細いビームサーチをして、最も良い物を採用という処理を追加してみた。
これは出現するソウルなどを考慮していない分、微妙な動きをしてしまうのであとで消した。
ビームサーチが貪欲に近くなってしまうことの対策として、通常の評価関数で取れるソウルが無くなった時、複数の評価関数を試すという処理を取り入れた。
色々な評価関数を試してみたが、最も効果があったのは、特定の点との岩を無視した距離を使う評価関数だった。
点としては、マップ上の4隅と中央を使った。つまり、困ったときに追加で5つの評価関数を試す。
これにより、近くのソウルが取れない時に大胆な移動をして遠くのソウルを集めることが可能になった。
複数の評価関数を試しても3ターン連続で評価値が悪化する時、「分身連打モード」に移行する。
「分身連打モード」では、敵のスキルを無視し、いずれかの角に自分身を連打しながら最も近いソウルに向かうという動きに限定し、11手の深い探索を行う。
これにより、強引なソウル取得による粘りが可能になった。
なお敵分身には弱いが、敵分身を適切に使ってくるAIは予選のときにはほとんど居なかったので、結果として強くなった。
通常の探索でソウルが取れるまで近づければ、通常のモードに戻る。
v6
v5のAIのメイン部分がスパゲッティ化して頭が痛くなったので、一度リセットしてv6にした。
決勝の前日、最後のリセット。
v3の時にあった「落石油断モード」「分身油断モード」を復活。
これで「落石油断モード」「分身油断モード」「分身連打モード」「秒読みモード」の4つがあることになりif文地獄と化した。
上位陣で回転斬をうまく活用する流れがあったので、回転斬を積極的に使う動きを追加した。
具体的には特定の条件を満たすと、2ターン目に多くの犬を回転斬で倒せるような移動を探索する。
相手が忍術を使わないと落石や分身で詰むようなタイミングで、相手がどの忍術を使うか、あるいは使わないかを記録して、
攻撃をするかどうかの判断材料にする仕組みを復活。
pirozAI[6.5.1]、決勝進出！
決勝までの間もオンライン対戦をしたいが、油断モードや分身連打モードの対策をされるとマズイので、
実行時引数でこれらのモードを抑制できるようにした。
本戦に向けて並列化などのパフォーマンス改善をした後、基本的な動きの改善を試みた。
忍者同士が固まってしまう問題に対して、
- フィールドを4分割し、同じエリアに入っていると減点
- 忍者同士の距離が3以下だと減点
を試した所、後者が良かった。
また、序盤のソウル取得効率が勝敗に大きく影響することに気づいたため、
序盤は、再優先で取得するソウルを指定した評価関数というものを実装し、それぞれで細くて長めのビームサーチを実行。
最も評価がよかった評価関数を採用し、通常のビームサーチを行うという動きを実装した。
序盤のソウル取得効率が向上した。
ここまで忍者からソウルまでの距離計算では、岩は通れないものとしていて実際との剥離が大きかったため、
動かせる岩を重さ3,動かせない岩を重さ10として距離を計算するようにした。
動きはおおむね良くなったが、ソウルが岩で囲まれているような場合や、ソウルが岩でできた通路にある場合にはハマることが増えた。
これの対策にもなるが、2番目に近いソウルと3番目に近いソウルへ向かう評価関数を追加し、
複数の評価関数を試すフェーズに入れた。
複数の評価関数を試すフェーズに早めに突入するために、ビームの中身を見て、1手目から3手目で評価関数が下がるならば早めにこのモードに入るようにした。
複数手詰み探索を実装した。実際に動かしてみると、価値のある詰みを見つけられることはほとんど無かった。
唯一、敵が自分身を使えない時に2手詰みを発見できるので、この場合のみ探索するようにした。
これだけだと勿体無いので、勝ちを確信した時に意味のない動きをする「ダンスモード*1」を実装した。
ちなみにデバッグには役立った。
もうすぐ決勝
決勝出るぞニコファーレ行くぞ
ニコ生で放送されるぞ
live.nicovideo.jp
正直決勝進出者は皆強すぎなので勝てる気がしません。
あとは乱数の神に祈って、いい戦いを見せてくれることを期待します。
*1:またの名を煽りモード
CODE VS 5.0 予選6位通過しました！
CODE VS 5.0の予選を6位で通過しました！
https://codevs.jp/user/ranking/50/
レートが最高点に達したなと思ったら止める戦法で逃げ切りました！
ずるい！
例年通りなら決勝はニコファーレで行われ、ニコ生で中継があるはずです。
体調を崩したりしなければ行くつもりです。
CODE VS 5.0の楽しみ方
犬を避けながら最も近いソウルに向かいます( ◠‿◠)
NoneAIなどに勝ちます( ◠‿◠)
詰んだら回転斬を使うようにします( ◠‿◠)
NormalAIに勝ち越します( ◠‿◠)
オンライン対戦に行きます( ◠‿◠)
岩が降ってきます(´･‿･｀)
楽しい！！
✌('ω'✌ )三✌('ω')✌三(✌'ω')✌
追記:
CODE VS 5.0に参加していない人向けに訳すと、
最初にやるべきことが分かりやすいルールで、プリセットAIと対戦して強化したり、
オンラインで「そういう戦術もあるのか～」ってなるのがとても楽しいです。
感想
CODE VSを知ったのは3.0の決勝の放送の時で、4.0の時は何もしないAIを書いて飽きました。
5.0は5日から始めましたが、とっつきやすさやオンライン対戦の面白さから熱中してしまいました。
上位勢の動きを見ると、「そんな動きどうやったらプログラムできるんだ・・・」と思います。
私のAIはバランスよく強いというよりは一部の相手に相性が良いようなタイプだと思うので、
予選を通過したのは本当に奇跡的だったと思います。
提出が不利そうだったので踏みとどまったのは正解でした。
ゲーム外の勝負もしていく心構えだったので、躊躇なく逃げ切りに入りました。
最終日のほとんどは順位表に張り付いて通過ボーダーの推移を見守っていました。
決勝のAIを提出するタイミングになったら、予選期間中どんなことをやっていたのかを振り返ってブログに書きたいです。
チームラボさんに遊びに行きました
CODE RUNNERで2位だったので(?)
キャリフル経由でオフィス見学のお誘いがあったので行ってきました！
CODE VS予選真っ只中、CODE VSやCODE RUNNERの開発者の方とお話することになりました。CODE VSのコツは聞けませんでした。
その代わり去年のCODE RUNNERの話は色々できて、今年はもっと面白くなるだろうと思いました。
あと参加記を書くとやっぱりチェックされるようです。適当なこと書けないですね(´･‿･｀)
Splatoon中に電子レンジを赤く照らして牽制する
(台所の照明を消した状態です)
経緯
「Splatoonの試合中に電子レンジを使われると接続が切れる」という現象は、実家Splatoonプレイヤーの多くが悩まされていると思います。
僕の場合、無線LAN親機とWiiUが階をまたいで離れているので有線接続も難しいです。
家族は僕のSplatoonプレイに協力的で、レンジを使う前にSplatoon中か確認を取ってくれます。
しかし、キッチンとWiiUは遠いので何かと負担をかけてしまいます。
そこでHueを使ってSplatoonプレイ中かどうかをキッチンに通知することにしました。
最終的な構成
WiiUの映像をキャプチャしてIkaLogが試合開始と終了を判別し、スクリプトを実行します。
スクリプトが自作アプリHotaruIkaのボタンを自動クリックすることで、HotaruIkaがHueのAPIを叩いてHueが点きます。
Hue
Hueはスマート電球と言えるものの一つで、遠隔操作で色や明るさを変えることができます。
色は普通の電球のような色から、カラフルな色も出せます。(ただ水色は出ない)
明るさは、最小にすれば直接見ても眩しくないくらいです。最大は眩しいです。普通に電球です。
他にもタイマー機能などがありますがまだ使ってません。
パソコンからHueを操作できるようにする
HueはAPIが公開されています。
HTTPリクエストでJSONを送るとJSONが帰ってくる形式のようで、とても簡単そうです。
折角なのでアプリは自作することにしました。
買って色々調べるまではJSONを投げる気マンマンでした。
が、そもそも公式でSDKとサンプルプログラムが用意されていて、JSONをパースするまでもない様子。
結局サンプルを基に改造したら実装する部分がほとんどありませんでした。
HotaruIka
できたアプリがこれです。イカ関連で光りそうな安直な名前にしました。
特定のHueをオフ、黄色に点灯、赤に点灯のいずれかにします。
赤が試合中、黄色がSplatoonプレイ中を表します。
Splatoonのプレイを開始するときに起動すれば、自動で黄色の点灯を始めます。
適当なボタンを押すことで状態が切り替わるほか、一定時間放置や終了でオフになります。
IkaLog
IkaLog って何ができるの
任天堂の WiiU 用ソフト「スプラトゥーン」の画面をリアルタイム解析して、 いろいろなことができるソフトです。
https://github.com/hasegaw/IkaLog/blob/master/doc/IkaUI.md
IkaLogの機能は本当に色々あります。
例えば、自動録画とリネームを行うことや、
stat.inkと連携して戦績を保存することができます。
stat.ink | ぴろずさんのイカログ
IkaLogの自動録画機能でHotaruIkaを操作させる
IkaLogのGUI版のIkaUIを用いました。
自動録画は、試合の開始時と終了時にスクリプトを呼び出すので、スクリプトを編集して、HotaruIkaのボタンを操作するように追加します。
IkaUIに付属するスクリプトは、AutoITを使って書かれています。
AutoITには、ウィンドウを探す関数やボタンを押す関数が用意されているので、自動操作が簡単に書けます。
SwingのボタンはAutoITで探せないようなので、WinGetPos,WinActivate,MouseClickといった関数でごまかしました。
マウスを操作するので、試合の合間にtwitterを見てたりすると誤操作があり得ます・・・
DDPC2016参加記
予選
Tasks - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder
A問題
やるだけ。
B問題
でソートして二分探索しながらシミュレーションっぽいのをやる
バグらせまくってつらくなったので、愚直解とソートして愚直の2つで30点取ってC問題へ
C問題
考察を頑張ると、削除をしまくるか、ある程度置換をした後先頭への挿入or置換をする2パターンになって、
後者のパターンはSuffix Arrayが必要だと分かる。Suffix Arrayのライブラリを持っていないので愚直SAを書くもそもそもSA以外の部分がバグっていたらしい。
点数を取れず時間切れ。
97位だけど17卒に当たるので本戦参加権を得た。
本戦前
DDPC参加者の朝は早い。7時起き。
準備・移動フェーズは特に問題無かった。
しかし、会場は電源が不足しているらしく予め充電しておいた方がいいとの情報が入る。手遅れ。
会場は、基本的に机に電源が無かった。電源がどうしても必要になったら特定の席に移る必要があった。
席は一つの長机を2人で共有する形。広くもないが狭くて困るほどでもなかった。
本戦
開始の合図が開始時間に遅れて始まる。開幕コンテストページに繋がらなかったが数分で回復。
問題一覧
Tasks - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 | AtCoder
A問題
やるだけ。
B問題
最小の時刻を求める問題なのでまず二分探索して、ある時刻
までに総和を
以上にできるかの判定問題にする。
制約的に二分探索後の判定は貪欲っぽいと予想→貪欲でできた
ある時間に選べる料理はその前の時間でも選べるので、最後に選ぶ料理から順に考えると都合が良く、選べる料理で最もおいしさが高いものを選べば良い。
料理を時間の降順でソートしておき、時間を戻しながら適宜料理を優先度つきキューに入れ、美味しさが最大となる要素を取り出していくように実装。
AC。
C問題
B問題までがスムーズだったので順位が良かった。C問題は10点の部分点は自明で満点は難しそう、間の20点はDPっぽいので満点のヒントになりそうなので20点を狙う。
左から右へ見ていくDPは無理、区間DPもなんか違う。
括弧列に対して、
と
の条件を満たす塗り方の数が
の条件を満たす塗り方の数から計算できれば解けそう。
結局構文解析をしながら配列をマージしていくDPのようなものが生えた。
最初の提出が10点(WA+TLE)だったので、MODを取るミスを疑ったが見つからない。
sum += sum + ans[i]なる謎の記述を訂正してまだ10点。
無駄な部分を計算しないようにしてTLEを無くす、WAが残り10点。満点のケースでもTLEが無くなったので一応満点も見えてきた。
辛くなってきたので一度D問題とE問題を見に行く。D問題は部分点がなくさっぱり分からない。E問題は部分点はあるもののデータ構造不可避な問題文を開いた瞬間バイバイ。
C問題のバグをなんとかする方針にした。
なんとか考察ミスを発見した。
括弧列を連結していくパターンで赤に塗った数と青に塗った数の差は一時的により大きくなるパターンがあることを見落としていた。
修正するがインデックスの変換をバグらせREを2回。
残り40秒で最後の提出。コンテスト終了の少し後にジャッジが走り切り、AC。やったぜ。
結果は15位でした。予選の順位や本戦に来ている人の強さからしてまずまず良い結果だと思います。
でもC問題はハマり過ぎた・・・
本戦後/感想
すぐに解説や表彰はなく、会社紹介や講演会、社内ツアーがあった。
社内ツアーは高い機械が動いている所が見れて面白かった。
DISCO本社の開催で説明やツアーが充実していたのでDISCOについては少し詳しくなったが、ディスカバリーチャンネルは会社のアピールをほとんどしていなかった。
撮影や取材をしていたので今後DDPCの様子が映る番組が放送されたりするかな・・・？
CODE RUNNER 2015 参加記
2位でした。とっても嬉しいです。おかげで懇親会では普段のN倍口数が増えて、参加記も文章が増えます。
開始前
紙ぺーぱーさん、とこはるさん、すぎむさんとお昼にカツを食べた。願掛けは意識してない。
会場の入り口前でchokudaiさんに遭遇した。
案内板らしいものはなかったのでchokudaiさんが居なかったら少し困ったかもしれない？
会場入り。受付してQUOカード10000円(ギリギリ首都圏外判定)とTシャツを手に入れる。
レッドブルを配っていたがおなかの調子があまり良くないのでスルー。
席について接続テスト。最初は繋がらなかったが数分で回復した。
始まるまで適当に机を整理してtweetdeckを眺める。
本戦中
考察と実装と感想をある程度分けてるので若干時系列が前後します。
開始直後、本戦問題を開くリンクを押してもリンク先が間違っていて何も起きない。URLを推測したら1発で当たった。
問題が長い。適当に読み飛ばしながら読む。
正の点数を得るにもそこそこステップが必要そう。仕事を受注して、仕事に社員を割り当てれば良いらしい。
仕事の納期に間に合わないと罰金があるので、仕事はこなせる分だけ受注しないと死にそう。
仕事の種類によって、得意な社員が異なるので、仕事に対して処理能力が高い社員を順に割り当てていき、期限ギリギリで終わるように人数を調整するという方針になった。
とりあえず色々な情報が手に入るgetinfoを叩いて情報をクラスにホイするプログラムを書いて、そこから点数を取れるようにしていく。実装がクソ重い。
第一世代プログラム
- 仕事がなく、かつ待機している社員が15人以上いれば仕事を1つ取る。
- 受注した仕事に対して、待機している社員から、その種類の仕事の能力が高い順に割り当てる。期限内に終わるようになるまで人数を増やす。
15人以上の待機を確保したのは、ある程度待機させた方が、来た仕事に対して高い適正のある社員が残っている可能性が高そうだから。
最初のプログラムを動かし始めた時点で既に一時間くらい経過していた。この時得られるポイントは最終的には8分の1になる。
大事な所だけを文章にすると短いけど実際問題を読んだり考察したりコード増やしたりを行ったり来たりしている。
最初のプログラムの効率が結構良かったらしく、前の順位表を見るといつの間にかランクインしていた。案外みんな大したことないのかとか、上位陣は潜伏して他のこと考えてるんじゃないかとか思った。
点数が得られるようになったので、仕事のデータなどをログに吐かせて考察する。
効率を上げるにはどんな指標が必要か考える。社員が50人と決まっていることを考えると、社員一人あたりの時間あたりの稼ぎ、つまり
(仕事の報酬) / (仕事にかかる時間) / (仕事に割り当てる人数)
が高いほど良さそう。
この値は仕事と、現在待機している社員のパラメータによって決まる。社員の割当方法は変更なし。今後この値を仕事の「指標」などと言うことにする。
指標は仕事が完了できない場合にはとりあえず-(罰金)としておいた。
ログを見るとこの指標は仕事によって大きく差があり、低いものは0.1未満、高いものだと0.7とかを超えた。
すると、仕事をせずに罰金を食らってでも、効率のいい仕事だけ取れば良いのではとなり、仕事を外注するというシステムがあるのでこれを利用したくなる。
仕事を取ってきて効率が悪そうなら外注にする。
また、効率のいい仕事を外注で見つけたらそれを割り当てる。
この方法で細かい試行錯誤をして次のようになった。
第二世代プログラム
- 外注されている仕事を見て、指標の最大値が0.6以上だったら即座にその仕事に社員を割り当てる。
- 外注している仕事が5つ以下かつ、待機している社員が15人以上いれば仕事を1つ取る。
- 受注した仕事の指標が0.2未満ならば外注する。0.2以上ならば社員を割り当てる。
これを実行してみると外注の仕事ばかり取ってきた。外注は宝の山だった。
ほとんど考察していなかった経験値や社員の挿げ替えについてはもう手遅れという感じだったので、方針はこれ以上変えられないという感じになり、このプログラムで最後まで走ることになった。
順位がみるみる上がっていくのを観測できた、そのうち2位になって、さらに1位になった。やったぜ。
ここからはパラメータ調整職人になった。主に外注されている仕事を取ってくるしきい値が大事っぽい。
しきい値を上げると社員の割り当てがあまり起きなくなり、暇な社員が増える。15人以上になった時は受注で暇な社員を減らしていたが、やはり受注は指標があまり良くなかった。
時間あたりの金の効率 >= しきい値 * 仕事している人数
みたいなことが言えるので、働いている人数との兼ね合いを考えてしきい値を調整していた。
ものすごい勢いで追い抜かれて2位になった。パラメータ調整職人しても追いつけそうにない。
どこで差がついたのだろう。やはり挿げ替えや経験値を序盤に見なかったのが痛かったか。それとも割り当てのアルゴリズムが悪かったか。
終了30分前くらいから、市場に出回る仕事の指標が高くなる傾向があった。
外注に手を出す人が増えたのでいい仕事を見つける可能性が上がったのか、ヤケクソで好条件で外注してる人でも居るのだろうか。
外注の仕事をもらうしきい値0.6は最後には1.5になっていた。
コンテスト終了。100850点で2位。
1位,3位とはそれぞれ1万点以上差がついた。終盤は順位は変わらないなあと思っていた。
表彰
こういうコンテストで壇上に上がるのは初めてでとても嬉しかった。あと緊張した。
最初にポイントを稼いだコツを聞かれるの、感想が言いづらくて厳しい。
これ顔出し配信じゃんって思ったけど、そもそも上位に居た時点でかなり映っていたらしい。
10万円の使い道は検討します。
その他コンテストについて
人によって応答が帰ってくるまで異常に時間がかかることがあったらしい。幸運にも自分は全くそのようなことがなかった。
難しいだろうけど出来るだけ不公平がないように運営がんばってほしい・・・
問題は面白かったです。なんか利益を最大化するために部下の使い方など手段を問わないブラック会社が生えた。
ただ問題の要素はもう少し少ない方がとっつきやすい気がする。
前準備してた話
表彰の時にも話した前準備のことです。
ゲーム終了直後の記念SSがこれです。ザ・Swingという感じ。
ぼくのかんがえたさいきょうのCODE RUNNER環境(クソ図でごめんなさい)
を実現しようと準備してました。
去年の本戦でプログラムを複数作って、手動で止めたり走らせたりしたという話を聞いてそれ良さそうだなあと思ったので、じゃあwindowsのタスクマネージャー的な物を用意してプログラムを一部だけ止めて差し替えたりとか色々できそうだなあと思ったのですが、そういうことに向いていそうなスクリプト言語の知識がありませんでした😇
実現したこととしてはプログラムやサーバーが止まったときに備えてデータをセーブロードしやすいように支度したり、グラフにプロットできるようにしたり、ログを出力したり、クエリを効率よく投げられるようにしました。
結果として本戦で便利だったのはログ出力・グラフプロット・クエリライブラリの3つでした。
ログは標準出力垂れ流しと大差ない気はしますが、Eclipseのウィンドウから独立してるのは良いです。
グラフプロットは分析やパラメータ調整職人の時に役立ちました。
クエリは種類ごとに時間を管理したり、自動リトライとか、エラー処理を入れてかなり快適な感じにしました。
並行プログラミングやGUIが役に立ったのでプログラミング第三(講義)に感謝🙏
コンテスト後
懇親会。2位なので調子に乗れる。
大体お昼食べたメンバーやキーキさんと固まる。
uwiさんと周りの人が話してたが、僕は顔を知らなかったのでチームラボの人だとしか分からなかった。
去った後に周りに聞いてみたらuwiさんだった。話しに行かないと。(使命感)
懇親会の半分以上の時間はuwiさんと話してた。
Java競技プログラマーの超強い人と話すのは初めてだったので、ライブラリのことについて聞いて色々知見が得られた。
ボクシングを出来るだけ減らすと速いらしいです。データ構造全部自前不可避。
No.310 2文字しりとり - yukicoderの素晴らしさを力説されるなと、Javaに関係あったりなかったりする話題で盛り上がったと思う。
紙ぺーぱーさん、すぎむさん、キーキさんとCOCOSで夜ご飯。懇親会でサンドイッチ3切れしか食べていなかったので助かった。
COCOSは初だったが普通のファミレスだ。立地の関係か人は多かった。
作問の話になった。
ぐるぐるツアーはクソ。(ハマったから過剰にdisります)
www.hackerrank.com
CODE FESTIVALの時からデータ構造を布教されているので次は平衡二分探索木を書かないといけない気がする。
新幹線でおうちへ。参加記を書く宣言をしていたので書く。クッソ時間かかった。
関係ないけど
yukicoderで12/25まで毎日問題が追加されるAdvent Calender Contestが今アツイです。
順位表→順位表- yukicoder
Adventar
www.adventar.org
僕の問題が16日,水曜日に公開されるので是非解いてください。
