RUPC2018参加記

2018/03/26-2018/03/28の三日間の日程でRUPC2018に参加してきたので、漢字仮名混じり(アルファベットもあるぞ)の文を書きました。

 ━━━━━

day1

深夜7時に自宅の最寄り駅から電車に乗りました。電車に乗っていただけなのに、京都に着いたときにはスマホが息も絶え絶えでした。

京都駅でいづみちはるさん、しゃけくんさん、olpheさんと合流して駅近くのイオンモールに行きました。

大人気音楽ゲエムであるところのチュナイズームをしようと思ったのですが、人が、いました。さらに間の悪いことに100円2クレの時間帯だったので、時間的にかなりヤバいことになりました。

その後電車に乗って南草津駅に着き、ツカサさんも交えて大人気ラーメン屋さんであるところのにぼ次朗に行きました。ここも結構混んでおり、バスを逃すファインプレーをしました。

結局自己紹介フェーズの最後に入ることになってしまい、お歴々のすんばらしい自己紹介を拝聴することは叶いませんでした。

らてあさんと初顔合わせ、合格祝いに100JPY頂きました。

 

コンテスト

一日目はolpheさんとツカサさんに組んで頂きました。

Aをolpheさんが通したあと、Bの読解を担当した僕がolpheさんに解法を伝えWA、Cをツカサさんが通します。

olpheさんをDに送り出したあとツカサさんとBを考え直してAC、ツカサさんはそのあとEを通してolpheさんとGに行きました。

僕はFの桁DPを担当したのですが、微妙に違う答えが出続け、かなり大変でした。愚直解で6e6くらいを試し、結果下二桁をまとめて扱うことにしてACしました。

print~~map/51.3/,1..<>

その間Gはバグり続け、結局そのままコンテスト終了、6完でした。

解法は合ってたそうなのですが……。

 

懇親会

懇親会ではナンさんと喋りました、というか踏ん切りがつかず他の人に話しかけられませんでした。悲しいね

ほどほどのところで切り上げ、ナンさんの案内でツカサさん、いづみちはるさん、しゃけくんさんと草津のゲームセンターに行きました。

途中からそすうささんも来て、非常に楽しかったです。しかし22時閉店、あまりにもはやすぎて何が起こったのかわかりませんでした。

 

day2

起床AC、受験を乗り越えた俺に死角はなかった

ixmelさんに話しかけることに成功、デレステが上手

 

コンテスト

今日はランダムチーム、setunaさんともう一人(ごめんなさい、お名前を忘れてしまった)で出ました。

僕はギリギリDiv1扱いだったので、二人にA,Bを投げてCを解き、僕は誤読しつつもAC。

そのあとD-Fを割り振って読み、Fは場合分けやるだけだと思ったので(これは嘘)、実装を投げてsetunaさんとDを考えました。

分割を全通り試しつつ、その間の文字列を再帰的に計算してmaxという解放を生やしましたがTLE、Gに移って一般グラフを二分グラフにできないかあれこれ悩みましたが解けず、Fが難航してそうだったので考えてみると場合分けがヤバいことに気づきました。

しばらく考えて限界場合分けを生やし、実装してもらったら通って、これは嬉しかったです。

その後はGを考えていましたが解けず、結局4完、まあこれも人生

 

懇親会

肉を焼きました。

同テーブルの人々をほとんど存じ上げなかったのですが、隣に座ったナンさんと内輪ネタをブチ上げるとまあなんか会話が広がってニッコリ、しかし肉を焼くレートが負なので炭化しました。

解散してolpheさん、seicaさん、ixmelさん、そすうささん、けんちょんさんと膳所のゲーセンに行きました。

いくつかの機種でマッチングできてとても楽しかったです。

 

day3

今日も起床AC、誰も俺を止められない

 

コンテスト

今日もランダムチーム、odanさんときくちさんと組みました。

ABを投げてCを見て、見ました。紙コーディングのやる気が無だったのでお二人のコーディングを眺め、暖めておいたコーナーケースを指摘するも対処方法を間違えながら、AもBも通ったのでCを書きます。

無事通ったので、皆でDを考えます。素数判定を生やしてもらいながら考えていると、DはDPのDなのでDPをしたい気持ちになりました。数列から、

・全て素数

・取り出す間隔が1以下

・狭義単調増加

の部分列を取り出せれば、それが素因数分解前の数字と一対一対応するので、お気持ちで漸化式を立てて書くとAC、あっけなかった

Fが多く解かれていたので、Fを考えます。各辺は高々1しか伸ばさないので、辺にコストを割り振っても良いことに気づき、最小カットとわかります。最短経路に寄与する辺の探しかたをきくちさんに教えてもらい、odanさんからフローのライブラリをもらって流すとAC!嬉しい

フローの問題を解説を見ずACしたのは初めてみたいなところがある

Eに移りました。オイラーツアーをやってみたかったのでそれを使う解法を考え、範囲乗算と範囲sumの遅延セグ木があれば解けるようなところまでいったのですが、セグ木が植わってなかった……

またオイラーツアーで複数回訪れる頂点の処理が違っており、解けませんでした。

頂点の扱いについて、

・辺についてクエリがあるときは訪れるたび

・頂点についてクエリがあるときは入るときと出るときだけ

オイラーツアーのvectorにぶち込めばよさそう

結果5完でした。これは僕としては嬉しい結果

 

その後帰るタイミングを逃していると、らてあさんと愉快な仲間たち と言葉を交わす貴重な機会を頂いたので日本語を喋りました。

ripproの方々の片付けが終わるまでふぁぼ爆コミュニケーションを行った後、立命館大学のオシャレな学食に行って遅めのランチと洒落込み、らてあさんのトークを拝聴していると意識が遠く……気がつくと帰りの電車の時間が近づいてきていました。

バス内でらてあさんに合格祝いとして30JPY頂いたので、バス代に使いました。TLEの危険を感じつつ初日行ったゲーセンに急ぎ、途中駿台に中指を立てつつマッチングをしました。

1クレでさすがに限界が来たので、らてあさんに京都駅までエスコートしてもらってお別れをしました。道中大学での競プロイベントについて教えてもらい、将来の展望にドキがムネムネしたりしなかったりしました。

 

首尾よく電車に乗り込み、最寄り駅に帰り着いたときにはまたもやスマホが息絶えなんとしており、電車の恐ろしさを知りました。

━━━━━

以上です。