はじめに

こんにちは、@kakira9618 です。

この記事は CCS Advent Calendar 2018 の1日目の記事です。

内容は、2018/11/25 に開催された「CODE THANKS FESTIVAL 2018」の参加記です。

CODE THANKS FESTIVAL とは

CODE FESTIVAL と CODE THANKS FESTIVAL は、Recruit社とindeed社が主催する競技プログラミングのオンサイト（現地）のお祭りです。

詳しくは公式サイトを参照してほしいのですが、オンサイトでのプロコンだけでなく、ビンゴゲームや懇親会など、さまざまなコンテンツがあり、とても楽しそうな企画となっています。

毎年9月～10月ごろに、CODE FESTIVALの予選がオンラインで2～3回開かれ、どれかの予選で上位の成績を取ると、その成績に応じて CODE FESTIVAL もしくは CODE THANKS FESTIVAL に招待されます(各FESTIVALごとに、100人ずつ招待されます)。参加は無料です。

オンサイト参加者はTシャツがもらえる他、フェス中のコンテストの成績や、その他のコンテンツの結果によって、さまざまな賞品（パーカーなど）がもらえます。

例年は、予選に参加できなかったり、成績が足りずに参加できなかったのですが、今年はうまく滑り込むことができた¹ので、そのレポートを書きます！！

私について

今年に入ってから競技プログラミングを本格的に始めた情報系学生（M2）です。

B2のあたりからACM-ICPCに参加する（国内予選敗退）など細々と競技プログラミングをやっていました。。。

現在(2018/12/01現在)、AtCoderでのレートは1650で、青コーダーです。Topcoder, Codeforcesも青なので、とても真っ青コーダーです。

Twitterやっています。もしよければフォローお願いします！（飯テロを高頻度で行う（？）ので、ご注意ください）

前日

前日は、「第5回ドワンゴからの挑戦状予選」があり、
3完217位(レート+44) で少し興奮していた（？）ため、よく眠れませんでした・・・²
良い子のみんなはしっかりと寝ましょう。

コンテスト前

11:00ごろに会場到着。「東棟」と書いてあるのに自信満々で「WEST棟」の方に入って10分溶かしました。

迷子検定1級をもつ私の方向感覚をもってすれば、東棟と聞いて何の疑いもなくWEST棟に入って10分を溶かすことが出来る
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

会場到着後、交通費の精算手続きをして、席について、誓約書のサイン、Wifiの設定、AtCoderの設定を済ませる。
大多数の人は既にもう来ていて、懇談してたりしていたので、もう少し早く到着すれば、と後悔しました。。。

設定を済ませるとすぐにお弁当の配布が。3つから選ぶのですが、1つは「叙々苑」のお弁当（焼肉定食）でした。

焼肉げと #code_festival pic.twitter.com/nrPiKRKBs4
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

しかし、コンテストがあと10分ほどで始まるため、叙々苑弁当はコンテスト後に食べることになりました。

3時のおやつです(叙々苑) #code_festival pic.twitter.com/jo6p5ZNwfG
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

また、パーカーのボーダーは上位50位以上とのこと。デスゲームだ……

上位50位にパーカー進呈 #code_festival
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

パーカーゲットできるように頑張るぞ！！　と意気込み、コンテスト開始！

コンテスト

こちらでは、コンテスト中の様子を時系列でお届けします。
解いた問題はこちらです。

12:00 ～コンテスト開始～　＆　A問題閲覧。
- 1問目->2問目の順で解いた場合と、2問目->1問目で解いた場合で場合分けすれば良さそう。
- 配点が $B\leq D$ になっているのを使ってないけど本当にそれで良いの？
- まぁ大丈夫そうかな、Aだし。
- 途中変数を書き間違えつつ、書き終える。提出。結果は見ずにBへ。
12:03 B問題
- 2つの操作をペアにして考えるのかな？
- ペアにすると両方とも4つずつ消費できる
- それなら4で割ったあまりが1:3もしくは3:1になっていればOKかな？
- 書いて提出-> WA. A問題はAC!
- う～ん、int -> long longになおして提出 -> WA.
- ああ、ペア操作ができる最大回数は $\min(X/4, Y/4)$ 回じゃん。提出 -> WA.
- えっ！？（ここで冷静になる）
- そうか、ペア操作回数を全て試さなきゃダメなのか。う～ん、TLが微妙・・・
- 紙を使ってなかったことに気づいた。とりあえず連立方程式を立ててみることにした
- 操作1をA回、操作2をB回行ったとして式を整理。普通に解けそうなので普通に解く。
- 割り切れるかどうかと解が有効であるかをチェックする回答を書く。提出 -> AC!
12:12 C問題
- ああーこれどこかで見たことがあるなぁ・・・³
- とりあえず入力＆ソートを書く
- $A_i$ と $A_{i - 1}$に囲われた区間は$O(N)$個しかないので、ここの長さが合計で何回足されるかを考えれば良い
- これは($A_{i-1}$より左側にある区間数 + 1)*($A_i$より右側にある区間数 + 1)で求められる。
- 後は実装するだけ。オーバーフローに注意。-> AC!
12:17 D問題
- う～ん……（3分考える）？　うん？　簡単じゃない？
- できるだけ貪欲に区間をつなげるやつを書く。 -> AC!
12:23 順位表を確認。ココらへんで37位くらいだったはず。パーカーを取る(50位以上)ためには、もう1問は必要だろう
12:24 E問題
- 明らかにDP感
- 状態はどうもてば良い？普通にdp[i][j] := 数字iだけがj個あるような状態（と等価な状態）の場合の数で良さそう⁴？
- 良さそう。jはどの辺まで必要かな？
- 一瞬ヤバそうな気がする（指数的に増えていくような気がする）が、よくよく考えたら $600(=300\times 2)$ を超えることはなさそう
- 遷移を考える。dp[i + 1][j] に行けるような前の状態を考えると、kを数字i+1を書く個数として、dp[i][(j - k) * 2]となりそう。
- 計算量は？300*600*300くらいだからまぁ大丈夫そう。
- 準備が整ったので書く。サンプル2が合わない（5が出力されてしまう）。（12:35ごろ）
- dp表をダンプしてみるが、正常そう
- 手動でサンプルを試す。ん？？5が正解じゃないの？？？（10分程考える）
- ああ、数字T + 1を作っても良いのか～なるほど～
- ここでよく考えず、ansにdp[T][2]を加えるだけのものを書く。サンプル3が合わない
- えぇ……（思考ループ30分⁵）次の問題読むか～
- 次の問題を読んだ瞬間、ansにdp[T][2^k]を加えなければいけないことに気づく（T+1だけでなくT+2, T+3, … も考慮しなければならない）
- AC!
13:21 順位表をチェックする。大体30位くらい。まだFは解かれていない。
13:21 F問題
- 問題を読む。
- 問題の把握にちょっと時間がかかる（5分くらい）
- 1つずつコインを置いてスライドさせる、という操作を繰り返せば良さそう。
- 辞書順最小を求めるので、貪欲にコインを置いていくんだろうと思った。
- 今置ける頂点の集合の中で最も頂点番号が小さいものにおけるかどうかを判定する。この判定がその場（その後の展開を考えずに）でできれば勝ち。
- そこにコインを置くということは、その頂点及びその部分木が使えなくなるということ。
- 残りM個置く場合、操作回数の最小と最大が定まるか……　定まりそう。
- 実際、Validな浅い頂点ベストM個にコインを置いていけば操作回数の最小が達成できるし、Validな深い頂点ベストM個にコインを置いていけば操作回数の最大が達成できる。
- Validな頂点がM個以上あって、これらの間にKが挟まれていればOKなのだろう。NGの場合は他の頂点を試していく。全ての頂点でNGの場合、答えは-1となる。
- 実装する（結構時間がかかった。バグを埋め込んでしまい、30分ほどかかった気がする）
- ここで順位表をチェックすると、順位表が凍結されていた。
- 提出。なんと1発AC!。とても嬉しくて、小さくガッツポーズしたのは内緒。
14:13 トイレ休憩
14:15 G問題を読む
- ふむふむ。簡単には解けなさそう。
- 二分探索かなぁ。う～ん・・・
- （実はコンテスト終了間際に誤読していたことに気づく。カードの数字は(1, ..., N)の置換なので、すべての数字はちょうど2回でる。ここを任意の数字だと思ってしまい、違う問題を考えてしまっていた⁶）
- Hを読むことにする
14:30 H問題を読む
- ゲーム系。中央値。
- 中央値と聞いて、二分探索を思いつく。
- だが、この後どうすればよいかで止まってしまった。
- 「N個の要素の中央値がx -> x以下の要素が[(N+1)/2]個以上となるような最小のx」という言い換えはできた。
- しかし、「中央値がx以上 -> (x以上の要素の数) >= (x未満の要素の数)」の言い換えができなかった。⁷
15:00 ～コンテスト終了～

コンテスト後

終了直後

コンテスト終了。お腹が減ったので焼肉弁当を食べました。

お弁当を食べていると、ちょくだいさん（AtCoder社長）が後方で話していることに気づく。

ちょくだいさん曰く、「パーカーのボーダーを上位50名にしてよかった～」だそうです。当初は2000点以上にパーカー進呈だったそうで、得点分布を見ると、該当者が2人という状況でした。

ちょくだいさんの話によると、最初パーカーのボーダーは2000点だったらしい（やばい
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

F問題が思ったより解かれていなかったのが想定外だったみたいです。
ちょくだいさんにAtCoderステッカーをもらい、そのまま結果発表へ。

結果発表

いよいよ結果発表。コンテスト終了1時間前に順位表が凍結されていたので、この時点では誰がどの順位かわかりません。

結果、12位 / 100名という成績で、パーカをゲットできました！！

パーカーのサイズは数に限りがあるので、順位が高い順に選ぶ権利が与えられる仕様でした。
パーカーと競プロer⁸のマッチング（？）ですね
TシャツもLサイズだったので、Lサイズを選びました⁹。

とりあえず、目標を果たせたので良かったです。

解説

ちょくだいさんの生解説です。AtCoderのコンテストで何回か聞いたことはあるのですが、生では始めてでした。

解説はとてもわかり易かったと思います。途中のやり取りが面白かったです。

ちょくだいさん「辞書順って言われて思いつくアルゴリズムって何〜？」
「貪欲」
ちょくだいさん「そう貪欲！早かった！！」#code_festival
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

ちょくだいさん「ちょっと次数書いてみるよ」
ちょくだいさん「1, 0, 2, 1, 1, 1, ...」
ちょくだいさん「1多いからやーめた」
— kakiraちゃん@飯テロリスト (@kakira9618) 2018年11月25日

他にも、Bを乱択（Yes/Noの50%出力）で通した（実際には乱択に到達する前に解が出力されていたみたいですが）人がいたらしいとの情報を得たりしました。。。まじか。

懇親会とビンゴゲーム

ビンゴゲームが始まりました。こんな感じの用紙に自分の回答を書いて、他の参加者さんとの共通点（1人につき最大1個）を見つけていきます。

一列をいち早く揃えて、受付に渡すと賞品がもらえます（もらえました）。
全部のマスを揃えると別に賞品がもらえるのですが、tempではなくtmpを書いている人が多かったりして、全部を埋めることはできませんでした。全マスを狙う場合は、戦略的にマスに書く値を決めましょう（）

ビンゴゲームと並列で懇親会（立食形式）があります。ビンゴゲームのお題をネタにして話せるので、とても話しかけ（話しかけられ）やすかったです。
データ構造の話（Wavelet Matrixなど）ができたり、twitterで有名な人と会えたりしてとても有意義でした。

感想

とても楽しく、戦利品もたくさん得られたり、競技プログラミングのモチベーションも上がったり、とても満足できるイベントでした！！

来年からも出られるみたいですが、次はCODE FESTIVALの方に頑張って出場してみたいなぁと思っています。

CCSで最近競技プログラミングを始めた方にもおすすめできるイベントです。誰かエントリーしないかなぁ。

また、遠方の参加者の場合でも、最大2泊までのホテル代（1万円x宿泊日数）、交通費などが支給されますので安心です。

戦利品

得られた戦利品は以下の通りです。

CODE FESTIVAL Tシャツ(L)
CODE FESTIVAL パーカー(L)
CODE FESTIVAL ステッカー
CODE FESTIVAL 無地レポート帳
CODE FESTIVAL 手さげ袋
AtCoder ステッカー(背景：白、透明の2種)
お菓子
焼肉弁当
人脈（？）
競プロのモチベ（？）

おわりに

明日の記事は、@massoumen さんの記事です。楽しみですね。

CODE FESTIVAL qual Bに参加して、101位でCODE THANKS FESTIVALに招待されました ↩
twitterで飯テロを行うなどをしていて、5:00くらいの就寝になりました。幸い、会場（テレコムセンタ－駅近く）が近かったので遅刻はせずに済みました。 ↩
後に、https://beta.atcoder.jp/contests/arc071/tasks/arc071_b が既視感の原因と判明（？） ↩
ここの状態の持ち方には多少のバリエーションがあるみたいです。 ↩
DPの更新が早くできるなぁ……でも答えには関係ないか……　もしかして600個以上になる？　いや、ならないなぁ……などと考えていました。。。 ↩
正しい問題を考えてたとしても、本番中にACできるとは思えないタイプの問題でした。 ↩
Median of Medians で学んだことを活かしきれていなくて、悔しいですね。 ↩
競技プログラミングをやる人 ↩
これは知見ですが、自分の服のサイズは把握しておきましょう。かなり迷いました。 ↩

CODE THANKS FESTIVAL 2018 参加記

目次