phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

HACK TO THE FUTURE 2018本戦参加記

概要

まぐれで予選突破してしまい、こんな機会滅多にないと思うので、参加してきました。

future-contest-2018-final.contest.atcoder.jp

普段、会場の情報とかつぶやいてくれる人とかありがたいと思っていたので、今回はできるだけつぶやくようにしてみました。(鬱陶しくツイートしててごめんなさい)

起床~移動

  • 前日yukicoderちょっとだけ出るつもりがガッツリでてしまい、寝たのがAM2時過ぎ
  • ちょっと緊張してたかAM8時の目覚ましで起床AC
  • たまたま入場がagwさんと一緒になった

準備

  • 会場がどんな雰囲気でやるのかわからなかったけど、大きめテーブルに2人ぐらいずつ座れる感じでゆったり
  • agwさんとmachyさんの後ろ側の席に陣取る


コンテスト開始

  • 問題読む
    • 50x50マスにいくつかの操作を行える
    • 操作は、植物を植える、収穫する、更地にする、道路を設置する、など7種類あり、それぞれ見合ったお金または労働力が必要となる
    • 植物は植えると、すでに植えられたマスには植物数が+1し、さらに勝手に隣接の更地マスに広がっていくが、マス内の植物数が100になると岩になってしまう
    • 植物の収穫数最大となるような1000ターンの操作列を出力せよ
  • 問題かなり複雑じゃないですかね・・・8時間コンテスト・・・?
  • 実際のビジュアライザとかの動き見ながら40分ぐらいかけて理解(遅い)

最初の考察フェーズ

  • 雰囲気的に、普通の畑みたいに区画に分けたいお気持ちになる
  • ということで大雑把には「サイズXの区画を増やす、区画内の収穫をする、他の操作、についてビームサーチする」を目指したい
  • 区画は、正方形とかだと移動コストが微妙にかかってしまうので、できれば1*Nか2*Nぐらいの長方形がよさそう?
  • 区画内を一気に収穫する想定だけど、収穫後にもう一度植える必要があるのは1手無駄してると思う
  • 道路を引くかワープ設置するかとか、道の設置のうまい方法とか考えつつ、お昼

  • お弁当用意していただいていた

「貧乏フェーズ」

  • 問題の制約をよく見ると、お金の初期値が100しかない
  • これは結構ギリギリな金額で、区画を作りたいと考えていたけど、結構厳しい
  • 「貧乏フェーズ」と名付けておく
  • 逆に、貧乏を脱出したら打てる手が増えるので、別戦略が必要そう
  • 「小金持ちフェーズ」と名付けておく
  • 状態の評価値はここら辺分けておきたい

折り返し地点

  • とりあえず、ビームサーチしたいと思ったけど、いざ実装しようと思ったら実装がだいぶ重い
  • この時点で実装の大変さが原因で途中まで書いてたコード捨てるの結構厳しい・・・
  • 0点で終わるよりはと思って、厳密さよりも動くコードを優先することに

貧乏フェーズの実装

  • できるだけワープ近くで、かつ、お金がかからないように1マス区画を作るのが最初にやることかなと思い、考える
..R..
.RxR.
RxWxR
.RxR.
..R..

R: 道か岩
x: 栽培区画
W: ワープゲート
  • ↑みたいな感じで、ワープ横に栽培区画を作ってそこで99まで栽培を行えば、100ターンぐらいで400植物ぐらいが手に入る
    • もちろん途中収穫などうまくできるとよさそうだけど、ここでは99まで栽培を考えてた
  • 市松模様的にもうちょっと広げて上げると多少スコアも上がるので、それを書く
  • 収穫とかと区画の作成とかを同時にタイミングを気にしながら手順を作る実装が地味に難しい
  • 貧乏フェーズの手法のまま最後まで行った場合のコード、ちょっと変形して別な場所にワープゲートを設置してそちらでも同じことやるコードを書く
    • 最終提出のコードはこれ

小金持ちフェーズの実装

  • 貧乏フェーズでは1マスごとにやってしまっているので、1回あたりの収穫量が少ない
  • 単純に拡張するとマスのサイズを広げてあげたい
  • この時点で、残り時間が3時間もない
  • standingみるとかなりやばい点数が出ている
  • 貧乏フェーズのコードは手元の見積もりで170万ぐらいだけど、1ページ目にも入れていない・・・
  • 「小金持ちフェーズ」だけでなく「大金持ちフェーズ」ぐらいが必要そう・・・

standing凍結(残り1時間)

  • とりあえず0点は避けたいので、↑の貧乏フェーズの手法の実装を投げて177万点
  • あとはどこまで実装しきれるか・・・
  • うおおおおおお
  • とにかく動けばいいやと書きなぐっていたら実装がバグりまくる
  • デバッグが「出力→ビジュアライザ」しかなくて効率がだいぶ悪い
  • 結局実装しきれず終了

  • さすがに8時間ぶっ続けでやった後の疲労感がすごいのと、不完全燃焼感がすごい

会社紹介

  • Futureの会社紹介と脆弱性検知ツール「Vuls」の開発者の方の技術紹介とか

https://thinkit.co.jp/article/10092

  • ミャンマー?から帰国したばっかりらしい
  • 他の社員の方で技術書出されている方とかもいらっしゃるよう

懇親会

  • やっぱり決勝は予選と違って「最上位(1~10位)の順位決定」をする必要があるので、問題が難しいとのこと
    • TCO finalなイメージ、らしい
    • それでもオープンも含めかなり高いスコアをたたき出している人が結構いて強い
  • あとは、参加者のプロな方やFutureの方などいろんな方とお話しできてよかった
    • 普段はstanding上位やツイッター上でしか見れない方ばかりで恐れ多い(((((((;´д`)))))))


  • 順位発表
  • 3位以上はビジュアライザ見ながら発表
  • やっぱり上位は盤面全部を使い切ってる感じですごい
    • それにアプローチが上位でも多様で良い問題感ある
  • 最後、なんと副賞や参加賞も追加で用意していただいていた(!)
  • 集合写真とって解散

反省


  • 出来は散々だったけど、楽しかった!
  • やっぱりこういうイベントに参加できるとだいぶ競プロモチベは上がるなぁと思った
    • イベント開催ありがとうございました
    • アルゴリズムもマラソンもへぼいので、もっといろんな問題解いて強くなりたい
  • 実装難易度や実装の仕方、書き方とか気を付けるようにしたい