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

フツーって言うなぁ!

フツーなサラリーマンのフツーな嘆き.

CODE THANKS FESTIVAL A日程に参加してきました

Python 競技プログラミング

12/7(日)に東京で行われた,リクルートホールディングス社主催のプログラミングコンテストであるCODE THANKS FESTIVALのA日程に参加してきました.

この大会は,先日行われた別のプロコンであるCODE FESTIVALの予選を通過できなかった人に向けて,より多くの人に大会に参加してもらいたいというリクルート社側のご厚意により開催されたものでした*1
自分は予選で,あと一歩の所で本戦参加を逃してしまったので,大会参加できることは純粋に嬉しかったです.

何してたかだけまとめときたいと思います.

コンテスト前

5時半起きで当日入り.
寒さが厳しかった.

受付を済ませた後に即昼食が出た.
叙々苑の焼肉弁当だった(めっちゃうまかった).

昼食を食べながら,隣の人と話す.
年齢層的に大学1,2回生が多そうで,若干場違い感.

WebDB Forumの昼食会でお会いしたリクルートの人事の方に(2週間ぶりに)再会する.
「前回は服装ちゃんとしてたのに…」って言われた(笑)

ルール説明にchokudaiさんが登場.
初めてお会いしたけど,わりとイメージ通りの人で安心した(?)

f:id:lethe2211:20141207112958j:plain

コンテストとsubmitした解答

問題はすべてPythonで解いた.

事前に聞いていたように,いつもの大会よりは難易度易しめだったと思う*2

A問題

与えられた入力値a,bに対して,4 * a + 2 * bを返す.

First Accept狙ったけど,同時開催されてたオープンコンテストの方にsubmitしてしまった*3

B問題

A,B,Cを生産量の降順にソートし,順番に使っていくと最小の時間で処理が終了する.

C問題

S_iの値に応じて,P_iの値を足していく.
インデックスが微妙にズレてるのだけが注意点.

D問題

区間[s, t]と[a, b]の差を求めて100をかける.
場合分けしてしまったが,後で解説を聞いて,区間の共通部分はmax(0, min(t, b) - max(s, a))で求められることを知って悶えた.

この辺から手が止まり出す.

E問題

最初,問題の意味が解読できなかったので,先にF問題を解いて戻ってきた.

少し考えなおして,N回試行した後に各々の手順の分戻せばよいと気づくが,それでもO(RCN)=O(50*50*5000)となり,「Pythonだとギリギリだなー,もっと良い解法ないかなー」と20分ぐらい悩む.
でも特に思いつかなかったのでsubmitしてみると通った.

F問題

与えられた情報から,確定している順位の最上位を求めるとよい.
DFSを使っても良いが,N<=50なので,情報を何度もなめて,参加者1より上位の参加者を新たに追加できなくなるまで追加し続ける手法でもO(N^2)で十分間に合う.

ここまではすべて一発Accept.

G問題

手が出なかった.
少なくともブルートフォースのシミュレートで部分点ぐらいは取りたかったが,意外に場合分けが面倒だった.

想定解は,DPで,「何番目の人を見ているか」,「すでに着席している中で,最も番号の大きい人から番号の小さい側にいくつ空席があるか」,「すでに着席している中で,最も番号の大きい人の座標」を保存する手法らしい.
これは後で復習したい.

H問題

見た感じ,自分には手に負えない問題だと感じた*4

Hに取り掛かった時点で残り1時間ぐらいだった.
順位表を見てみると,13位ぐらいだったので,部分点を通すだけでも入賞できそうだと思い,そこに注力した.

書いたコードがこれ↓
O(R^3C^3)という糞コード. 5分ぐらいジャッジ結果が返ってこなくて焦ったが,無事15点は取れた.

想定解は,中心の座標を決定し,そこから生地の左端までの長方形を考え,点対称となるかどうかを見ていくらしい(?)*5

結果

615点で9位入賞.
正直,こんなので入賞してしまって申し訳ない感じはあるが,嬉しかった*6

オープンコンテストの方で見ても45位ぐらいだったので,自分にしては上出来だったのでは.

懇親会

立食形式での懇親会だった*7

DDR太鼓の達人が置いてあった.
chokudaiさんめっちゃ頑張ってた.

個人的には書道コーディングが面白かった.
これは,普段コンピュータで行うコーディングを,筆で行うというもの.
結構いろんなネタがあった*8

自分が書いたのがこれ↓

f:id:lethe2211:20141207184549j:plain

上でも書いたように,大学の学部生が多かったように思う.
般教の話とか久しぶりにした.

また,今回たまたまなのかもしれないが,女子率も結構高かった.
「プロコン」というと,どうしても男所帯のイメージがあるが,裾野を見るとそうでもないのかなと思った.

食事も豪華で,自分は寿司ばかり食べていた.


自分にとってはたぶん,学生生活最後のオンサイトのプログラミングコンテストになるかと思います*9

本戦出場できなかった時は悔しかったですが,そこそこの結果を残せてよかったのではないかと思います.

そろそろ修論に取り掛かるべき時期が来てしまいました.
何とか修了できるように頑張ります.

*1:ありがたいと思う反面,少し複雑な感じ…

*2:ABCぐらい?

*3:普通に最速じゃなかった

*4:それを知ることができただけでも成長できている感じはあるけど

*5:解説を聞いたがあまり良くわからなかった…

*6:賞品は焼肉会食らしい

*7:未成年者も多いということでアルコールはなし

*8:エディタ戦争ネタはどこでも出てくるな…

*9:最後もクソも2回目だけど