えびちゃんの日記

えびちゃん（競プロ）の日記です。

RUPC 2019 参加記

3 月 5 日から 7 日に行われた RUPC 2019 の参加記です．

Day 0

新千歳空港から伊丹空港に行く．日本語が下手な人になったりジンギスカンステーキ丼（ちょっとお高い）を食べたりする．

めちゃくちゃかわいい写真を撮った．

とちゃうく〜（到着）． そこから（えーと）あんまり覚えてないけど南草津駅に行く．道中で迷子になって半泣きに．

そすうさが北大勢とご飯を食べに行くとか言ってるけどえびちゃんは一緒に食べてない．えーん拗ねた，立命勢になってやる．

えーホテルどこやねん，駅から徒歩 0 分とは？ とか言いながらランダムウォークしたら 1 分足らずでそれっぽい建物を見つける．うれしい．近くにファミマがあったので晩ごはんはそれで済ませることに（えびちゃん横着がち）．ご飯の後は AtCoder Scores に先日の ABC の問題を追加したりしてた（ステマ）．

次の日の朝早いなぁとか言って早く寝ようとする．おやすみ．

Day 1

おはうく〜（無事起床）

ゴリラジオ体操に出るも，おといれに幽閉されるなどして遅めに全完．朝食のバイキングがおいしい．スクランブルエッグすき．パン用のバターをつけて食べたりした．

立命館大学行きのバス停が見つからなくて数分あわあわしたけど，西口ではなくて東口っぽいことをなんとなく察してそっちに向かうことに．駅の中でりあんさんに出くわしてわたわたしたりした（えびちゃんのこと覚えてくれてて嬉しかった）．

バスに乗って整理券を取って運賃を用意してたら他の人たちがカードっぽいものをかざして乗ってるのを発見して，情弱だったかなと思ったけど実は suica ではなくて専用カードらしいことを後から知る．えびちゃんの勝ち． これは非常に恥ずかしいのでオフレコなんだけど，運賃を入れるところではなく両替のところに運賃を入れてしまった．なんか小銭のマークが書いてあったから仕方ないよね，えびちゃんは悪くない（おいおい）．

無事にキャンパス構内に入ったけど無限に広くて迷う．なんか雰囲気でそれっぽい建物に入ってみる．

えびちゃんは Day 0 で立命の人になったので，会場に諸々を運んだりお外のスペースにお菓子を並べたりする作業をした．

受付の時間になったので，当然受付をする．参加者に名札を渡すことで顔と名前を一致させようとしたけど実質不可能．それでもたぶん何人かは覚えた．

自己紹介むずかしいね．えびちゃん緊張しがちであんまり覚えてないけど．

Day 1 のチームは事前に決めていて，seica ちゃんと碧黴さんとえびちゃんで参加．「にゃー」とか「ぷぇ(๑>﹏<๑｀)！」とか言っていたのでチーム名を nya_pue__ とかにしたら賛同が得られたのでそれにする（いいの？）． 早速チームアカウントを作るんだけど，えびちゃんのおふざけでパスワード当てゲームを始めたりした．文字数とかを伝えると無事にエスパーしてもらえた（脆弱か？）． 近くにいた olphe に「にゃー」とか言って困らせたりした（ごめんね）．

時間は早く過ぎがちで，なんやかんやでコンテスト始まりそうな時間になって，焦りつつ序盤の戦略を考える．結局えびちゃんが A，碧黴さんが B，seica ちゃんが C をやることにしたはず．

コンテスト 1

えびちゃんが焦って嘘コードを書いてもっと焦るけど，なんとか落ち着いて無事 A を AC（ぷぇ！）．みんな早すぎるね？

次に碧黴さんが B に投げるけど WA（にゃー）になってるのでソースを見てみる．怪しそうなところを見つけたので指摘して，直してもらうと AC（ぷぇ！）．碧黴さんが無限に自分を責めてた．

// この辺からすでに前後関係が怪しいけど，ざっくりあってるはず．

C 不可能か？ とか毎回全探索か？ とか考察をしてるけどつらそうなのでえびちゃんは D を読んでみる．

D は，そすうさがゲームに勝つのを助けるやつなんだけど，いやこれスターグラフとかで破滅では？ とか言って困る．よく見るとグラフは自分で作るらしいことに気づく．グラフの制約に自己ループとか多重辺とかの制約がなくて，これいいのかなーとか考えてたりしたけど別によさそう． 焦ってわけわからなくなったので seica ちゃんに相談してみる．その間に碧黴さんは C の考察をがんばってくれてたと思う．

いい感じに候補を二つに絞って進められるようなグラフを seica ちゃんが作ってくれたけど，ちょっと複雑そうなのでがんばって構築方法を考えたりした． えークエリ回数足りなくないか？ いや，枝刈りすればいいのか，とか考えるけど，冷静に考えると嘘枝刈りであることがペナルティを受けてから判明したりして困る．たぶんこの辺りで碧黴さんが C を AC（ぷぇ！）してた気がする．

えびちゃんがひらめいて，各ビットごとに辺を張っていけばいいのでは？ みたいなことを言ったら他の二人に天才扱いされる（ひえー）．なんだけど RE（にゃー）で落ちる．

// もしかしたら C を通したのこの辺りだったかも？

D のソースをよく見ると，解を出力した直後に assert(false); したりしてて（おいおい）申し訳なくなるも，直すとちゃんと AC（ぷぇ！）．

E はたぶんえびちゃんあまり関与してなくて，気づいたら通ってた気がする．チーム戦の醍醐味だね．

F を考えてたけど浮かびそうにないので G を読むのを提案したりする．seica ちゃんが「上から貪欲では？」とか言ってるので hack したりした．貪欲が無理ならフローでしょとかしゃべった． 燃やす埋めるでいけそうみたいな話になって，それっぽいスライドを見ながらお勉強する．seica ちゃんが実は NP-hard らしいことに気づいて，えびちゃんと F の考察に移った気がする．

それでも碧黴さんは燃やす埋めるをがんばって勉強してて，勇者か？ みたいな気持ちになる．結局うまくいったらしくて，seica ちゃんが細部を詰めつつ実装することに．えびちゃんは碧黴さんと F の考察をする．

seica ちゃんが何かしらでバグらせてたっぽいけどなんとか AC（ぷぇ！）．競プロ系バトル漫画でありがちな展開っぽい．めちゃ嬉しくなって，ぷぇぷぇ叫ぶ狂人になってた，恥ずかしいし申し訳ない．

F，えびちゃんが priority queue で常勝か？ とか言って書こうとするけどうまくいかない（ひえー）．そんなこんなでコンテストが終わってしまう，申し訳なさがあった．

end of コンテスト 1

なんやかんや話して時間が過ぎた後，解説を聞く（それはそう）．そすうさの C の解説がよくて，おおーってなったりした．エスパーしたやつの証明を聞くとなるほどなぁとなりがち．

懇親会で AtCoder Scores の話を振られたので答えたりする．無限に承認欲求が満たされる．

ねこ耳をつけてたら（なじんでいて忘れてたけど受付のあたりからずっとつけてたんだよね）カメラを向けられたので，にゃーんみたいなポーズをしたりする．撮影するなら先に言ってほしいにゃぁ（あるいは撮影されてなかったのかも）．

結局 い つ も の 勢とおしゃべりして過ごしちゃったけど，それはそれで楽しいので満足．beet さんに AtCoder Scores の機能追加を求められたりした．嬉しいね（そのうちやります）．

残ったお食事を処分しなきゃで，もったいない気持ちになったのでもぐもぐしたりした．おいしかったです．

いろいろおしゃべりしたりしたあとホテルに戻ってきて Day 1 終了．

Day 2

おはうく〜（寝坊）．ゴリラジオ体操に参加できなかった．ご飯を食べる．スクランブルエッグがおいしいことを知ったので，バイキングの 9 個分けのお皿の 2 個にスクランブルエッグを入れたりした．小学生っぽい．

そすうさに研究内容の話を聞いたりして，おもしろそうだなぁみたいな気持ちになってた．

前々から話は聞いてたけど †女の子集団† が現れてすごいなぁとなる．すごいなぁ．

Day 2 は，そすうさとつたじぇーとえびちゃんで組むことになってたので，それをする．つたじぇーにも耳をつけて，チーム ears で参加．耳に石詰められそうで怖いけど．

戦略は，つたじぇーに FA をとらせるのをしたくて，B を任せることにして，えびちゃんは A をやったんだったはず．考察はそすうさにおまかせ（おいおい）．

コンテスト 2

えー，A の記憶はありません．つたじぇーが解いたのかも（は？） // 書き終えてから思い出しました．ソートして出力するのをえびちゃんが書きました．

つたじぇー的には相性の悪い B だったぽくて，えびちゃんに投げられる．えびちゃんが既出を感じて実装するけど，当然愚直ではだめで，こわれる（ごめんなさい）．

そすうさに考察を手伝ってもらって，それっぽい不等式を生やしてもらう．えびちゃん焦ってて，\(O(1)\) で求まるのに「それをにぶたんで求めたらいい？」とか聞いちゃう（数分前ににぶたんかもみたいな考察をしてたからね，許してね）．そすうさは優しいので「にぶたんでもいいけど」みたいな返しをしてくれた．まぁ \(O(1)\) でやる．掛け算が怖くて（いらなかったかもだけど）Python でやることに．サンプルで落ちてるけど，ちゃんと場合分けをして無事 AC．うれしい．

この辺りから問題とアルファベットの対応がわかんなくなって，結局いまもわかってません．

こたつがめが爆発するやつの考察をそすうさから聞いて，えびちゃんが実装する．サンプル合わないけど，いろいろ試して「あ〜なるほどね」みたいになって AC，えらいえらい．

いろいろ読むけどわからず．えー難しい．

幾何のやつ（F？）は，ひらめけばいい感じになるでしょとか思ってたけどだめっぽくて諦め．これはよくないムーブだった気もするし仕方なかった気もする．

ポッキーのやつは，条件を絞ったケースで実験して雰囲気をつかんだ気になってたけど，世界一絞り方が下手だったのでだめ． 記憶が曖昧だけど，つたじぇーがいい感じの絞り方をして雰囲気をつかんでくれたので，あとは xor で常勝でしょとか言って実装する．世界一手柄の横取りが上手みたいになって申し訳なくなるけどいいよね．ちゃんと AC．

イルカがジャンプするやつ，グラフを作ってなんかしそうとか思ったけど作り方がわからず終了．

AXBXCX みたいなやつから ABCAC っぽさを感じるも，わからずそすうさに投げる．えーえびちゃん何もしてなくないか．

L は数論っぽくて，楽しそうっぽさを感じたので考えてみることに．楽しそうなやつに特攻してみるの，えびちゃんの悪い癖っぽい．

// えびちゃんはずっと L をやってて，その間ほかの 2 人が何をしてたかあまりわからず．今からその 2 人の参加記をもっかい読みます

// 読みました

燃やす埋めるが昨日見たみたいなやつ，参加記で無限回言及されてそう．

トランプを並べ換えるやつを見て，ICPC 国内予選のリボンを LR で折りたたむやつを思い出してつらそうだけど楽しそうみたいな気持ちになって，特攻してみる．操作回数を \(k\) とすると \(2^k\) で割った余りが同じ数たちが並ぶのでは？ とか思って，なんだけど順番がよくわかんなくなって，つらくなった．そすうさがんばって（ごめんね）．

木でゲームするやつを考えて，いやーわからん HL 分解！ｗ とか適当を言ったりした． A を固定したときに各 B に対する処理をいい感じにしてほしいなぁみたいなことを言ったりした．えびちゃん無責任すぎるね．

結局 L は，与えられた数たちの，与えられた素数での位数を求めて最小公倍数をとったりするとよさそうな気持ちになった．

原始根を求めるアルゴリズムを前に書いたことがあった気がするけど，探すのに手間取って結局ググる．一番上に出てきたやつに「competitive programming」みたいなタイトルがついてて「おいおい，お誂え向きか？」とか言ってた．

原始根 \(r\) に対して，\(a\) が \(r^m\) で表せるなら \(a\) の位数は（えーとえーと）\((p-1)/\gcd(p-1, m)\) かなんかそんな感じのになるはずで，それをやろうとする．\(r\) は原始根なので，\(r^m \equiv a\) となる \(m\) は絶対に存在するはずで，いいでしょとか考える．

あとはその \(m\) を求めるだけで，どうするんですか？ BSGS ですよね，つたじぇー教えて．とか言って教えてもらう．

や，冷静に考えると最悪 \(O(\sqrt{P}\times \sum |G|)\) とかで，破滅なんですが，いや実はいい感じになって通るでしょとか考えてた．

実装するも，思い通りの出力と違って，おいおいとか言ってたら実はバグってなくておいおいとか言った記憶がある（これ Day 1 だったかも）（おいおい）

サンプルがあったので投げてみる．TLE で，それはそうなんだけど，何かしらを信じて，メモ化みたいなことをしようとしたりするのを何回かやったけどだめで，えびちゃん泣いちゃった．

トランプのやつをそすうさとつたじぇーががんばって実装してたけど，うまくいってないっぽくてつらそうだった．

えーん終了（無慈悲）．

えびちゃんもほかの人と考察するのをもっと楽しみたかったなぁとか少し後悔．

end of コンテスト 2

コンテストが終わって，ほかのチームで L をやってた人の話を聞くに，BSGS の分け方を平方根以外に変えるみたいな話を聞いて，頭いいなぁとか思ってた（これくらいは思いつくべきなんだけど）（それでは通らないっぽくてつらかったらしいけど）．なんか，実は離散対数やる必要ないとか聞こえてえびちゃんまた泣いちゃった．

実は位数を求めるだけならそれ用のアルゴリズムがあるっぽくて，信じてググるべきだったとめちゃ後悔．

雨の中懇親会の会場へ．たぶくんと 575 検出をしたりして歩く．

懇親会，面白くて，beet さんがガリガリ君を飲み物の入ったグラスに突っ込んで「こうすると置き場に困らない」とか言ってた．冷静に考えて狂ってないか．

「これはイカですか」とか「これは玉ねぎですか」とかみたいな判定問題を雑に解く人たちがいたりした（WA）．弱学習器っぽい．

beet さんが席を立ってるときに，酔った人（お名前を失念しました，ごめんなさい）が「beet さんは透明人間になれるのか」とか言い出して，発想がやばいなぁとか思ってた．

えびちゃん疲れて寝ちゃってたけど，みんなおしゃべりしてて元気だなぁとか思ってた．

懇親会が終わってなぜかゲーセンへ．久々に jubeat をやって難しいなぁとか言ってた．卓球してる人たちとか，激しくドラムを叩くメイドさんとかを見たりして楽しんだ．

なんやかんやでホテルに戻って Day 2 終了．

Day 3

無事起きて朝ごはん．今日も今日とてスクランブルエッグを 2/9 にしたりする．のんびり食べてた結果，間に合わなさそうなことに気づく．間に合わなかった．

つたじぇーが問題文の印刷をしてるけど，無限時間掛かってるっぽくて困ってた．手書きした方が早いまでありそうとか言った．

つたじぇーがチーム編成を仕切っててすごいなぁとなる．見るの 3 回目なはずなんだけど，間近だと違って見えがち．

前の方に座ってた olphe に「にゃー」ってやったら同タイミングで「にゃー」が返ってきて笑っちゃったりした．

なんか朝早くて人の集まりがよくなかったり，がやがやしてたけどコンテスト開始．

コンテスト 3

提出を見ながら風船を配るやつをやる． え，2 分経っても AC 出ないんですけど，これはなに．みたいな気持ちになるけどちゃんと AC が続々出てきて焦る．

風船にテープが貼りつくと，はがすときに割れがちなことで有名だったけど，TAB くんがめっちゃ丁寧にはがしたりしてた．風船界の tourist．

TAB くんに座席表への記入と FA の記録を任せて，えびちゃんは提出を見て指示をしたりテープを量産する係をしてた．配るのを若い人たちに任せて楽をしてて申し訳なかったかも．

開始数十分で 3 完が続々と出て焦るけど，コンテスタント側だとそのくらいで 3 完くらいはできてたいのでそれはそうみたいな気持ちになる．

チーム名を見たらどの座席だったかがすぐ思い浮かぶくらいには脳が最適化されててすごかったんだけど，口が追いついてなくて「左の右から 5 番目」とか言ってた．

通ったり通らなかったりする提出を見たり，コンテスタントががんばってるのを見るのが思ってたより楽しくて，時間があっという間に過ぎた．

G が全然通らなくて，防衛力高いなぁとか思ってたけど，rickytheta さんとかがそれなりの時間に AC して，いい感じの難易度調整だったのかなぁみたいな話をする．終盤まで success rate が 100% だったりして面白かった．

Burningkotatsu の早解きがすごくて，すごいなぁとか言ったりしてた．

ohauku が A に CE を投げて共有してたので，コードを見てみたら末尾に「不可能ですが...」とか書いてて笑ってた．ちなみに #error という命令が存在します．

結局，不可能が可能になって ohauku が優勝．さすがすぎる．

自分たちの作ったテストケースでコンテスタントを苦しめてるのとか，コンテスタントが自分たちの問題に時間ギリギリまで取り組んでるのとかを見て嬉しくなってた．

end of コンテスト 3

解説をしたりして終了．えーあっという間すぎないか，困る．

お片付けをする．monkukui が静かに風船を割るプロになってたり，waku がきたない音を出して風船をしぼませるプロになったりしてた．

えーん，毎日が競プロ合宿だったらいいのに，とか思うけど，こういうのはたまにあるからいいんだよね．でももっといっぱいしたいしもっと長くやりたい（わがまま）．HUPC 開催したら人々来てくれるのかなぁ．

参加記を書き終えると合宿が終わっちゃった実感が湧いて寂しくなった．