RUPC2019 参加記 Day 0 - 3

たのしかった

Day 0

寝ようと思ったら気がついたら起きていた こたつがめが滋賀に来た

↑これは名古屋だね

Day 1

歯医者に行く 敗北者…? 取り消せよ…! 最後に全力でフロスされて歯ァガタガタ言わされてしまった

到着してしまう こたつとエンカ!w

自己紹介フェーズでいづみちはるさんがこたつを名乗っていてウケた beetさんが「AtCoderのレーティングがたぶん会場で1位です」みたいなことを言っていて怖くなってしまう それ以外は忘れてしまった 悲しい

randomに組むか〜wと思っていたらなんとくじでbeetさんと当たる かてません

drogskolさん beetさんと組んでチーム名をrupc_ukuku09にする うっくっくwwwwwwえいえいえt(←いずらいt)

drogskolさんがABCを、beetさんと自分でDEFGを担当しようということになる

ここからコンテスト

Dを読むと構築なので担当したい気持ちになる

drogskolさんがABを通してくれている間にDとか構築インタラクティブやしにぶたんやろ〜とヘラヘラしながらbeetさんに無を持っていくと無であることを指摘される

無を有にするうちにAとBが通っているので有を実装すると通る ここまで32分くらい

drogskolさんが実験をして天才になってCを通していた beetさんが一瞬でEを通していた こわいなあ(50分)

その間にFとGを読んでGは苦手だなあ やめるか!wという気持ちになってFを考えておく 絶対値なので大小関係を考えるをすると大小関係の変動しない交換は意味がないことがわかる

beetさんにGが「燃やす埋める」っぽいと言われるが燃やす埋めるを解いたことがなく フローで解けるらしい くらいの理解しかなかったため相槌を打つオタクと化してしまう

同色罰金がうくだけど二部グラフなので頂点反転!wをしてもうまくいかない 終わってから聞いたんですが電球を頂点にすると破滅するらしい 悲しいね

悲しいのでFを考察する わからんわからんと言いながらa[i],i,a[j],jの大小関係実質12通りを書き下すと、a[i]とiの間 と a[j]とjの間 が重なっていないものはswapするべきで 得られるスコアは2つの区間の距離の2倍っぽいことがわかる

貪欲以外のアプローチが思いつかなかったので証明のない貪欲を書く monoidであることをbeetさんが気づくのでbeetさんのセグメント木ライブラリに乗せて殴る→サンプルは合うのにWA

適当に自明assertを入れることを提案するとREする えらかった がんばって直すと通る 159分

残り時間はGがわからず いやー燃やす埋めるに見えるけど 実はDPか?とか言っているとコンテストが終了していた

コンテストここまで

オンサイト1位と2位は組んでたチームだから実質1位!ガハハw まあ3位なんですが

D問題なかなか自分の実装がよさそうだったのでイキる やめようね! ビットごとにめっちゃ辺を張る実装もすこなんや

懇親会で渾身の懇親をする 実はほとんど知っていた人としか話してないね コミュ障なので

olpheくんとか自分とか「どうやったら競プロうまくなれますか」
beetさん「4000問解くと、実力が上がるので安定して、レートがこんなふうになることがなくなります(手を大きく上下させる)」
うしさん「?(机に寝ていた状態から起き上がる)」

↑これすき

懇親会後ゲーセン勢に合流してmaimaiをする いづみちはるさん音ゲーが上手すぎないか 帰ろうとしたら終電ギリギリアウトでこわれてしまった Day 1終了

終電に温情で乗せてもらったので勝ち

Day 2

へのkと不明瞭にいちゃつく けんちょん olphe ナン でrupc_olnanchonとしてチームを組んでおいた

わたてん9話を見た ノアちゃんがガチめいてきた 星野みやこに変身セットあたりで目覚めましたねクォレハ… まあひなたちゃん優しいからね、仕方ないね

問題数13問でおっぱげた

olpheくんがA ナンがB けんちょんさんがCをまず読んで残りはよしなにすることになる

ここからコンテスト

olpheくんがAを爆速で通す 1分

Bがシミュレーションに見えたのでシミュレーションを書いてしまう Sample 4を手元で実行して禿げる 算数をしないといけない気持ちになりけんちょんさんのCの実装を優先してもらう けんちょんさんがCを通す 14分

算数をしようと思ったところ算数が苦手だったので泣いてしまった 諦めて別の問題をすることを決意

けんちょんさんがGを考えていて逆型ゲームに誤読しているっぽかった(最後の1本を食べきった人の負け に見えていそうだった)ので誤読を指摘する Gが通る 27分

(ほとんど関わっていなかったけどFの考察がこのへんで進んでいたらしい)

ここからが本当の地獄!

olpheくんを尻目に面白そうなL問題を考える すぐに原始根→離散対数→gcd (575)では?と言う 実装をしてもらって投げるとTLEしてしまう だめであることに気づくのに無限時間かかってしまった

Bをolpheくんが通す プロ 堅実 114分

けんちょんさんがHを通す 昨日見た燃やす埋めるらしい なるほどなあ ところで問題を読んでいません

並行してolpheと二人でIを考える 考えていると天から「逆順に見なさい」という声が聞こえるので逆順に見るといいなあとなる

2q d + A (0 <= A < 2q)の形が適当に作れるので上端と下端を生やすと判定がすぐにできる

満たすAについて適当をするとサンプルが合う WAが出るんですが自明assertをするとREでおっぱげる オーバーフローなどを直すと通る 197分

Dが冷静になるとただのDPなので書く デバッグ出力こわれるから高さを小さくしていたらWAになって踊った AC 225分

Eをみんなで考える olpheが思いついた感じだったので書く 実はほとんど寝ていたのでJとLを考えるマンになってしまう

Jが区間スケジューリングっぽいというのは最初の方にolpheから聞いていたので物理パートの方針ガチャをするとn回目でいい感じになる 受験物理の経験が生きたな(確信) 放物線はy=ax(T-x)なのでここのaを出す v=(vx, vy)として出した式と比較してvをaで表す 最小は1/Tっぽい 45°だなあ 最高

Eが通ったのでけんちょんさんがLをほげしていくのと並行してJを実装する 手が止まったらもう片方が奪う感じで目まぐるしく実装する人が入れ替わっていた

Jの実装が完了するがSampleが合わねえ おわり とりあえず投げる 当然WAなんですが

コンテストここまで

おもむろにJのソートを逆順にすると通ってキレる

オンサイト7位 悪くはないんですが主観的冷えというものがあり Lも通したかったなあ 負けです

懇親会で渾身の食事をする 複数のよっぱらいが存在していて面白くなった これが†人生†や

懇親会の卓で500点以下の問題を作問して投げる遊びをする 自分も1問いい感じの300-400が生やせたのでヨシ beetさんが作問能力も高いことがわかりかてませんの意を強くした

懇親会後ゲーセンでmaimaiをする こたつがめとマッチング!w

帰ろうとしたら終電1本前でこわれてしまった Day 2終了

Day 3

こたつへのナンでチームを組むことにしていた

2人して絶起をする

3人して遅刻をする

会場へ向かう途中にbeetさんのツイートを見る

包除数え上げが出るのか〜(うく)

こたつが最遅だったのでチーム名をRUPC_Burningkotatsuにした こたつがめもやした

へのがA ナンがB こたつがCを読むことに

ここからコンテスト

へのkがAを通す rupc_H_E_N_T_A_Iに僅差で負けたらしい 悲しいね

自分がわからなくてこたつがCの方針が立ったらしいので実装してもらう

へのkにBの問題概要を伝えていたらこたつが読んでいたのがBであったことが発覚 何? まあBが一瞬で方針が立つのはこたつの異常能力な気がするのでそれが起きてよかった へのと一緒にCを読むとSampleがすべてを教えてくれるのでわかる どちらも通る 15分

Dをへのkが実装する そのうちにEFGを読もうとするがEは苦手なタイプの文字列なので無理だねとなる Fを読むと受験数学の勘がまず個数を固定しなさいと言ってくるので個数を固定する すると自明な包除の式が立つ(ここで脳内でbeetさんの方角を向いて礼拝した)ので綺麗にしたいなあとなってこたつに見せる するとこたつのおかげで冷静になってこのまま計算してもたかだかO(N2)じゃーんとなって終わる ホワイトボードを見るとhomu_aishiteruなる文字列がFの下に書かれていて泣いてしまった いや20分ってなんやねん

Dが通ったのでFを実装すると当然通る やったぜ。 39分→46分

その間にへのとこたつがEの考察を詰めていた Manacharとか使ったんじゃないかなあ しらんけど 線形とか回文とか言っていたけど結局ロリハで殴ったらしい なるほどなあ 待っていると通る 67分!!!!

悠々とGを考察し始めると思いつかなくて禿げる

いろいろなことを考える cycleの種類は上から見て1周するか1周しないかだなあとなる 1つ繋げるみたいなことを考え始める

Gに到達して30分ほどで27状態くらいを持つDPを思いつくが破滅なのでやめたくなる しかし重い腰をあげて実装に取りかかる(この頃には上下しながら1周するcycleの存在が頭から消えてしまっている)

地獄だなあと思いながら書く へのkとナンの2人で独立に書く←これはなに 二人ともSample 1は通るけど2が合わないね

へのkが上下しながら1周するcycleの存在を思い出して実装する 自分は忘れたまま悲しくなっていた

コンテストここまで

つらすぎて朝青龍になる まあオンサイト2位だし多少はね?

地獄DPを実装しきることができるタイプのベテランになりたいね 素直に反省です いや地獄DPが本質じゃなくて考察が抜けていたんですが

解説ののち解散になった

ボウリングまではついていくことに決めた

funcsr もやし先輩 くちもちとくらさん きゅうりさん Pulmnさんで昼食を食べに行く バスで駅まで行くが来た道を戻る

ちょうど15時くらいで飲食店が次々と閉まる 残った選択肢がすいていそうな得々うどんか混んでいるにぼ次郎でにぼ次郎を選んだ

にぼ三郎を頼んで完飲をした おいしかった オタク必ずしも完飲をしないことを学んだ

ボウリングに行った 申し込み用紙に「ナン」と書いたら名前を「ナニ」と間違えられて泣いた

きゅうりさんとくちもちとくらさんがお上手 funcsrとナンが無だった かなしいね

ボウリングから帰って参加記を書く ブログがなかったのではてなブログに登録する

とりあえず記事内で言及している人に読んでもらってから公開するお気持ちになる Day 3 終了

感想

楽しかった 問題が良質だった Day 2, 3の"あと一問"が解きたかった...(いやDay 2はほんまお前お前)

来年も申し込みTLEしない限り行こうと思います 他の大学オンサイトとかも行ければ行く いやよく考えたら遠いな 破滅してしまった

おまけ

去年の参加記書いてないね 長いイベントだなあ(詠嘆)