足跡-sokuseki-

りかの日進月歩の記録

RUPC2019（立命合宿）参加記

競技プログラミング 参加記

3/5(火)から3/7(木)に行われたRUPC2019（立命館大学競技プログラミング合宿2019 : ATND）に参加しました。

Day0

今年は前泊をしていたので、同じく前泊していた北大の人とまぜそばを食べました。


Day1 立命館大学セット

運営なので受付をしていました。
自己紹介フェーズでネタに走っている人がいて面白かったです。
チーム決めは今回から自動でいい感じにやってくれるアプリケーション（Competitive Programming Team Maker）を使うことにしました。結構良かったと思います。tsutajさんありがとうございます。


コンテストは3時間7問のセットでした。
去年のRUPCでは風船配りがなかったんですが、今年はぜひともしたいという気持ちになったのでしました。最初30分くらいのABの風船を配るフェーズがバタバタしていたのでつらかったです。
すぐにACが量産されないように、次からはAやBの難易度を上げたい気持ちになりました。

FGが防衛問題になっていたんですが、オンサイトでも2時間くらいで全完が出てしまいました。（といいつつ、ランダムではなく事前にチームを組んでいた強いところだったので、セットの難易度は悪くなかったんじゃないかと思っています）



コンテスト後の解説はC問題を担当しました（後で何度も間違えられたんですが、原案ではないです）。自分もC問題の原案を初めて聞いたときはぼっちオセロで実験したなあと昔を思い出しながらしゃべっていました。

懇親会はいつもの学内のところでやっていました。デザートがあったのは初めてな気がする。
いいセットだったといろんな人に言ってもらえて嬉しかったです。
いつもの勢とばかり懇親していたのでもう少しいろんな人と話せばよかったなあと今になって思います。


Day2 会津大学セット

Day2は事前にチームを組んでいたので、はい。

以下時系列がちょっとあやしいかも。

実装が嫌いなので考察しかしませんと宣言して、はじめはAとBをtsutajさんとえびちゃんに任せてCを読むことに。Aがすぐに通ったので、Cの問題概要をtsutajさんに伝えると、配置の9!通りを全探索すればいいと言われて、それぞれで文字列をなめてコストを求めるのは時間がかかるので、任意の2つの数字間の移動を何回行うかを前計算しておくといいって伝えたら実装してくれました。Bがつらそうだったので、Cの実装の間にBの解法をえびちゃんと考察すると、割り算をするだけだったのでえびちゃんに実装を任せるとpythonで書いてくれました。
順位表をみるとGが結構解かれていたけど、ちょっと考えたくらいだとわからなかったのでDEを考察しはじめる。DはtsutajさんがDPでできそうと言ったので任せる。Eは4近傍ではなく8近傍の移動を遷移として最短経路を求めると良さそうとえびちゃんに伝えると実装してくれる。DバグったみたいだったのでえびちゃんがEを実装する間にtsutajさんとHを考えようとすると、すぐにtsutajさんが燃やす埋めるで解けると言い始めたので、プロか？ってなった*1。DのバグがわかってACして、Eも考察漏れがあったのを直してACしたので、tsutajさんにHの実装をたのむ。
Gはよくわからなくて、Fの幾何も無理そうだったのでI以降に目を通すことにする。HがACしたあと、えびちゃんとtsutajさんがGを考察すると解けたっぽいので実装してもらうとACした。
あとは、
I：えびちゃんが実験してた。あと、dからkを復元するときに、復元できる数は区間で表せそうとかなって、-1判定は難しくないのでは？とかなる
J：なんか無理そう。
K：AとBを決め打ちすると、それぞれが近づく場合は面倒だけど、遠ざかる場合はあとは独立に考えられるよねというところまでは考察できる。
L：数学ができないのでつらいなあと思っているとえびちゃんがいっぱい頑張ってくれた（原始根？とかよくわからないんですが、惜しいところまでいったみたい？（よくわかってない
M：答えを決めるとXが一意に定まるので、答えを二分探索してSAをしてうしろにあるXから被らないように貪欲に3つとってきたいんですが、具体的な方法がわからずひるど
みたいなかんじだったので、Iの解法を生やして実装したらサンプルが通らなくて嘘って気づいてえーんってなってるうちにコンテストが終わりました。

コンテスト後は大学から懇親会の会場まで歩きました。雨が降ってて険しかった。
懇親会では即興で作問してみんなに解いてもらう会みたいなのをしていたのを見ていて、おもしろかったです。ビールにガリガリ君を入れて飲んでいた甜菜がいてウケた。


いま気づいたけどこのツイートの画像の背景にメイド服がある…？
いつもの勢とばかり懇親していたのでもう少しいろんな人と(ry

懇親会後はゲーセンに行きました。たのしかったです。

Day3 北海道大学セット

集合時間が日に日に早くなっていくことで有名な会津合宿・立命合宿なので、朝がつらいです。

Day3も事前にチームを組んでいたので、はい。


参加者でAtCoderレート1位のびーとくんがいればこわくない！wって気持ちで。

戦略はびーとくんが後半を解くので、せいかちゃんと一緒に前を埋めるって感じでした。
順当にレート順で自分がAを担当してBをせいかちゃんが担当することになりました。

コンテストが始まったのでAを実装すると思っていたより面倒でつらい気持ちになりました*2。AC。せいかちゃんがBを実装していて、自分がCを読んでいたらびーとくんがいきなりEわかったとか言い始めて怖かったです（プロすぎでは？）。
せいかちゃんとびーとくんが交互に(?)実装している間、Cを考察する。Cは最初、今までに宣言した数よりも小さい数しか宣言できないって誤読していてサンプル意味不明か？ってなってた（申し訳なさ）。いろいろあって、BとEが通ったあと、最大値は 約数の個数-1 で最小値は 素因数の個数 であることがわかったので実装しました。その間せいかちゃんがD、びーとくんがFを考察していて、CがACしたあとDの考察に加わる。Dは区間ごとに損失がiであるような個数をしゃくとりっぽく(?)求めてあげるといいねってなって、書いてサンプルを試すとあわなくて悲しい気持ちになりました。
びーとくんのFの考察をきくと、赤と黒の間の辺の数え上げ方法がわからないってなってるみたいで、3人*3で少し考えると片方の使わない数を決め打ちして包除ぽいことがわかる。
Dをデバッグしていると、一番最初の区間だけは任意の長さの矢について区間の長さの数だけ損失が起こることがわかったので、それを直すとAC。びーとくんもそのあとFを通す。すごい。

3人でGの考察をするとDPであることがわかるんだけど、閉路検出のためには状態をたくさん持つ必要があって、正気か？みたいな空気になる。「まああと1時間あるのでがんばりましょう（主に実装するびーとくんが）」ということで、自分とせいかちゃんが一緒に遷移を考えながら、びーとくんが7次元DP（異常）を実装していく。実装が終わってサンプルを試すと1つめは合うのに2つめはあわなくて、3人でデバッグをしていると、実は閉路検出をするときにはもっと状態が必要で、サンプル1ではそれがなくてもうまくいくみたいで、うく。びーとくんが11次元DP（やばい）に直してサンプルを試しても合わなくて、つらい気持ちになりながらデバッグを再開すると、添字ミスがあったみたいでAC。
15分残して全完です！！

オンサイト1位で、オンサイト2位のBurningkotatsuが終了までに全完するとペナで負けるなあとか全体1位のrickythetaさんはGみたいなのすきそうとかいう話をする。
その後は全完チームがでないままコンテストが終了し、オンサイト優勝！！

その後の解説では、ほむ愛してるチームがtsutajさんが解説する問題でFAをとって てんほむ をしていたりして面白かった。

そして、tsutajさんが閉会のあいさつをして、RUPC2019は無事終了しました。とっても楽しかったです。
参加者のみなさんが、RUPC2019を楽しんでくれたみたいで、運営としても嬉しいです。
参加者のみなさん、会津大学・北海道大学のみなさん、ありがとうございました。

*1:Day1で燃やす埋めるをずっと考えていたらしい

*2:制約をちゃんと読んでいなくて、入力がuniqueではないと思っていた

*3:3人といいつつ、ほぼびーとくんとせいかちゃん