shining segtree

競技プログラミングとかについて書きます。

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 に参加しました。

主催してくださった皆様ありがとうございました。ものすごく楽しかったので参加記を書きます。

https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/936749340441243648https://twitter.com/CodeFestival/status/93674934044124364

 

お昼ご飯だわ~い!! 

 

 

前日

前泊の人々を集めてボドゲをしました。

メンバーは竹雄さんtsutajさんらてあさんフェリンさんこうきさんでした。

各位参加ありがとうございました!

だいぶ楽しかったのですが都心のカラオケは高く財布が四散爆発するところだったので当初の予定と変えて2時間で出ました。

その後ふーらくたるさんと合流、行き場を失い迷える子羊をしたのちファミレスでご飯。次に集まるときはちゃんとコワーキングスペースを借りるなりしますね…。

 ボドゲ自体は最高に楽しかったです。次こそギャンブラーギャンブルをやりたい。

 

当日

起床AC。ゆりかもめって駅も揺れるんですね、ゆれかもめやが。

道中でらてあさんにtwitterで連絡し、駅で落ち合い会場へ。

 

開場20分前とかだったので会場横のスペースで tourist じゃんけんをしました。

 そろそろ怒られそうだよね。

そうこうしていると開場、入場即手続きACからのTシャツゲット!

2枚目のコンテストTシャツ嬉しい!

お弁当を食べながらコンテストの開始を待ちました。

 キーボードを持ってきていたんですが、うるさいキーボードだったため撤去。

周りが自分のことを気にしてないかが気になって集中できない、ってことありませんか?ありますね。

問題

A問題

最大値を求める。すべての要素見ていくのではなく max_element を使うべきだった。

max_element - cpprefjp C++日本語リファレンス

 

B問題

回文を構築する。先頭から i 文字を反転して連結して回文かどうかを調べた。

string.substr(0, i) と std::reverse() で実装すると早い。

 

C問題

priority_queue でえいする。こういう問題大好きです。

Typical 貪欲 Contest があったらまず収録されているであろう問題ですね。

この時点で15位とかだったのでテンションが上がる。

 

D問題

M人乗りのバスにN人ずつ乗ります。

1台のバスに乗るとき余る人の数は N - (M % N) 人になります。

N = N - (M % N) とし、余った人数NをまたM人乗りのバスに乗せていくと、

また N - (M % N) 人余ります。

この操作がなんだかユークリッドの互除法に似てるなぁと思ったので、なんとなくGCDしてみたらAC。エスパー良くないね。

色々考えていたせいで40分もかけてしまった。

 

E問題

50個のコイン袋を10手で判断すればいいため、1回で5袋を判断できればよいなぁという気持ちになる。

コインが1袋に10000枚入っているので、1枚、10枚、100枚、1000枚、10000枚と取っていくとよいことが分かるが、重さ 8, 9, 10, 11, 12 の5種について

(1×8)+(10×9)+(100×10)+(1000×11)+(10000×12) = 132098

ただし

132098 = (1×8)+(10×9)+(100×0)+(1000×12)+(10000×12)

であるため、1のほうから数を決めていく必要がある。

5進数?か何かでやるとより賢いらしい。

 

F問題

O(n^2) の自明な DP が生えるが入力が大きい。

しかし不自然な制約のおかげで入力が実は小さい。

細かい計算ができず解法に自信が持てなかったため、あれこれ検証しているうちにコンテスト終了。

パーカーが得られず悲しいね。

mapDP を書いたことがなかったため経験値不足を感じた。

 

 

表彰

5位のふーらくたるさんが表彰されマイクを握ったその刹那──

 

"何か"が私に語りかけました。 

 

私はその一瞬で読唇術の全てを会得、真空状態の中でふーらくたるさんが

 

「今まで競技プログラミングをやってきて表彰されたのは初めてなので、とてもうれしいです」

 

と話しているのが分かりました。

 

あまりに感動的なコメントに私は滝のように涙を流し、涙は廻り大河を成し大地を潤し大海へと流れ込みそうでしたが耐えました。その反動で私は読唇術の全てを忘れました。

 

↓真空状態については以下を参照してください。

fooractal-mine.hatenablog.com

 

コネクションハント

懇親会の前にコネクションハントという参加者同士質問をしあって、質問の答えを集める、というイベントがありました。

特に面白い質問も思いつかなかったため、好きなコンテストについて聞いてみました。

結果は以下のようになりました。

  1. ICPC (7票)
  2. ARC (6票)
  3. AGC (5票)
  4. CODE FESTIVAL (4票)

ICPCが1位なのは意外でしたね…

珍しい回答だと Anarchy Golf, AtCoder の unrated なコンテスト などがありました。

ちょくだいさんにも質問に答えていただきました!

 

懇親会+宴

いつもの人々と一緒にご飯を食べながら歩き回った結果、念願の大悪魔と会話するという実績を解除することができました。早くこの世界を統べてほしいですね。

どこかで本人の隣でふぁぼ爆をするのが流行っていたようです。

競プロ界隈でふぁぼ爆が流行っているのはなんなんでしょうか…ww

 

その後はなんかこのまま帰るのはなぁと思っている人々で集まってボウリングをしたりカラオケをしたりしました。競プロerとボウリングをするのは2回目なのですが、レベルが高くないので安心ですし楽しいです(?)

 

総括

CODE FESTIVAL は最高なので、出てない人は出ましょう!

来年こそは本選出場&パーカーゲットするぞという思いでいます。精進あるのみだなぁ。

 

ICPC つくばに参加権がないため、私の今年の競プロオフはこれでおしまいです。

今年の後半だけで50人以上の競プロerとお話しできて、とても仲良くなれた方々もいて私は嬉しいです。

コミュ障を乗り越えて色々な方に話しかけるのと、Twitterでの事前のつながりがやはり大きいですね。

僕とお話ししてくださった全ての方々、ありがとうございます。今後ともよろしくお願いいたします。

 

 

zenaa