ゆらのふなびと

競プロ, Python, C++

RUPC2017 参加記

RUPC2017（立命館大学競技プログラミング合宿2017）の参加記です．

atnd.org

昨年に引き続き 2 度目の参加．チーム戦ができる数少ないオンサイトということで楽しみにしていました．

Day 1: 立命館&阪大セット

この日は作問チームに参加していました．

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=RitsCamp17Day1

経緯としては，立命館の作問人員が足りなくて大変という話を Yazaten さんから聞いていたので手伝うよと言っていたところ，誘っていただいたという感じです．阪大もくっついて巨大化したのでむしろ問題数が増えて 4 時間 11 問になりました*1．当日までは，問題案を投げたりテスター解を投げたりしていました．

会場に向かう途中，湖西線トラップ*2にひっかかり近江舞子まで行ってしまいました．おかげで駅メモが捗りました． 会場に着いたのはコンテスト開始 5 秒前でした．

僕が作問を担当したのは E 問題「卒業式」と I 問題「Islands Survival」です．

E 問題は，自分の作問ストックにあった問題にストーリーをつけて出したものです．卒業式と RUPC が被っているフレンズが多かったのでネタにしました．

I 問題は，ノートにグラフを描いて遊んでいたら生えました． 生えたての頃は入力のグラフが木に限られていて「Tree Survival」という問題名だったのですが， Slack で議論していたら木じゃなくても解けることに気づき，「Islands Survival」になりました． 絵を描いてみると解法がわかる感じが気に入っています． 実装が少し辛いのもあってか，本番の AC 数は下から 2 番目でした．

コンテスタントのみなさん，作問チームのみなさんありがとうございました． また機会があればどこかの作問チームに紛れ込むかもしれません（？）

余談ですが，作問の副産物として，数式・アルファベットの両端に半角スペースを入れる習慣が身に着きました．スペースがないと地味に読みづらいので，問題文を書く人はぜひ気にしてほしいです*3．

コンテスト後は学内で懇親会でした．生協の揚げ物フィーバーだったので，油の摂取量がオーバーフローしないように気をつけていました．同学年の競プロerたちと就活話をしたり，n_vip さんや rian さんを特定したりしていました．

家に 2 時間半かけて帰ると既に 23:30 で感情を喪失したので，次の日は会場最寄りのアーバンホテル南草津に泊まることにしました*4．

Day 2: 会津セット

7:19 に限界集落を出発し会場へ．

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=RitsCamp17Day2

この日は odan さん，tsutaj さんとチーム toy18 で参加しました*5．

昨年の CODE FESTIVAL でもらったノートをまだ使っていなかったので，この機会に使うことにしました．

この辺りから敬体と文体が混ざります(sorry)

～～～コンテスト開始～～～

C 問題を読む．構文解析っぽいので NLP のプロである odan さんに投げる．

代わりに A 問題をやることに．式が書いてあったのでそれをありがたく使わせていただくが WA．別に式が間違っていたわけではなく，僕が出力する角度を [0, 360) の範囲に納めるのを忘れていた．AC したけど意外と辛かった．

次は E 問題を読むことに．「比の最小化→二分探索」は幸いすぐ気づいた*6．操作後のグラフは全域木になるので，最大全域木をやればよさそう．クラスカルを写経して submit したが WA．よく考えると，全域木側で比を最大化したからといって，他の辺についての比が最小化されるとは限らない．適当に式をいじったら実装できる形になったので書いて AC．FA が取れて歓喜．

D 問題を解いていた tsutaj さんがバグっていて辛そうだったのでヘルプに入る．当初は dp[i][j] = ( i 日目までに励まし力を j 使ったときの，今まで登校できた日数の最大値) という O(NP) の DP を考えていたが，それが嘘だと気づくのに 10 分ほどかかった．i 日目に必要な励まし力を求めるには，i - 1 日目までに連続で何日登校したかが分からないといけない． 紆余曲折を経て dp[i][j][k] = ( i 日目までに j 日登校し，i - 1 日目までに k 回連続で登校したときの，残っている励まし量の最大値) という DP に至る．励まし量を添え字ではなく配列の値にするというのは，ナップザックの重みと価値を入れ替えて DP するやつのイメージで考えていた．添え字のエラーにさいなまれながら AC．

I は BIT を 10 個持てばよさそうという話を聞くも，change クエリの処理方法がわからずパス．

F は最小カットっぽいけど，サイズが大きいので最大流できない．よく考えると，岩は少なくとも 2 個あれば非連結にできるので，岩が 0 個 or 1 個で済む場合の判定だけ真面目に考えればよい*7．方針としては岩を set に突っ込んで DFS すればよさそうということを言って odan さんに任せる．コンテスト終了 5 分前くらいにバグが取れたものの TLE．set を unordered_set にしたら通るのでは～？と思って書き直すも，コンパイルエラーが消えず間に合わなかった*8．

～～～コンテスト終了～～～

E を自力でさっと解けたのはよかった．D や F も考察では貢献できたものの，実装ではいろいろ振り回してしまって申し訳なかった．F は UnionFind でやると楽という話を他のチームの人に聞いて納得した．「連結性の判定→UnionFind」は出てくるべきだった．

実装に時間がかかり，後半の問題にほとんど目が通せなかったのが悲しかったです． 解説を聞いていたらどの問題も面白そうだったので，解きます．

懇親会の写真はたぶんみんなが上げます．お腹が MLE しそうなほど食べられて幸せでした．ありがとう御社．

↓ホテルからの写真

Day 3: 北大セット

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day3

rian さん，Pulmn さんとチーム ElogV で参加しました*9．

北大の運営陣が tsutaj さんが 1 人だけで大変そうだった（ありがとうございます……）*10

～～～コンテスト開始～～～

A 問題を読む．よくある回文の問題なので適当に実装して投げるが WA．文字長が奇数のときの処理が間違っているのを rian さんが指摘してくれたので直して AC．結局切り上げを切り捨てにするだけでよかった．

E を読むとセグ木っぽいが，セグ木の経験値が低いので投げたくなった．D を読んでいた rian さんもグラフっぽいけどよくわからないという状態．僕はグラフの問題が好きで，rian さんはグラフよりはセグ木の方がいいという感じで不安定マッチングだったので D と E を交換した．D の速度の範囲が小さいことは rian さんが気づいてくれていたので，適当にダイクストラをすればよいだろうとたかをくくる．頂点 1 → n → 1 のサイクルの最短距離を求めるというのが特殊だが，それは頂点 n を既に経由したか否かのフラグを持てばよさそう．結局 d[i][j][k] = (頂点 i に 直前の体感速度が j でたどり着き，すでに頂点 n を経由している (k=1) / していない (k=0) ときの頂点 i までの最短距離) としたダイクストラを書いてAC．

僕が D を書き終える頃には rian さんが E の方針を立ててくれていた．連続する 1 の区間を set で管理すればよさそうだが，rian さんが使っている C# には lower_bound がないので辛いということで，僕が実装を担当することに．といっても僕も慣れていないので C++er の Pulmn さんに助けを求めるなどしていた*11．実装に 30 分くらいかかって submit するも WA．更新処理で足りていない部分があることに気づく．G の解法を rian さんと Pulmn さんが生やしていたので G を rian さんにコーディングしてもらいながら，僕は E の足りない部分をつめていた．その後は submit→WA→PCを明け渡してデバッグ→コーディング→……を繰り返していた．結局 E も G も通せず時間切れ．

～～～コンテスト終了～～～

G は完全に解けていたようなので，E を捨てて G に PC を明け渡した方がよさそうだった．特に 3 時間という短いセットだと，自分の実装力の限界を知ることは大切かもしれない*12．

rian さんの指摘力がすごかった．A の WA の理由をすぐ見つけてくれたり，B の実装を Pulmn さんが辛そうにしていたのもサポートしてくれたりしていて，チーム戦慣れを感じた．

解説を tsutaj さんが 1 人でやっていてプロだった．

予定があったので，解説が終了すると早々に会場を去りました．

御社にスポンサー感謝の旨を伝えてきました．

金銭面での援助は学生には本当にありがたいです．

まとめ

やはりチーム戦は楽しい．今年は ICPC に出場するつもりなので，できるだけ長く楽しめるように頑張りたいと思いました．

昨年に比べると自分の典型力*13が上がっていることが実感できたのはよかったです（Day2E, Day3Dなど）．一方で，「これは解けない」「絶対バグる」等の感覚はまだまだ鍛えていかないといけないと感じました．もちろん典型力を上げる方も（セグ木で殴る力など）．

3 日間楽しかったです．運営のみなさん，参加者のみなさん，スポンサー様，ありがとうございました．RUPC はみんなでコンテストを楽しめる場としても，競プロer の交流の場としても非常に良い機会だと感じています．決して簡単に運営できるイベントではないと思いますが，来年もみなさんと一緒に RUPC に参加できることを楽しみにしています．僕にできることがあれば手伝いますので，なんなりと言ってください*14．

*1:昨年は 3 時間 7 問だった

*2:琵琶湖線の「湖西線経由」に乗ってしまった

*3:day1 作問チームでは tubo28 さんのご指導によりスペースを入れていました

*4:1 人用の部屋がちょうど 1 部屋だけ空いていて助かった

*5:toy は 3 人の頭文字．18 はみんな 18 卒(B3 or M1)だったので

*6:「これ蟻本で見たことある！」

*7:SRM の div1easy に似たような発想で全探索に至る問題があった

*8:原因は hash を unorder_set を使う「前に」定義していないことだった．気をつけよう

*9:チーム名は Pulmn さんの発案．ダイクストラの計算量

*10:先輩たちはみんな卒業式だったらしい

*11:知見として，set.erase(itr1, itr2) で [itr1, itr2) の範囲を一気に削除できることを知った

*12:ICPC国内予選しかり

*13:「典型力が高い」とは，「典型と思える範囲が広い」ということだと思っています

*14:他のイベントでも，割とやりたがりなのでどうぞこき使ってください