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

足跡-sokuseki-

りかの日進月歩の記録

RUPC2017参加記

3/22から3/24に立命館大学で行われたRUPC2017に参加した。

立命館大学競技プログラミング合宿2017 : ATND

 

Day1 : 立命館大学&大阪大学セット

 

コンテスト前 

会場の設営のために10時半くらいにBKCに着いたけど、Twitterではすでに到着している参加者がいてびっくりした。

会場であるBKCで卒業式をしていて、人がとても多かった(怖い)。

あと、自己紹介フェーズがなくなってしまって悲しかった(運営側として申し訳ない気持ちもあります……)。

 

コンテスト

出題側だったので、コンテスト中はジャッジを眺めながら風船運びをしたり、B問題の解説スライドを作ったりしていた。 

コンテストの問題は、B問題とK問題の原案を考えて、B問題の解説をした。 

 

コンテスト後のRCOの宣伝コーナーが面白かった。競プロerに優しい会社。 

 

懇親会 

学内のユニオンフードコートというところで立食パーティーをした。

Twitterでよく見る @ukuku09 さんや @LatteMalta さん、夏の会津合宿でチームを組んだ @somennagasi さんたちとお話しした。とても楽しかったです!!!!

 

懇親会後

大学の宿泊施設に移動して、チェックイン。

 

私の就寝時間までは時間が結構あったのと、RUPC前の1~2週間くらい前から全然競プロできてなくて鈍ってそうだったので、バチャコンをすることに。  

 

 こんな時間にもかかわらず5人も参加してもらえて嬉しかった。

 

 そのあとはTwitterでタイムラインを監視していた。

 

 もちろんベッドで寝ました。

 

 

Day2 : 会津大学セット

 

コンテスト前

 

目覚ましをかける前に寝落ちしてしまって、起きるのがギリギリになって焦った。

湖西線トラップ*1 にかかってしまった人がいて、開催時刻が30分遅くなったので、お菓子を食べてた。おいしい。

 

コンテスト

 

私はB問題を担当することになったので、@_ybrliiu さんにA問題を実装してもらっている間に考察していた。参加者を1人決め打ちすると、その人が勝者になる回数と引き分けになる回数はupper_boundやlower_boundを使うとO(logN)で求められるので全体でO(NlogN)になっていけそうとわかる。A問題がバグっている間にコーディングを代わってもらってB問題をAC。

そのあとA問題を見て、場合分けでいけると思ったので、方針を伝えてから、@konbu1610 さんと一緒にC問題を考える。因数定理をつかって項を一つずつ見つけていけばいいという方針が立って、とりあえず構文解析の実装に移る。構文解析だけでもだいぶバグらせていて辛かった。

ここらで、A問題のバグが取れないので方針を変えて、tをループで回すことにした。@_ybrliiu さんが実装してA問題がAC。その後私は構文解析のところを書き終えてから、多項式の割り算を時間をかけながら実装してACした。

この段階で残りがあと1時間半くらいだったので、E問題を@konbu1610 さんと考えていた。各辺の労力/長さを計算して、労力/長さが大きい順に木を構成していけばいいんじゃないかと思って、@konbu1610 さんに実装してもらっていたけど、嘘解法だとわかって、どうしよう……となったところでコンテスト終了。

 

悲しかったけど、「展開する前のそれぞれの一次式の元の定数項は相異なることが保証される」を理解していなかったのが悪かった。うん。

 

 

懇親会

南草津駅前の魚民に行った。RUPCのほぼすべての参加者が2日目の懇親会に来ていた。

@kenkoooo さんと同じ机だったので、RCOの話を聞いていた。あとKaggleの話も面白かったです。

 

懇親会後

 先輩たちが泊まっている部屋に遊びに行った。そして例によって例のごとくコンテスト。

コンテスト後は解法を教えてもらったり、蟻本やTwitterの話をしたりと、だいぶ長い間居座っていた。いろいろな話ができたので嬉しかったけど、寝る時間を削ってしまって申し訳なかったなあと思ってます。

 

 

Day3 : 北海道大学セット

コンテスト前

目覚ましをつけるとちゃんと起きられるタイプなので、 7時半くらいには起きた。それから荷物をまとめてチェックアウトして、ゆっくり会場に向かう。

ドリンクがなくなっていて、お菓子も少なかったので、RiPProの先輩たちと学内コンビニに買い出しに行った。

 

コンテスト

 

 

A問題を担当することになったけど、「並び替えて」という言葉を読み飛ばして(誤読して) これ本当にA問題か?と思いながら考えていた。実は前日のバチャコンで文字列から削除する系の問題*2を見ていたために、頭の中で(これもしかしてDPする感じか……?)と思って、B問題を考えていた@chakku_000 さんと代わってもらうことにした。その後、@s1230151 さんがA問題、@chakku_000 さんがC問題を考えることになって、@chakku_000 さんがC問題をAC。

B問題は現在8位のユニットとユニット1の差を見て、いくつ増やせばいいかを求めるのかなと思って実装したら、ユニット1の値を変えると他のユニットの合計得点が変わってしまうと気づいて、誤解法だとわかる。その後私がB問題を考え直している間に、A問題がAC。B問題は、値を変更する数をループで回して、その後に合計得点を計算し、ユニット1が8位以上なら答えとするという方法を思いついたので、それを実装した。

実装したはいいけど、バグが取れなくて、@s1230151 さんと一緒にデバッグしていた。その間@chakku_000 さんはE問題を考察。残り30分くらいでB問題をACした。

そしてEが解けないままコンテストが終わる。

A問題を誤読してB問題をひたすらバグらせる害悪でした。

 

 

コンテスト後

解説が(アニメネタとかがあって)とても面白かった。 

解説後は立命館の成績返却とガイダンスに行かなければならなかったので、すぐに会場を去った。

遅れて行ったら、私がいない間に表彰されていたらしくてびっくりした。

  

 

全体を通して

 

 Twitterで見かける人や初めて知った人などたくさんの人と交流できてよかった!

次のオンサイトは会津合宿かな?(オンサイトは楽しいのでHUPCやQUPCやNJPCなどのオンサイトがあればぜひ行きたいです!!)

 

 

 RCOさん、ありがとうございました!!!!!!!!!!

 

 

 

余談

Day1のK問題について。 

K問題原案ですが、大学の定期考査期間中(1月末)に、テスト勉強したくない気持ちが強くなってきて、来期は期末考査がなくレポートだけで成績が決まる講義をたくさん受けたい!!!!と思っていたら降ってきました。やったね。

なお、原案は

  • レポートの数
  • 友達の数
  • AORイカちゃんが自力でレポートを仕上げる最低回数
  • AORイカちゃんと友達のそれぞれのレポートの点数

が与えられて、合計得点の最大値を求める問題(難易度はBくらい)だったのですが、先輩による改変を経て化けました。びっくりしました。

 

*1:京都大阪方面から滋賀に向かうJRには琵琶湖線湖西線があり、南草津に来るには琵琶湖線に乗らないといけないのですが、京都や滋賀に住んでいる人でも間違えることがあります

f:id:wk1080id:20170325010402j:plain

*2:D: ヘイホー君と削除 - CODE FESTIVAL 2015 あさぷろ Easy | AtCoder