RUPC2019参加記

 RUPCに初参加しました。というか合宿系イベントとかチーム戦とか自体初参加でした。

 

1日目

 起床に失敗して自己紹介できませんでした。コンテストはけんちょん(@drken1215)とつたじぇー(@_TTJR_)と組みました。

・つたじぇーがAを爆速で通してオンサイトFAを取る(1分)

・その勢いのままBを論理和っぽく書いたらif文列挙勢に勝てたのかオンサイトFAだった(3分)

・Cでけんちょんが詰まってて見たらたしかにやばそうなので一旦捨てることにする。つたじぇーがゲーム構築インタラクティブっていういかにも僕っぽいDを投げつけて実家っぽいEにいく。なんか一瞬で通して全体FA取ってた、すごい。(16分)

・Dを考えるとインタラクティブなのでにぶたんをしたくて、辺をうまく張るとできることがわかるので書く。手元でしっかりめにテストして出すと通る(30分)。新しいタイプの形式でかなり面白いと思った。

・とりあえずCに戻って1人でオセロして遊ぶと規則性がなんとなくわかったので「エスパーします」って言って書いたら通る(40分)。これwriterが天才すぎる。

・ほむと一緒にFを考える。添字n個と数列n個の計2n個のなかでなるべく大きいものと小さいものを組ませたいよなぁと思いながらサンプル3の上位n個に◯をつけてみたらすべてが解決した(61分)。全体FA、やったね。

・あとはGだけで燃やす埋めるっぽいので色々と試行錯誤をしているとほむが装置だけみればいいことに気づいて(天才)、けんちょんが2部グラフだから反転するとできることに気づく(天才)。ぼくはわからないのでお菓子食べてた。ちょっと添字がバグってたらしく1WAしたけど無事全完(170分)。ペナ差で逆転してオンサイト優勝。嬉しいね。

 

 懇親会はわりとちゃんと懇親した気がする。初めましてもいっぱいできてよかった。

 

2日目

 起床は成功よりの失敗。会津セットだしKUで組むかということでへの(@heno_code )とやむなく(@yamerarenaku )で組む。意識が高いので3日前くらいに去年のセットでばちゃをしてから臨んだ。

・へのがAを通す(1分)。僕がBを考えるけど全然できないのでへのに投げる(は?)。ごたごたしてる間にやむなくがCを通す(12分)。へのがB, Gを通す(18分)。BがオンサイトFAでGが全体FAだったらしい。

・やむなくがEが解けたらしいので書いてもらう。CEが出て辛そうだったけど通る(47分)。その間に見ていたDが普通にDPでできることに気づいたので書くと通る(55分)。これもオンサイトFAだったらしい。Dを書く前にチラ見したHが燃やす埋めるっぽかったのでやむなくに投げたら僕が書いている間に考察が終わってDが通った5分後にはACしていた、早すぎる。

・Fはとりあえず辺を決めれば良さそうというとへのがO(N^2)をすぐに実装してくれる。投げてみたらTLEしたけどへのがしゃくとりに気づいてすぐに書き直してAC(103分)。実装が強すぎる。

・Jの物理パートだけ計算して実装はへのに任せる。この時点では単調性があると思ってた(うく)。Iを考えていると突然逆から見たくなる。逆から見ると操作はk -> 2k % n , 2k+1 % n の2択だとわかって、これはシフトしてbitを立てたり立てなかったりする操作なのでできる(146分)。4つめのオンサイトFAを獲得する。

・Jで単調性がないことに気づいて破滅する。やむなくの指摘でLの誤読に気づいて考え直すとこれは原始根の指数でGCD。が制約を見るとBSGSじゃ厳しそうなので強い気持ちでBSGSを捨てると位数を考えるだけで十分なことがわかる。位数はp-1の約数のみ考えれば十分で素因数ごとに見ていくことができるので書いてみたらサンプルがあう。投げる。AC(202分)。5つめのオンサイトFA。NO_FAとはなんだったのか。

・Jが一生あわなくて悲しい気持ちになる。DPをしようとしていて、横でやむなくが区間スケジューリングっぽくできるっていう主張をしてくれていたらしいけど脳が死んでいて捨ててしまう。ほんますまん。

 結果10完でオンサイト優勝。でも時間の大部分を費やしたJを通せないのはつらいね。メンバー相性がかなりいいことに気づいてしまってICPCこの3人で出ませんかって僕が言いまくることになる(パワハラ)。

 

 懇親会は大半ほむにくっついてた。終わったあと卓球をしたりもした。楽しい。

 

3日目

 起床成功。ほげもち(@hogemochi ) + ランダムにしたらみかん(@mkan_0141 )さんと組むことに。チーム名をhomu_aishiteruにすると同時にコンテストの目的がFAになる。

・A~Cをみかんさんとほげもちにお願いしてDから読む。ほむがwriterな問題はFだとわかるのでFから考えると赤の個数決めうち包除原理でできることがわかる。みかんさんがAを通してくれたのでFを書いて出すとFAだった(20分)。大勝利。

・ほげもちがBを解いてくれる。Cを読むと約数の個数と素因数の個数を数えればいいとわかるのでみかんさんに書いてもらいながらDを考えたりする。

・Dを書く、落ちる。デバッグする。落ちる。まだバグってる。直す。デバッグ出力の改行を消し忘れててPEする。消す。落ちる。#define int long long する。間違えてEに投げてTLEする。Dに投げなおして落ちる。何もわからん、やめるか(最悪)。

・Eを考えるとロリハでいけそうな気持ちになるけどなんか実装が嫌になる(正直Dが通らない時点でかなり萎えてた、すみません)。楽しそうなGにいくと嘘が生えるけど当然あわない。

・ついにほげもちがDのバグをみつけて直す、通る(165分)。最初のsubmitから100分+7ペナは無にもほどがある。大反省。

結果はオンサイト8位くらい。DのバグとEを実装できないのがひどくて、それは橙無理ですねって感じ。Fのwriterと解説は予想通りほむで、「FAはほむあいしてるです」を言わせることに成功する。ほむ愛してるよ。後から気づいたけどここまでちゃんと当てられるなら「FAはてんぷらあいしてるです」を言わせたほうがおいしかった。次回以降の課題。

 

帰ってそのままバイトに行く。おうちに帰るまでがRUPCなので塾講は実質RUPC。過去にへのを相手に授業をしたことがあることが判明してウケた。

 

最後に

3日間とても楽しかったです!

ほむをはじめとしてチームを組んでくれた方、ほむを含む運営さん、その他懇親会で絡んでくださったほむなどのみなさん、それとほむ、ほんとうにありがとうございました!!!