読者です 読者をやめる 読者になる 読者になる

CODE FESTIVAL 2016 参加記

時系列順に書いていきます。

1日目

到着

11:10頃到着した。知り合いが結構いた。

本戦

本戦は3時間(12:30 - 15:30)であった。4完(A,B,C,D)2半(E,H)の計2,700点(54位)でパーカーを取得した。以下簡単に時系列順にコンテストの進め方を書く:

  • 0h00m - 0h30m (12:30 - 13:00)
    A,B,C,D問題を解いた。(+1500)
  • 0h30m - 1h00m (13:00 - 13:30)
    最初の15分でEの部分点を通し(+500)、残り15分で満点解法を考えていた。それでもわからなかったので後回しにして、別の解ける問題を探すことにした。
  • 1h00m - 1h40m (13:30 - 14:10)
    Hを考察し、部分点を手に入れた(+700)。
  • 1h40m - 2h10m (14:10 - 14:40)
    Gが解けそうだったので解こうとした。自明な解法(queueに枝を突っ込んでKruskal)をやってみたがTLEなどで落ちたので断念した。
  • 2h10m - 3h00m (14:40 - 15:30)
    Eの満点やFを解こうとした。Fの考察について、dpでやりそうだということは分かったが、indexについてかなり長い時間試行錯誤*1を繰り返したので、時間がかなり取られてしまった。正解が分かった時点では残り時間が10分程度しかなく、そこからバグなく実装することができなかったため、Fは正解できずに終わった。*2 *3

11/28追記: 提出一覧f:id:koba-e964:20161128130513j:plain

11/28追記: 終了後に高校で同期だったyurahunaに遭遇した。高校の同期であったことはこの時初めて知った。東京に来た地元の人間は相当稀なので嬉しかった。

夕食・自由時間

今年の夕食はケータリングだった。*4

自由時間は割と暇を持て余しがちだった。将棋AIのトークを聞きに行って、そのあと学科同期の人たち*5で集まってボドゲで遊んだ。

Exhibition直前に太鼓の達人をminus3thetaと一緒にやった。曲は知らなかったのでminusに選んでもらった(マリオワールドのむずかしいだった)。一応合格できたが疲労で死ぬかと思った。minusがうまかった*6

Exhibition

強い人が強いことをやっているなぁという印象だった。色々思うところがあり*7、それとなく聞き流しながら一人でfinalの復習をやっていた。

Team Relay (Introduction)

チームリレーの顔合わせ、自己紹介をやった。私たちはTeam Dで、海外勢はFatalEagleで、日本勢はHuziwara, kobae964, siotouto, ei1333, beet, dolicas, zeptometer, ioryz, haradukaの9人だった。
英語の練習をするためにFatalEagleに話しかけようとするも、緊張のあまりろくに話せないという事態になってしまった。

宿泊

イベントが終わって全員帰宅かホテルに向かうという形になった。今年はホテルがバラバラなようで、ホテルへのバスは出ず自分で歩いていかなければならなかった。*8

2日目

朝プロ (Elimination Tournament)

3回戦まで行くも敗退。

  • 1回目 (group11)
    A 500, B 100の計600点で通過。
  • 2回目 (group11 + group12 -> group06)
    A 700, B 200の計900点で通過。Aはよくわからなかったがサンプルケースからエスパーして通った*9ので一人で爆笑していた。*10
  • 3回目 (group05 + group06 -> group3)
    A 200, B 400の計600点で脱落。通過したかったらAは700点取る必要があった。

また自由時間

筋力: 17ptくらいしかとれなかった。前屈+10cm, ジャンプ36cm*11, 握力36kgf, 背筋120kgf。
LT: chokudaiがハンドスプリングをやっていて強かった。

Team Relay

作戦タイム

まず、11問の問題に対して10人のメンバーなので、2問解く人間を決めなければならなかった。スタッフの方から「チーム内でチーム内順位3位以下の人」が2問解くという説明を受けたので、チーム内順位3位の私が2問解くことにした。
次に、10人のメンバーを3つのクラスタに分け、それぞれのクラスタに問題を割り当てた。*12 割り当ては以下の通り:

  • A,B,C,D,E
    dolicas, zeptometer, ioryz, haraduka, kobae964
  • F,G,H
    siotouto, ei1333, beet
  • I,J,K
    FatalEagle, Huziwara, kobae964
本番

チーム内全員の動きを把握していたわけではないので、細かい動きは分からないが、私たちのチームは非常によく戦い、2位になった。
私の動きは以下の通り:

  • 最初
    Eを読んで即*13解法を思いつき、haradukaがAを解き終わった直後に実装してEを通した(07m04s)。
  • 中盤
    Iをやることにして、簡単な解法を思いついたので行ったものの、コーディングスペースで間違いに気づき、WAをもらった(nが奇数の時にしかうまくいかない解法だった)。11/28追記: FatalEagleがJ問題の解法を思いつき、そのアイデア*14の素晴らしさに感服した。またHuziwaraFatalEagleがK問題を頑張って考察していたが、私はこの手の問題が苦手で全く貢献できなかった。
  • 後半
    他の人のアイデア*15を使って、n=2のときはダメで、それ以外のnについて具体的に解を構成する方法を見出した。*16 焦っている中でのdfs解法なので実装に手こずりそうだった(し実際にWAも3回出した)が、Huziwaraによる的確なデバッグにより見事AC(71m27s)して2位になった。

11/28追記: スコアボードf:id:koba-e964:20161128130145j:plain

インタビュー

私がIを通してチームが2位になった直後、カメラマンがインタビューに来た。なぜか私が感想を聞かれることになったが、緊張のあまり(日本語なのに!!)ろくに聞き取れず返答もままならない、という醜態を晒すことになった。

aftermath

テンションが上がりまくっていて、極度の疲労状態になり、足腰もガタガタという状態が全完後1時間くらい続いた。FatalEagleが他の(全完した)チームの人と話したいと言ってきたので、スタッフの人に尋ねてみた。*17 またFatalEagleに「この"3y3s"の意味わかる?」と聞いたら、「"eyes"のことで、問題番号の"I"とかけているのでは」という答えをもらった。*18

表彰

1位のチーム(50分程度で全完した)が表彰されているのを見てすごいなぁと思っていたら、2位のチームも表彰される*19ということになって、足腰ガタガタのまま壇上に上がった。Best Collaborator Awardのマグカップをもらったが、手が痺れて落とす危険性が高かったので後ろの人に持ってもらった。もしかしたらまたインタビューされるかもしれないと思って何を言うか少しだけ考えたが、その予感は的中してしまい、感想を言うことになってしまった。qnighyへの対抗意識からせっかくの機会なので英語で以下のようなスピーチをした(文法的にヤバい場所は赤で、可能な改善点は青でハイライトしている):

EVERY ONE of our team worked very well*20, and our team worked quite well together*21. I couldn't be prouder to*22 compete and enjoy with every other people*23 in this*24 team.

翻訳:

(通訳の方、駄文で本当に失礼しました…。)
そのあとはいよいよ足腰がやばくなって来たので座ったりした。

Team Relay 総括

上に書いた通りである。

帰路

学科同期とセイクで優勝した
11/28追記: そのあと汐留駅のイルミネーションを見た。雨だったのが残念だが、こういうところに恋人と行くとロマンティックなんだろうなぁなどということをぼんやりと考えていた。

総括

とても楽しかった。特に問題を早く解くことは苦手なので、朝プロは良い練習になった。また英語で話すのも苦手*25なので、練習の機会としても絶好の機会であった。

まとめ

関係者の皆さん、本当にありがとうございました!!!

*1:[現在の移動の数]に加えて、[今まで見た頂点の数] -> [今まで見た頂点の数][番号最大の頂点から戻れる頂点番号の最小値] -> [今まで見た頂点の数][頂点1に戻る道のある頂点の番号の最大値] という順番で考察した。最後のは正解

*2:自分の実装力の低さ、Gと戯れていたことに対する後悔などで精神がズタボロになっていた。

*3:事前に順位表を見てqnighyがE,Fを通していたのは知っていたので、Fを通して勝ちたいと思ったが、間に合わなかった。

*4:去年はチケットと自分の好きな食事を交換する形式だった。遅く行っても(選ばなければ)食事は残っているだろうと思って遅めに行ったら、そもそも食事が残っていなくて辛い思いをした。

*5:kw_udon, zptmtr,minus3theta

*6:確か200,000 < 私のスコア < 230,000 < 270,000 < minusのスコアだったと記憶している

*7:この時点ではまだfinalの結果が思わしくなかったことについての傷が癒えていなかった。

*8:一概に悪いとも言えなくて、ホテルから会場に向かうのにバスを使う必要がなく、寝坊してもある程度はカバーできる。

*9:ceil(x/2) / pはエスパーしようと思えばできる。

*10:あとで周囲に聞いたら、期待値の線型性などを使うと簡単に答えが導出できるということが分かった。

*11:モヤシなので体力がなく、とくにジャンプ力が弱い

*12:去年の私のチームのやり方と同じである。

*13:11/28追記:よく考えて見ると、少し詰まって5分くらいかかったので、「即」ではなかった。

*14:3行ごとに1行全て埋める + 周囲を埋める

*15:n=2kのケースはn=kのケースに帰着できる。11/28追記:zeptometerらが思いついた気がするが、記憶がはっきりしない(すみません…)。

*16:n=4の時はad-hocにつくる。

*17:OKだが、解法を話すのはやめてほしいということだった。

*18:実はこれは某音ゲー由来だということを、帰宅してから知った。

*19:Best Collaborator Award

*20:考え直したらhardの方がそれっぽい

*21:acting as oneなどという表現も使いたい

*22:proud to Vは〇〇できる(現在)ことを誇りに思うので、"prouder to have competed and enjoyed"の方が良さそう、だけど話している間にそんなことを考えるのは無理

*23:all the other membersなどがよい

*24:ourの方がよいかなぁ

*25:他人より苦手とは言ってない、残念ながらこれでもかなりマシな方らしい