sataniC++

C++、競プロ、数学などについて色々考えたりします。

CODE FESTIVAL 2016に参加しました

競プロ参加 競プロ参加-イベント

CODE FESTIVAL 2016の予選に通過できたので、本選にも参加してきました。
それに関してあったことなど、いろいろ書いておきます。

予選前

twitter.com
「大体東京で開催されるイベントは交通費だけでかなりのお金かかるしなぁ…」
という事情からイベント事はほとんど諦めていたんですが、

「こどふぇすは交通費宿泊費全額負担します！」

という言葉に誘われて何とか頑張ってみることにしました。

予選

予選A

A問題を53秒で早解きしたと思いきやいきなりWA…。
それに気づかずB,Cと解いて、Aが解けていなかったことに気づきすぐにAC。

twitter.com
14分3完で全体245位だったものの、ギリギリ予選通過ラインだったらしく一先ず安心しました。

予選B

twitter.com
もう予選通過はしていましたが、ABCDをポンポンとAC出来て53分4完99位と好記録を残せました。

予選C

21分3完192位で予選通過はギリギリラインだったのかな…？という順位でした。



全3回の予選において、予選には参加できていそうな順位を取れて「本選もがんばるぞ～」と意気込んでいました。

本選前

-1日目

twitter.com
twitter.com
twitter.com
飛行機やらいくつもの電車やらを乗り継いで行く計画を全て立てたことが無かったため、色々と苦労していました（泣）。

特に日曜日の帰りの飛行機が既に予約いっぱいで、仕方なく月曜日の朝一の飛行機で帰ることに…。


飛行機に乗ることが決まったら、なるべく早く予約は済ませておこうという良い教訓になりました（月曜日の午前中にあった大学の講義はやむなく欠席することに）。

0日目

twitter.com
絶対にパーカーはゲットしてやるからな！
という意気込みで去年の過去問を解いたりもしていました。

当日は早起きする必要があったので、23時前にはもう寝ることに。

本選

1日目

twitter.com
朝4時に起床し、5時に歩いて最寄駅へ（駅まで徒歩3,40分）。

twitter.com
（時間の都合上、朝一の特急に乗る必要がありましたが、駅には人っ子一人いなかったため、電車内で特急券を買うことになってしまいました）


twitter.com
そして初めて一人飛行機チャレンジに成功しました。

途中、保安検査場などのゲートを通る際にはスマホをかざすだけで良く、「これが現代の技術か…」と感動しました。
（かざすときにスマホの画面が暗くなってしまっていてわちゃわちゃしたのは内緒）


twitter.com
そして電車を何個か乗り継いで無事会場へ到着！
家を出てから6時間ほど経っていたので、すでに結構疲れていました（白目）。


f:id:satanic0258:20170222152357j:plain
席に座ると軽食が置いてあり、場内に流れる音楽のビートにノリながらPC等の準備をしていました。


twitter.com
そして本番！

A

問題を見て、「あっこれ去年のこどふぇすアフターサイトにあった"りんごの挑戦状"にあったやつだ！」と思うも、そのクイズに思考が引っ張られ、最初の30秒は問題文中に書いてある表から"snuke"の文字を実際に探していました。
（見つけてからサンプルを見ておかしいことに気づく）

結局、ただ文字列S_{ij}をすべて調べる自明な解法でAC(02:35)。

B

色々紙で計算したものの、何故かバグが取れず2WAして飛ばすことに。
A問題のミスで変に動揺してたんだと思います（白目）。

C

同じ言語を話せる人同士を同じ連結成分とするUnionFindを構成することで、難なくAC(19:59)。

D

少し考えを整理するのに時間がかかりました。
ある2枚のカードがペアとなる判定が「同じ数字」「和がMの倍数」のいずれか、ということから、すべての数字に\mod Mを適用して(0,M),(1,M-1),\cdotsとペアにしていく解法を思い付き、実装。

最後にMが偶数なら(\frac{M}{2},\frac{M}{2})というペアを作りますが、これを奇数の時にも同じことを行ってしまっていて1WAを出してしまいました。

しかしすぐに間違いに気づき、何とかAC(60:24)。

この時点で1200点

DをACした時点で残り2時間で、パーカーゲットまではあと400点となりました。
ここで解けてなかったB問題に戻ろうとも思いましたが、「Bは満点300点」ということに気づき、
今からBだけを解いてもパーカーは貰えない！

ということで、500点であるEの部分点を先にもぎ取ることにしました。

E

twitter.com
何とか部分点を…と90分間必死に4WAしつつ考えた結果、なんとか☝このような解法をひねり出せました。

この解法は、時間計算量がO(\sum_{i=1}^N{\frac{N}{i}}) = O(NlogN)ですが、部分点はN\leq10^6だったため、部分点はゲットすることができました(153:10)。


点数も1600点を超え、無事パーカーゲット！
Eの部分点が通ったとき、心の中で思いっきりガッツポーズをしていました。

B

そしてBに戻り、もう一度ちゃんと計算しなおしてみると、よくわからないことをしていたことに気づきました（数十分前の自分のコードが読めなかった）。
結局、iまでの総和の公式(\sum_{k=1}^i=\frac{i(i+1)}{2})を使う解法であっさりAC(162:29)。

結果

twitter.com
最終的に、162分4.5完110位で本選終了しました。
220人中110位ということで、ちょうどど真ん中でした。


会場後ろでパーカーを受け取り、ニコニコしながらすぐ着替えました。


本選後

twitter.com
touristさんの強さの秘訣を聞いて（勝てない）と思うなどしていました。


twitter.com
その後は、色々見て回ろうかと思うも、疲れからかあまり動く気が起きず（もったいなかった）。
chokudaiさんの本選解説を聞くだけとなってしまいました。

この時点で全然誰とも話せてないので、コミュ障って感じがしましたね（競プロerを生で見たのが初めてだったので「みんな強そう」となっていた）。


その後はプロ軍団によるエキシビションマッチを見ていました。
どちらの問題見ても全然ピンとくる解法がなく、こういう問題を相手するのか…と遠い目をしていました。



twitter.com
最後に全員集合して、リレーのチームが発表されました。
私はQチームで、btkさんと同じチームとなりました（ここで初めて知ってる人を見つける）。

twitter.com
アナウンスで「まずチームのメンバーと自己紹介をしましょう！」という流れになったのですが、今年から海外からも参加している方がいるということで、自己紹介を全員英語で行いました（瀕死）。
英語で自己紹介すると分かっていればもうちょっとちゃんと言えたと思いますね…。
これを受けて、来年のこどふぇすまでに（参加できたらですが）英語をもっとちゃんと勉強しておこうと思いました。
（DPとグラフ問題が苦手だけど数学の問題は解けるかもしれない、みたいなことを言った記憶があります）

帰り際にbtkさんと「チーム内に東大の人半数くらいいて怖い」という話をして会場から出ていきました。

1日目終了後

twitter.com
twitter.com
そして建物を出て、指定されたホテルに向かいました。
（送迎バスみたいなものがあるような話を何故かどこかで得ていたため、「あっ自分で行くのか…」と困惑していました）

twitter.com
うろうろした結果、40分くらいかけて何とかホテルに到着することが出来ました。

ホテルのカウンターで、「えっと…CODE FESTIVALの…参加者なんですが…」みたいなことを伝え、何とか入室しました（本当にこれで泊まれるのかと不安になっていた）。

twitter.com
その際、ペン型ドライバーを記念品として貰いました。
（「なんだこれ」という思いと、「飛行機乗るとき危険物として扱われて乗れなかったりしないか」など変なことを考えてました（失礼））


1日目は全然他の方と話せなかったので、Twitter上で「明日は会いましょう🔥」というリプを交わして寝ました。

2日目

会場まで

twitter.com
ホテルを出るとき、同じホテルを指定されたらしい人々を発見した(こどふぇすパーカーを着ていたのですぐわかった)ので、その方々に付いていくことにしました。
その内の一人はkzyKTさんであると分かり、ちょこちょこ互いの話をしながら会場へと向かいました。

twitter.com
自分の席に着くとおにぎりが置いてあり、もぐもぐしながらトーナメントの準備。

トーナメント

Round1

twitter.com
とりあえずすぐに分かるBの部分点(100)を通して、うむむと考えていたらあっという間に30分が経過してしまいました。
たまたまグループ内で「正の点数が取れていれば通過」となっていたため、運よくRound2へ。

Round2

twitter.com
20分弱くらいかけてAの部分点(200)+Bの部分点(200)を獲得するも、グループ内の人たちが10分前後で既に400点を取っており、通過には至りませんでした。

twitter.com
後からA問題の解法がTLで流れてきて、「天才だー」となっていました。

Round3

せっかくだから、とRound3の問題を見て解こうと思ったものの、方針が立たず。
というか朝から部分点もぎ取りに全力になるのを2回やっていたので、すでに疲れが出ていました。


結果もらえたステッカーは2つで、あまり健闘できなかったな…という感じに終わりました。
次までには朝に頭が回るような訓練をしておきたいと思います(？)。

昼

トーナメントが終わってからは、kouさんと焼き肉弁当を食べたり、
体力測定で「体格大きい人圧倒的に有利だ…」と絶望したり、
yurahunaさんに「トーナメント優勝おめでとうございます👏」と祝いの言葉を述べたり、
りんごさんクイズを楽しく聞いたりしていました。

コンテンツが豊富でとても楽しく、あっという間にリレーの時間となりました。

リレー

チーム対抗リレーでは、一人一問を解くルールとなっています。
割り当てられたチームQ(黄色)では、本選順位の低い人からA,B,C,...と問題を解くことになり、
私はF問題-「3分割ゲーム/Trichotomy」を担当することになりました。
（チーム内の一人が2日目欠席していたため、btkさんが2問担当していました）


(以下、F問題の解説を書いています。適当に読み飛ばしてください)


F問題は、

f(N)=『長さNの紐を3つに分割して、最長、最短の長さの紐1本ずつを捨てる操作』を繰り返し行える最大の回数
という関数fに対して、あるXが与えられたとき、f(N)=Xを満たす最大のNを求めよ。
ただし、1\leq X \leq40である。

という問題でした。

少し考えてみると、f(N)を求める際にNを分割して長さMの紐が残るとするとき、f(N)=f(M)+1となることが分かります。

さらに、操作回数を最大にすることを考えると、長さN(\geq 3)の紐は、それぞれ長さ、1、\lfloor \frac{N-1}{2} \rfloor、\lceil \frac{N-1}{2} \rceilの紐に分割するのが最適であることが分かります(N<3の時は紐を3つに分割出来ません)。
このとき、1\leq \lfloor \frac{N-1}{2} \rfloor \leq \lceil \frac{N-1}{2} \rceilであるため、長さ\lfloor \frac{N-1}{2} \rfloorの紐が残ることが分かります。


以上のことから、f(N)は、
\displaystyle f(N) = \begin{cases} 0 & (N<3) \\ f(\lfloor \frac{N-1}{2} \rfloor) + 1 & (N\geq 3) \end{cases}
と再帰的に計算することが出来ることが分かります。


ここで、Nが奇数の時、紐は1、\frac{N-1}{2}、\frac{N-1}{2}と分割することが出来ますが、決まった操作回数でNを最大化することを考えると、長さM=N+1の紐を考えて、1、\frac{M}{2}-1、\frac{M}{2}と分割した方が良いことが分かります。
（このとき、それぞれで残る紐の長さ\frac{N-1}{2}、\frac{M}{2}-1は等しくなります）
逆に、Nが偶数の時、長さM=N+1の紐を考えると、残る紐の長さは長さMの紐の方が長いことが分かります。

つまり、f(N)=Xを満たす最大のNは、偶数となることが分かります。

よって、あるXに対し、f(N)=Xを満たす最大のNをN=g(X)({}^\forall Xでg(X)は偶数)と書くと、
\displaystyle f(g(X)) = \begin{cases} 0 & (g(X)<3) \\ f(\frac{g(X)}{2}-1) + 1 & (g(X)\geq 3) \end{cases}
となります。

また、長さg(X)の紐に一度最適な操作を行うと、長さg(X-1)の紐が残ります。
よって、fは次のようにも書くことが出来ます。
\displaystyle f(g(X)) = \begin{cases} 0 & (g(X)<3) \\ f(g(X-1)) + 1 & (g(X)\geq 3) \end{cases}

これらの式の右辺におけるfの引数を比較すると、
\displaystyle \frac{g(X)}{2}-1 = g(X-1)
となります。
これと、g(0) = 2と明らかに分かる式(操作できるのは長さ3以上の紐であるため、操作できない紐の長さの最大は2となります)から、g(X)を求めると、
\displaystyle \begin{eqnarray} \frac{g(X)}{2}-1 &=& g(X-1) \\ g(X) &=& 2g(X-1)+2 \\ g(X) + 2 &=& 2(g(X-1) + 2) \\ &=& 2^2(g(X-2)+2) \\ &=& \cdots \\ &=& 2^X(g(0)+2) \\ &=& 4 \cdot 2^X \\ &=& 2^{X+2} \\ \therefore g(X) &=& 2^{X+2} - 2 \end{eqnarray}

以上から、あるXに対し、f(N)=Xを満たす最大のNを求めることが出来ました。


ただ、実際のコンテスト時間中には、このようにちゃんとは求めず、「N=2^{X+2}-2という仮説は正しいだろう」として実装を行いました。
そのコードの中身も、

int x;
std::cin >> x;
std::cout << (1 << (x+2)) - 2 << std::endl;

という非常に簡単なコードでAC出来ました(この時点で13分ほど)。



自分の担当の問題を無事AC出来たので、あとは他の人のフォローに回っていました。
といっても、簡単な問題は各々で解けていたため、難しい問題ばかり残ってあまり手を出せないでいました。
チーム内の上位陣はやっぱ頭の回転も速いんだな、と感心していました。
f:id:satanic0258:20170222152415j:plain
（リレーの机はこんな様子でした）

祭りの終わり

f:id:satanic0258:20170222152441j:plain
最後に様々な項目についての表彰があり、CODE FESTIVAL 2016は幕を下ろしました。

今回、特に表彰で登壇するようなこともなかったため、次回があれば何か爪あとを残したいと思いました。


建物を出てから、「会いましょう！」と何回か言っていたのに全然会えていなかったtreeoneさんとお話をすることが出来ました。
「良きライバル(？)として互いに精進しましょう🔥」と努力を誓うなどしました。


帰るまでがこどふぇすだ！

twitter.com
上に述べた通り、当日に飛行機が取れなかったため、翌日の朝の飛行機まで時間を潰す必要がありました。


twitter.com
とりあえず駅に行こう…と歩き始めて間もなく、大学に入ってからずっと使っていたカバンが突如破損してしまい、てんやわんやになっていました。
若干小雨も降っていたため、適当な軒下に入りカバンを修理。
（金具だけが壊れていたので肩紐をカバンの端に無理やり結んで何とかなりました）



twitter.com
twitter.com
twitter.com
twitter.com
twitter.com
そして、一人での東京も初めてだったため、東京駅やスカイツリーなどへ行き、写真を大量に撮りながら夜の観光をしました。
脚が少し痛くもなっていましたが、せっかくだし…と出来るだけ色々行ってみました。


twitter.com
道中、松屋を見つけたので夕食は初の松屋にしてみました。
「券売機で券を買えばよい」という店のシステムをネットで調べて把握しながら頂きました。

「人と話す必要がない」「安い」「美味しい」と、便利なところがあるもんだ…と感心していました。


twitter.com
日曜-月曜の宿泊はこちらの都合なので宿泊代も出ないため、
「出来るだけ安く済ませよう！」と、ネットカフェに泊まることにしました（ネットカフェに入るのも初めて）。

twitter.com
安いところということもあってか、PCはXP、スペースは1畳ほど、ベッドではなく座椅子などと、若干寝るにはつらい環境ではあったものの、「まぁ仮眠程度だしいいか…」と割り切って仮眠をとりました。

twitter.com
結局滞在時間も5時間程度だったため、1泊500円という破格で止まることが出来ました。
でもあまり疲れは取れないので、翌日も予定があるようなときはカプセルホテルなどに泊まるといいかもしれないですね。

3日目

twitter.com
まだ朝早いものの、朝一の飛行機に乗るため4時前に起床して準備をしていました。

twitter.com
twitter.com
空港でおにぎりを買い、東京を後にしました。


twitter.com
5時間ほどの移動を経て、無事帰ってくることが出来ました🙌

まとめ

今回、CODE FESTIVAL 2016を通して、非常に多くの体験をすることが出来ました。

twitter.com
それも、交通費宿泊費全額負担という大きな支えがあってこそのものです。
さらに、初めてのことがたくさんある中で、交通や領収書のことでリプを頂いたり色々とフォロワーさんにも助けていただきました。
ありがとうございました！


次回の開催もあれば、是非参加したいと思います🔥