hogecoder

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

RUPC 2018 参加記

勉強会参加記

立命館大学競技プログラミング合宿 2018 (通称 RUPC 2018) に参加しました。去年に引き続き 2 回目の参加です。いやあ濃密な三日間だったなあ・・・

以下時系列順に振り返るいつもの

Day 0 (前日)

飛行機が遅延しまくる。11:10 離陸予定の飛行機が 15 時に飛んだ (は？) おかげで観光できず。大幅遅延は事前 (搭乗前日) に知らされていたとはいえ、残念な気持ちになる。

宿についてすぐに ARC があったので参加したけど構築が一生解けなくて人生終了した。こう振り返るとなんか虚無イベントしか起こってないような・・・。

Day 1

深夜バス組が南草津でボドゲを朝からやるらしいので、京都に普通に泊まってた自分も早起きして参加した。CODE THANKS FESTIVAL 前のボドゲ会にも参加してた人々が多くて、再会できてよかった。ギャンブラーギャンブルをやるとらてあ氏が無限に勝つのですごいと思いました (小並感)

コンテスト

立命館大学に移動して、コンテストのチームを乱択する。自分はうくさん ( @ukuku09 ) と、 wheson さん ( @wheson ) と組むことになりました。

最初の方針としては wheson さんが A を、自分が B を、うくさんが C を読むことになっていて、B を読んだのですが、国語と数学が壊滅的なため題意が一生わからなかった (後でうくさんに投げてしまった)。自分が題意理解フェーズしている間に wheson さんが A を通してくれた。

C はうくさんから問題文を聞いて map に入れるだけ解法はすぐ思い浮かんで、最悪ケースで普通に二乗オーダーになるのでやばそうだなあと思ったけど、投げたら通ってウケた。長さ最大で回文みたいになっている数列が来たらやばそうではある。そしていまだに B がわからない。

wheson さんとうくさんが B の解読に努めて、自分はとりあえず後ろを読むことに。D は区間 DP みたいな気持ちになるけどわからない。なんか E は全部張るだけでよさそうなので書いたら通る (この問題、最初有向グラフだと思っていた・・・)

F は若干面倒な桁 DP っぽいのでとりあえず飛ばす。G は最初見たとき並列二分探索かと思ったけどそれすらいらなくて、単にクエリを時系列順にソートして状態を更新していけばよい。セグ木でいい感じに書けそうだったので書く。若干バグったけど AC。

ここで全員で B と格闘するもまだ通らない。つらすぎでは？ (ここで 1 時間弱 AC がない虚無を過ごす)

F に戻ってきた。パターンが含まれていない文字列を数えて全体から引くと良さそうだと気づく。早速書くけどコーナーに引っかかって 1WA しつつ AC (自分はパターンの何文字目まで一致したかを状態として持ったけど、下 3 桁持ったほうがコーナー気にする必要なくて圧倒的に楽ですね)

あと F を書いてる途中で D の解法が浮かんだ。区画 merge の順番が関係なくて、最後にどうなっているかだけ気にすれば良いため、普通に左から DP すればよい、ということをうくさんに伝えて書いてもらって AC。

そしてさらに B がやっと解決する。出力の順番罠やんけ！

結果的に全完した (奇跡) 後ろの問題全部解けたので気持ちよかった。

懇親会

ひとがおおくてすごいなあと思った。去年よりも 30 人増えてますもんね。

去年は会話した人を記事に列挙できるくらいの人数だったけどもう列挙できないくらいお話しました。たのしかったです。自分とお話してくれたすべてのひとにありがとう。

Day2

なんか会場着いたらチノちゃんとティッピー載せた成人男性がいるけど

コンテスト

この日は事前にチームが決まっていて、 うしさん ( @ei1333 ) と treeone さん ( @treeone79 ) と組みました。

コンテスト開始 1 時間前が集合時間なんですが華麗に遅刻 (30 分遅れ) (ごめん)

うしさんはコンテスト開始 30 秒前くらいに到着、パソコンを開いたら FA が奪われていたらしい。さすがのうしさんもパソコンの起動時間には勝てなかったらしい。

B 問題担当ワイ、WA を出す (は？) もなんとか AC。A 問題と C 問題もチームメイトによって気が付かない間に片付けられていく。

D 見た一同、これ不可能では？？となる。あとで気づいてたんですが問題解釈間違ってたね (かなしいね)

F はうしプロと treeone プロが通してくれた。 I は制約的に bit DP で、点集合を全て覆うような円の最小半径が欲しい気持ちになるので適当にググったら tubo さんの記事を見つける。前でチーム戦をしている tubo さんに感謝しつつ貼ってメモ化再帰を書いたら TLE する (えぇ・・・) いやオーダー的には大丈夫だよなあと思ってループで書き直したら AC した。メモ化再帰が世界一苦手。

H はうしさんが「あぁこれは Suffix Array でいけそうだなぁ破滅だなぁ」とかなんとか言いながら通してた。プロすぎる。このへんからうしさんが床コーディングをはじめる。

G は一般マッチングが欲しい気持ちになって、これまたググったら出てきたのでうしさんが貼って提出。 N \leq 800 の O(N^{3}) だけど難なく通って草。

相変わらず D は破滅なので J とか E とかをやるも破滅する。後半は全員で破滅虚無人生終了コーディングしてた。つらい。

あとで気づいたけど E の悪魔的ケース気づいてなかったね。

懇親会

焼き肉！！！なんかやたら火力が強くて、定数倍高速化を極めた焼き肉とか言ってた。

食べて飲んだあとは近くの温泉に入って疲れを癒していました。やざてんさんのかばん無事でよかった。

Day 3

コンテスト

泣く子も黙る †admin† でした。コンテスト開始 2 時間前から会場入りしていたんですが割とちょうどよい感じで準備が終わって、チーム決めたり解説編集したりしてました。

割と典型を集めたセットになっていて、全完はでるだろうとは思っていたけど、おわってみれば 19 チームが全完していて、これは想像していたよりもはるかに多い数でした。次回はもっと難易度上げるか！ｗ 皆さん解いてくれてありがとうございました。

その後

その後は立命のキャンパス内にある超いい感じの食堂？に行ったり、南草津駅で虚無をしたり、再びカラオケ屋でボドゲをしたり、某 treeone の通知欄を破壊したり、京都でご飯を食べたり、某 treeone に通知欄を破壊されたりしました。南草津着いた後はずっと olphe さん・TIke さん・フェリンさんと遊んでました。正直超たのしかったです、ありがとうございました。

まとめ

いや立命合宿は楽しいかな〜やっぱｗ チーム戦も楽しめるし作問もできるし (聞いてないｗ)

来年もまた参加したいです・・・！！！