CODE FESTIVAL 2016本戦に参加しました(その1)

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。お久しぶりです。

もう1週間以上経ってしまいましたが、実験レポートや課題などが一段落ついたので、やっと参加記を書きたいと思います。

DDCC参加記も後日書きます。

1日目

久しぶりに新幹線に乗り、東京へ向かう。

新幹線で読むためにライトノベルを4冊買ったが、片道では0.5冊程度しか読めないことを知る。

新橋・汐留周辺で道に迷う。日テレを見る。外国人の女性に「繁華街に行きたいんだけど、どこがオススメ?」みたいなことを英語で聞かれ、人生で初めて"I'm stranger."と言う。

電通のビルを横切り、なんとか余裕をもって会場に到着。

Tシャツをもらい、PCのセッティングを終えてのんびり過ごす。chokudaiさんを目撃する。

開会式直前くらいに自分の左前に同じ大学の、高校からの友人(@refine_P)が現れる。来ることどころか競プロをやっていたことも知らなかったので驚愕。知り合いゼロでの参加を免れる。

(このペースで書いていて終わるのか?)

なんやかんやで開会式が終わり、本戦に向けて緊張感が高まる。とりあえずじゃがりこ(サラダ)とチョコレートを確保。

本戦開始。

A問題は探すだけ。

B問題は、1からkまでの和を計算していき、Nを超えた時点で、その時の和SとNの差S-N(足し過ぎた分)が、多分1からkまでに含まれているので、それを飛ばして出力。AC。

C問題は、1分ほど誤読。後になって、同じ誤読をしている人が多いことを知る。定義が再帰的になっており、間に何百人もの通訳者を挟んでもOKと分かり、いろいろ考えてUnion-Find木で解く(同じ言語を話せる人は同じグループ)。AC。

D問題は、とりあえず色々試してみて、「和がMの倍数」のペアを先に作ってから「同じ数」のペアを作ると良いと確信。

少しの間「和がM」と勘違いするも、すぐに「の倍数」に気づき、「じゃあ最初からMで割った余りで受け取ったら"和がM"でいけるやん」と思う。

ただし、それだと例えばM=10のときに「1,11,21」と「1,21,21」が同じ扱いになるので、注意が必要だと考える。しかし、その時は「余りが1なのは3つ、その中に同数ペアは1組」という情報だけ持っていればよいことに気づく(「11,11,21,21」と「21,21,21,21」は同じ扱いでOK)。

各余りについて「何枚あるか」「同数ペアがいくつあるか」の情報を持ち、余りがkになるグループとM-kになるグループでペアを作っていく。できるペア数はmin(k, M-k)組。

ただし、このときに、余った方において同数ペアをいくつ食いつぶすかどうかを考えないといけない。残る枚数と元々のペア数から計算できる。

また、余りが0またはM/2になる場合は特殊ケースとして、「そのグループ内でペアを作れるだけ作ればいい」となる。

このあたりを実装して、AC。

D問題において、i を 1 と打ち間違えていることに気づくまで結構タイムロス。悲しい。

E問題、色々考えるも解けず。二分探索かな?とか思ったが全然違った。どうやら私は、神の視点で全てを見渡してDPするのは大丈夫だが「その時々の立場でDPする」という発想が苦手なようだ(シカのAtCoDeerくんがせんべいを食べる問題とか)。

結果は1500点という、点数設定者のニヤニヤ顔が目に浮かぶような悔しい結果となった。

順位は220人中143位。真ん中ちょい下。悔しい。

来年も来て、絶対にパーカーを貰ってやる!と決意。なお来年開催される保証も来年の賞品がパーカーである保証も無い。

本戦を終え、touristさんの講演。英語リスニング力が低いのを悔やむ。自分も将来子供ができたら早いうちからプログラミングに触れさせてみようかなあなどと思う。

山本一成さんのトークライブを聞こうとするも、一成さんが「みんなご飯食べたら?」と言ったので適当に食べる。

一成さんのトークライブが面白かった。競プロとは違う視点でのソフトウェア開発の話が聞けた。彼女を作って競プロの世界へ誘い込まねばならぬと決意を新たにする。

続いて、秋葉拓哉さんのペアプログラミングのイベント。問題がシンプルかつ発想を要する問題で面白かった。ブルートフォースに実装してからWinとLose分布を描画してみるという考え方があるんだなあ。

UFOキャッチャーに失敗し、「渡る世間はナベばかり」という鬼畜神経衰弱に悶絶。

エキシビションマッチのために本戦会場へ戻される。

エキシビションマッチを友達と喋りながら画面近くで観戦。やいやい言いながら考えながら実況解説を聞きながらチャレンジャーの画面を見るというのは非常に楽しかった。

海外チームがランダム戦略を取ったときの盛り上がりが面白かった。indeedチームがBを通したり、その前にオープンコンテストでBやAがACされたり、すごかった。

翌日のチーム対抗リレーの顔合わせで、同じ大学の先輩の方(面識は無かった)と合う。どうやら他にも同じ大学の人が来ているようでびっくりした。

チームは準急さんと同じだったので心強いと思うとともに、足を引っ張らないように頑張らないといけないなあと思った。

同じチームのロシア人青年がめちゃくちゃイケメンだった。

一日目が終了してホテルに行き、そこで友達と、同じチームの大学の先輩と、さきほど聞いたもう一人の先輩と会う。お腹がすいていたので部屋に戻ってから4人でコンビニへ。

ご飯やお菓子を買って、ホテルのロビーで食べながら歓談。興味深い話も色々聞けた。4人中自分を含む3人が翌週のDDCCにも参加するということを知る。DDCCも知り合いゼロではないようだ。

適度なところで部屋に戻り、風呂に入って寝る。パジャマが思ってた感じと違ったので、風邪を引かないか心配だった。

長くなったので、翌日分はまた次回。たぶん明日更新します。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする