CODE FESTIVAL 2015参加記

CODE FESTIVAL 2015に参加しました。非常につらいのと楽しいのとが混在していて複雑な気持ちです。

予選A

D問題を10人もACしていないうちに書き終わったので「余裕だぜー!」と提出したところWA。
結局7WAの末1時間後にAC。98位でなんとか予選通過。つらい。

予選B

D問題はsetっぽいと思いつつも、予選Aで通過確定してたので動的セグメント木で頑張ってみようとする。→75点
動的木で100点は無理っぽいと判断したので想定解(多分)に路線変更して、70分ほどで全完。35位。(実は動的木で通してる人もいた)

前日

本戦に持って行くPCの設定をしていてyukicoder不参加。 開始1時間後ぐらいの順位表だけ見てみたけどとてもつらそうでした。
午前1時ぐらいに就寝。

1日目

午前4時ぐらいに起床。7時に起きる予定だったけど微妙に目が覚めてしまったので仕方なく起きる。
六本木一丁目駅を降りて泉ガーデンギャラリーへ、向かうはずだったのにいつの間にかスウェーデン大使館にたどり着いて焦る。
何とか本戦会場に到着。ぼっちを演じるなどして時間をつぶす。

本戦

4完(ABCE) 168位/198人。 パーカーを得られず。

  • A やるだけ。AC。
  • B 考えるのが面倒でDPオーバーフローをやらかす。小さいケースだけ出力して法則を確認。AC。
  • C 貪欲っぽいけどDP? いや、フローでいける。とネタとシャリを二部グラフにして流してAC。
    このあたりで自分の調子が悪いことを自覚する。 Cでフローが出るわけないというのに……
  • D 少し考えてわからなかったので飛ばす。
  • E '!'で状態がつぶれるとか色々場合分けをして提出。 AC。
  • D 区間スケジューリングを考えたり、union-find貼ったりとか色々迷走する。
  • FよりGの方が正解者多かったのでGを見る。 区間区切ってほげほげってのは見えてたはずなのに区間DPの発想には至らず。飛ばす。
  • D よくよく考えたら区間加算と区間maxの遅延評価セグメント木で殴れそうなことに気付く。想定解ではないだろうけど。
    手元の遅延セグ木を貼り付けて少しいじるもバグる。そもそもライブラリの遅延セグ木の使い方を忘れている(N度目)。
    ググって出てきたkagamizさんのStarry Sky木を貼り付けるも、コピペしたコードのグローバール変数にある n を設定しておかなければならない点を見落としていて、何をしても出力が 0 にしかならなくて悩む。
  • コンテスト終了。 n の存在に気付いてコードを修正。終了10分後にDをAC。

昨年も参加しましたが、昨年より解ける問題の種類は増えているはずだし、 AtCoderのコンテストで1ページ目に食い込めることも増えていたので、 「50-70位ぐらいには入って、あわよくば沖縄ツアーだぜウェイ」と調子乗っていたら、 まさかの去年より順位を落としたうえ、参加者の8割が得ていたパーカーを得られませんでした。(去年は144位)
非パーカー取得者で topcoder algorithm rating 最高な気がする……。
主にリクルート社関係のコンテストでオンサイトのプロコンに何度か参加していますが、 毎度オンサイトはボロボロです。主に寝不足が原因の集中力不足のせいだと思うけど、案外緊張でもしてるのかしら……。

本戦後

CODE FESTIVALはプログラミングコンテストではなくお祭りなので本戦なんて飾りです。 パーカーも箪笥の肥やしにしかなりえないのです。と、自分を納得させて寿司食ったりトークライブを見たりするなどして過ごす。sugim48さんやsigma425さんのtopcoder作問話を聞いたりもした。 生の匿名先生はレアキャラらしい。
落ち着いて食事できる場所がなくて大変だった。

エキシビション

解説を小耳にはさみながらAに挑戦する。 最大流+SCCっぽいというのはまぁ問題を見てすぐに使いそうだなとわかるけど、ちょっと試しに書いてみてもサンプルが合わない。 諦めてエンターテイナーyosupoさんのおもしろ芸を眺める。
→ 後日ちょっと考えたらACしました。

1日目終了

リレーチームの顔合わせ。 twitterとかコンテストで見かける人が沢山。 自分も認知されてるみたいで少し嬉しい。
バスに乗ってホテルへ。バスで隣に乗ってたkenkooooさんとroitiさんが色々話してるのを盗み聞ぎするなどして過ごす。
ホテルの廊下めっちゃ長い。 ポット用のお湯を取りに行くのが大変で、用意してきた茶葉を使わなかった。 あと湯船めっちゃ狭い。
1時ぐらいに寝る。


2日目

6時に起きる。
バスに揺られて会場へ。

あさプロ

168位なのでeasyに参加する。 easyで無双する予定だったのに、easy参加資格が101位~とかで結構激戦区だった。

  • A sqrtを使うも、double型のまま乗算しててWAを生やす。intでキャストしてAC。
  • B 奇数のとき全てのアルファベットが同じならOKとかいう謎理論を考える。コード書いてからサンプルを見てそんなものはないと気付く。時間かかるもAC。
  • C 二分探索をする。 AC。
  • D 制約も小さいので分け方をn通り試して、LCSをしようとするが、LCS長×2を残せるのに、×2を忘れていて時間を溶かす。 AC。
  • easyは11位。
  • middleの A/B はeasyの C/D なので取りあえずコピペ。
  • middle C 貪欲感あったけど、DP書いてもそんなに時間かからなさそうだったから慎重にDPを書こうとする。
    dp_left[i] := i番目の石の集合の左側をi番目の石と同じ色にするのに必要なコスト、 同様に dp_right[i]。
    ここで頭が付いていなくて、最終的に全部白くなるのを全部黒くしようとしていて、奇数位置(0-indexed)だけを見るようにしていたためサンプルが合わない。(本来は偶数位置のみを見るべき)
  • 結局ここで詰まって時間切れ。middleは81位。
  • 表彰のときにkenkooooさんが「twitter見てます」と話しかけてくれた。

  • 後日middle Dを解くも強実装な方針だったため、Cで時間潰さなくても時間内には提出できてなかったかな。

詰まった時点で貪欲を試しに投げたりとかすべきだったかな。 本戦のリベンジで、 easy で1桁順位 かつ middle でも上位入賞が目標だったけどどちらも達成できず。 ここらでタンブラーをあきらめる。

リレーまで

駐車場で昼ご飯を食べたり、太鼓のプロを見たり、謎クイズを見たりして過ごす。

リレー

チーム△K
168位なのでCを担当。
一瞬見てヤバ気な問題だったけど、'0'はサンプルにあったし、他の数字も覚えている範囲の円周率を書きだしたらすぐ見つかったので大丈夫。念のためacos(-1)を出力して、文字列の何番目かを出力するようにした。AC。
と思いきや、PCを閉じたときにブラウザがオフラインモードになってしまったらしく、コンテストページにつながらなくて焦る。めっちゃ汗出た。ブラウザを開きなおして提出。AC。
暇になったので他の人のを手伝おうとするも、手伝い始めた30秒後とかに順番が回って来て、問題を把握する前にみんな続々とACしていく。
H問題で詰まってしまったらしいので問題をチラ見するも、(僕が問題を勘違いしていて)みんなが何を言っているのか分からなかったので不用意に口出ししないことを心の中で決める。
皆の協力の末無事AC。やったぜ。

リレー後

ハッピーアワー。お酒とかは出てこない。
色んな人の話を聞く。コンテストは自宅から参加できるのでむしろこっちが大切。
疲れが結構あったので、そのまま直で帰宅。南北線の車両にmayokoさんを発見したりした。
お疲れ様でした。


TCOの日本オンサイトのときとか、コンテスト前後に時間の余裕があって色々交流できたので、 もう少しコンテンツ減らしても十分楽しいかもしれない?