hogecoder

tsutaj 競技プログラミングの記録

RUPC 2019 参加記

勉強会参加記

立命館大学プログラミング合宿 2019 (RUPC 2019) に参加しました。RUPC への参加は 3 年連続 3 回目です。

Day 0

飛行機で関西国際空港に到着、その後電車で立命館大学まで移動。空港に 14 時半 くらいに着いたし、集合時間の 18 時にはまあ間に合うでしょうと思っていたんですが意外と電車の所要時間が結構あって遅れそうになる。それでも天才的乗り換えにより乗り換え検索アプリ上の到着予定時刻よりも 20 分ほど早く到着、なんとか間に合う。

晩御飯は立命のりかさんと、北大のろであ君・TAB 君と一緒にまぜそばを食べた。おいしかった。

Day 1

参加者の受付開始。立命に続々と競プロ er が集まってくる。

自分が作った チーム分けアプリ を使う際に必要な情報 (HN や AtCoder ID など) を参加者に教えてもらう。皆さんご協力ありがとうございました。

自分は事前にチームが決まっていて、てんぷらとけんちょんさんと一緒に組むことに。とりあえずレート順に問題を見ていこうということになったので自分が A を読むことになった。

コンテスト開始。A はさすがにちょっとした計算をするだけっぽい。題意を若干間違えるも 1:45 でオンサイト FA を取る。その後てんぷらが B を通してこれもオンサイト FA。

C はけんちょんさんの担当だったがチラ見させてもらった。なんかやばそうな雰囲気を感じ取る。

D を読んでみる。なんか構築とインタラクティブの雰囲気を感じて途端にやりたくなくなる (は？) これは自分がやらないほうがよさそうなのでてんぷらに投げて E を読む。ペアのセグ木を持てば更新ができそうなので書く、通る 全体 FA だったのでうれしいね

自分が F を読んでいる間にてんぷらが D と C を立て続けに通す (やばい)

残っているのが F と G だけになったので自分とてんぷらが F を、けんちょんさんが G を考察することに。数列の値とインデックスの値をまとめてソートして上半分と下半分に分けて考察していくと良さげな方法をてんぷらが思いつく。実際あっていそうだし実装も大丈夫そうなのでやってもらう 通る ここまで 1 時間で相当いいペース

最後は G で、フローである、もっというと燃やす埋めるであることは疑っていたがどのようなグラフを構築したらいいかがなかなかわからない。グラフの頂点が何に対応するかを少し変えて考察するとうまく行きそうなことに気づき、更に同色ペナルティ (伝わって) 制約も二部グラフなので頑張れば表現できる・・・みたいなところに行き着くまで 1 時間以上使った気がする。

実装してもらうも WA が出た。サンプルケースの値を少し変えて実行すると答えがおかしいことに気づく。インデックス周りが間違っているらしい。それを直すと通る！！

結果は全完でオンサイト 1 位。終盤で逆転したので嬉しかった。

この日の懇親会会場は学内だった。2 時間ずっと競プロの話ができて楽しかったです。初めてお話できた方々も多くいてよかった。

Day 2

この日も事前にチームを組んでいた。りかさんとえび君とチームを組んで出ることに。

コンテスト開始。B を最初に読んだが明らかに苦手なのでチームメイトに投げて C を読む。全部のパターンを試せることに気づいて、数字列も (前, 後) のペアの個数を持っておけば高速に処理できるとりかさんにアドバイスをもらったので書く 書き終わるまでに少し時間がかかったが通る

自分が D, H を、えび君が E を担当して、りかさんに他の問題文を読んでもらった。D は y = 0 を考えていたためにサンプルが合わず虚無を過ごしたが通る。その後 E も通る。

H は Day1 G を解いているならかなり楽に書けるため書く 通る 問題演習大事だね。

しばらくして G の解法も思いつく。1 本だけ棒があった際に勝ち負けがどうなるかはわかるため、あとはそれを Grundy 数にして考えればよい。えび君に書いてもらって AC。

その後は F や K, I, L, M などに手を付けたが AC が増えず。特に L をえび君がずっと考えてくれたり、I をりかさんがずっと考えてくれたりしていたが、あまりアシストできなくて申し訳なかった。

懇親会は居酒屋で行われ、他大学の ICPC 事情や今回の合宿のセットの感想などをワイワイ話す。今回は平和に終わったのでよかった。

Day 3

北大セットなのでジャッジ側に回る。 8 時に集合して準備をすすめたにもかかわらずプリンターの速度がおそすぎて A しか刷れなかった (えぇ・・・)

チーム決めも無事終わってコンテスト開始。開始すぐの段階で A, B, C の AC が出て、開始 1 時間時点では 5 完のチームもいた。その後主に G 問題に阻まれ全完が出るのかどうかという展開になったが、まず rickytheta さん (オンライン) が全完。その後 rupc_ohauku チームも全完、結果的にかなり良いバランスでコンテストが終了したので難易度設定はこれくらいがいいのかもしれないなと思った

自分は C, F の Writer と全問題の Tester をやっていました。なんか自分が Writer をやった問題に対して rupc_homu_aishiteru チームが FA をとったので解説時に homu_aishiteru を読み上げさせられる事態になった。 包除原理はぜひ覚えて帰っていってね！

そしてなぜか自分が締めの挨拶をした。運営っぽいことができた。

その後ご飯を食べたりゲーセンに行ったりご飯を食べたりした。大いに懇親できた気がする。

総括

参加者の皆さん、運営さん、ありがとう！！！たくさん楽しみました！！！！！

またお会いしましょう〜〜〜