HACK TO THE FUTURE 2019 本選参加記
概要
20卒枠で予選通過(73 位)したので参加してきました。
slack, git, (twitter) にコンテスト中のログを残していたので時系列で参加記を書きます。
質問などあればコメントか twitter にお願いします。
前日
交通費・前後泊宿泊費が出るので前日入り。
金曜日は4限まで計算機科学実験及演習4*1 があるので 19時頃の新幹線で東京に向かいます。
夜飯は北品川周辺で Md*2 と餃子定食を食べました。
RELEASE THE SPYCE 8 話を見て就寝。
コンテスト当日
目黒川に沿って歩き、大崎駅 ThinkPark Tower を目指します。
topcoder の衣類を着ている人を見てビビるなどする。
受付でTシャツでない衣類(HTTFパーカー)を受け取り、適当な場所に座ります。
コンテスト開始(10:30)
問題概要
- 1000ターンでモンスター「高橋君」を育成し、最終的な所持金を最大化する
- 実行できる行動はアルバイト、「高橋君」のスキルトレーニング、討伐の3種類
- 討伐には基本報酬額、要求スキル、受注可能期間が定められている
- 「高橋君」のスキルレベル、受注ターンにより実報酬額は(指数的に)変化する
とりあえずビジュアライザで遊びたいので毎ターンアルバイトをする自明解を提出(11:00)
最初に考えたこと
- あるスキルのレベルが1上がるだけで実報酬額は倍になるので、レベルを0から1にするだけでもかなり報酬が増えるはず
- 基本的にアルバイトするよりは各ターンで報酬額が最大の討伐を受注する方がお得
- 重実装も無さそうなのでとりあえずシミュレータを書きたい
最初の 200ターンでアルバイト、次の10ターンで各スキルレベルを0から1にする、以後はその時点で報酬額が最大の討伐を実行するコードを提出(11:20)
この時点でシミュレータは完成していた。
スキルレベル強化が偉いと分かったので、ランダムにスキルを選びトレーニングが可能なら実行、そうでなければ討伐を実行するように変更し提出。得点が100倍になる。完全に調子に乗る(11:30)
完全に理解したので1位です #HTTF
— ざき🍆 (@zaki_joho) December 1, 2018
考えたこと2
- そもそも序盤からアルバイトせずに討伐を受注すればいいのでは？
- トレーニングはスキルレベルが上がると指数的に費用が増加するが、スキルレベル上昇による報酬額の増加はそれを上回るっぽい
ここらで人々の得点が爆発し、順位表が壊れる。表示得点のデノミが行われた。
【お知らせ】ドラゴンボール感を出し過ぎたので点数を1/10000にしました。 #httf
— chokudai(高橋 直大) (@chokudai) December 1, 2018
アルバイトをやめ、最初からトレーニングor討伐受注を行うように変更し提出。また得点が100倍になる。(12:20, 101631938.31 points)
この時点では余裕の一位だったので調子に乗ったまま昼食へ。エビチリ弁当を選択。
カフェスペースには PC 持ち込み禁止だったので解法を考えながら完食。
実行結果をビジュアライザに投げると意図していない行動を取っていた(無効な行動をしていた)。討伐が受注可能か確認する部分がバグっていたので修正し提出。(12:40, 133646794.66 points)
考えたこと3
- 現状では各ターンで報酬額が最大の討伐を選択しているが、これは締切ギリギリに受注した方が報酬が増えることを考慮していない
- 討伐が「短期間」「中期間」「長期間」に分かれていることを考慮していない
- 締切ちょうどに討伐を受注すると報酬が10倍になることを使いたい
- 全スキルレベルがMAXになる前後で行動決定ルーチンを変えるべきでは？
以上の考察から
- スキルレベルがMAXになるまでは可能な限りトレーニングを行い、所持金が足りなくなった場合は締切が比較的近い討伐の内で報酬額が最大のものを選択。
- MAXになった後はそのターンで締切を迎える討伐を選択。
に行動決定方法を修正。kurenai3110 さんを抜いて1位になる。(14:00, 316193686.45 points)
トレーニングの際、どのスキルレベルを上げるかは毎回ランダムに決定していた。
乱数の引きによって1割ぐらい得点が上下することが分かっていたので試行回数を稼いで最終所持金が最大となるものを出力する方針に変更。この時点では1試行あたり150ms 程度かかっていた。
高速化のためにやったこと
- vector を可能な限り生配列に変更
- 討伐を B[i] ごとに分類・基本報酬額でソートして保持
- 最良の行動を string で持っていたのを pair<int,int> で持つように変更
- 報酬額を前計算
150倍速くなって1000回程試行回数が稼げるようになった。
スコアも上がって3.4 億点(16:00)
しかしこの時点で4位ぐらいになっていた。上位陣とは1割近く差をつけられているので割と焦る。残り2時間半で何ができるだろう…
最後に考えたこと
- スキルレベルがMAXになるまではその時点で報酬額が最大の討伐を選択しているが、これは最善ではないはず
- どのスキルレベルを上げるかはランダムに選択しているが、これも最善ではなさそう
- (サンプルケース埋め込み………)
ここで体力が尽きて地蔵になり、ビジュアライザで遊ぶ人になる。
たまに小さな修正をして乱数に祈るなどしていた気がする。
上振れを引いて最高得点を更新。これが最終得点になります.。（は？）(16:30)
standings 凍結(17:30)
この時点で5位だった気がする。
既に完全に頭が寝ていたので乱数に祈ったりカフェスペースでコーヒーを飲んだりして時間を潰す。ICE COFFEE ボタンを押したらホットコーヒーが出てきた。
コンテスト終了(18:30)
近くの赤い人達が bitDP とか最小費用流をしたみたいな会話が聞こえてくる。本当に同じ問題を見ていたのだろうか・・・
会社紹介(18:45)
- ツカモさんとナカモさんが出てきて Loppi の話をしていた気がする
- ほとんど寝てました・・・ごめんなさい・・・
- 競プロer 激推ししてるらしいです
懇親会(19:00)
酒と肉とピザが出た。ビール一杯で終了。合鴨のロースが美味しかった。正直眠すぎて懇親どころではなかった。
結果発表(20:00)
ここで凍結されていた順位表の最終結果発表。
5位から1位、その後6～10位の受賞者が発表される形式。
9位まで名前が呼ばれず、それはそう。(ラスト2時間寝ていたため)
しかし、10位で名前が呼ばれました。マジか。賞金 ￥10,000 を頂きました。
賞金貰いました！！フューチャーアーキテクト株式会社さんありがとうございます！！！#HTTF pic.twitter.com/m3QeukBY4F
— ざき🍆 (@zaki_joho) December 1, 2018
表彰後は初めてお会いした同大学のてんぷらさんやツカモさんに声を掛けていただきました、ありがとうございました。
最後に記念撮影をして参加賞を受け取って解散。エントランスは既に閉まっているので裏口を通って帰ります。
感想
初めて参加したマラソンコンテストで賞金を貰えるとは思っていなかったので本当に嬉しいです。*3
大半の人がコンテスト終了直前に得点更新していたことに驚きました。人々勝負強いですね・・・
会社サイド全面バックアップといった印象で、F社の好感度が上がった。イベントを開催していただきありがとうございました。
2年後も新卒枠になっているはずなので(コンテストがあれば)是非参加したいです。(ツカモさんお願いします！！)
反省
- 予選も最後3時間地蔵だったし、本選も最後2時間地蔵だったし*4、マラソンのために体力が欲しい
- トレーニングを行うスキルをランダムに選んでいたが、ここで焼きなましをすると良かったらしい(焼きなましするには試行回数が足りないと思っていた)
- 中盤にある特定の討伐を目指してスキルに指向性を持たせると良かったらしい
- 上記の2点と重複することだが、数ターン先読みして行動決定するべきだった
- 序盤でバグらず1位をキープできていたのはえらかった
コンテスト翌日
完全に寝過ごしてフロントからの電話で起きるなどした
スヤスヤしてたらフロントから電話かかってきて追い出された
— ざき🍆 (@zaki_joho) December 2, 2018
Md と再合流し、春日亭で油そばを食べる
帰宅(19:00)
順位ボードを持って帰ってきてしまった
