Comments碧黴(あおかび)です。立命館大学競技プログラミング合宿(RUPC)2019に参加してきました。2019らしいので参加記を書きます。前日の夜に東京で予定があった(というかRUPCに合わせて立てた)ので東京で前泊することにする。お絵描きして駅に向かおうとしたら学割をとっていなかったことに気づいて泣いたが、家の近くのキャンパスでも発行できることに気づいて事なきを得る。2019九州大学のOBであるKorenariさん(@Korenari_D)と食事に行った。同人関係の話と、業界の諸々の話を聞いたりした。おにくおいしいホテルに着いてからは永遠にゴロゴロしていた気がする。翌日は7:30の新幹線だったのでさっさと寝たかったが、Twitterで流れてきたGeoguessrというゲームにハマってしまったのと、深夜アニメが面白いので、結局2時くらいに寝た。1日目ちゃんと起きれた。爆速で朝の支度を行い、東海道新幹線に飛び乗る。米原に着いてから快速やバスを乗り継ぎ、11:30ちょうどに会場に到着。2019至るところにガヴドロのコマが貼られていた。おやつコーナーに最新刊である7巻のコマも貼ってあって”信用可能”だった。人々やTwitterで知っていて初めて会う人(社会人勢や高校・高専勢など)もいっぱいいた。ぼくはチームメイトを決めていたのでその2人がくるまで適当にABCを解いたりする。2019えびちゃん(@rsk0315_h4x)とseicaちゃん(@seica_at_se)とチームを組んだ。適当にA,B,Cをチーム内で分担する。Bを単純なシミュレーションなのにいきなりバグらせてしまって大変申し訳なかった。Cのオセロ問題でseicaちゃんが詰まっていて、問題を読むと地獄のような全列挙しか浮かばない。Dはインタラクティブっぽくて嫌だったので、Eを読む。LISの和の最大値を出力する問題。ぶたんでLISテーブルを構築するときに、更新前の値を持っておいて後々後ろから可能な最大値をにぶたんで決めていくことを思いつく。seicaちゃんに問題概要を説明すると、セグ木でできるよ~と言われ、そのままseicaちゃんがぶん殴って通す。ぷぇ~その間にえびちゃんがDをビット構築する解法を思いつき、サクッとAC。数あてマジックを思い出した。Cについて地獄実装しか思いつかず、サンプルを見るとどう頑張っても64マス中48マスしか埋められないらしい。ゲーム問題は実際に遊んでみることが大事だとICPCアジアで学んでいたので、1人で適当にやってみると石が配置できない部分が格子状に現れることに気づいた。あとはエスパーをして書いて提出すると通った。FとGをなんとなく考察する。なんもわかんねえなあ~と言っているとseicaちゃんがGはフロー、燃やす埋めるっぽいことを言及する。ググりまくってこれ解けないタイプじゃね?と言っていると二部グラフなので反転できることにseicaちゃんが気づいて書いて通す。結果は6/7完オンサイト5位。他大の人と組むのは初めてだったけど、強い人は強いなあ(トートロジー)と思った。音ゲーマーが懇親会に行かないことにぶったまげていたものの、懇親会に行く。もやし先輩やけんちょんさんと初めて話したり、らてあさんの就活ヤバ情報を聞いたりしていた。らてあさんが「エロいのちょうだ~い」と言って新しく作った名刺を要求してきたのが面白かった。終わったあとゲーセンに行くか迷ったものの、ホテルに荷物を置いたらそのまま布団に刺さってしまった。2日目3時半に起きて破滅する。朝食の時間まで燃やす埋めるの解説を読んだりアズレンをやったりしていた。7時に朝食を食べて二度寝。チームは決まっていたのでのんびり向かった。2日目は5時間セットだったので、少し大会を意識して東北大メンバーと組んだ。2019異常チームが多くてアレだった(強さとか格好とかね)https://twitter.com/prd_xxx/status/1103513082188324864コンテスト(会津セット)問題いつものようにA,B,Cを分担する。Bは愚直シミュレーションで通るやろ!と思ってサンプルを入れたら永遠に終わらなかったので式変形。いうのはこたつがめが得意なのでよしなにしてもらい、言われたとおりに実装する。DはDPのD、Eは問題文がアレだったけどBFSをいじれば行けそうだなあ(まあpriority_queueにブチ込むのでdijkstraなんですが)となり、こたつがめが書く。いたるところから“こたつがめ“と聞こえてきて、そのたびにこたつがめが反応しているのが面白かった。Gはゲームで、Nimっぽいのでとりあえず勝ちor負けの状態を押し付けることを考える。長さ1のキッポーはそれ以上食べることができなくて、全て長さ1の状態で相手に押し付ければ勝ち、ということなので結局(長さ-1)の山を考えて勝ち負けを逆転させたNimを考えればいいことになる。一度にとれる長さに制限があるやつは典型らしく教えてもらったのを書いたら通った。Hだったので両方読む。Fは幾何で、Hはなんか2状態を割り当てて、依存関係があるなあと思っていたら燃やす埋めるだった回。辺の貼り方を逆にしていて出力が全部0になったりしたけど通った。Fはなんもわからんなあ、このままいつものように後半椅子温めマンになってしまうと思っていたら、こたつがめが本質をつぶやく。2019想定解は\(O(N)\)(しゃくとり)だったらしいけど\(O(N^2)\)で通ってしまった。20195時間セットで後半2時間にACが出たのは初だったので、ちょっとは成長したかなあという気持ちになる。結果8/13完オンサイト4位。やったねコンテストが終わったあとTABさんと話していたけど、弊チームは定数倍が軽いらしい。確かにJAGのときもbitset高速化で通したりしていたなあ。懇親会メイドの隣に座った。てんぷらさんとつたじぇーさんがイチャつくのを見ていた気がする。ゲーセンメイツがめちゃくちゃ多かった。あんさんが雛鶴あいちゃんに変身し始めていたり、メイドがDrummaniaをやっていたりして完全に異常空間だった。コスプレイヤー2人と南草津駅まで行き、別れる。終電が20分遅れでアになった。前日にらてあさんとりあんさんにチーム組みませんか?と誘っていたので待機。2019https://twitter.com/AokabiC/status/1103445972703539200前日にりあんさんがかなり酔っ払っていて若干不安だったものの無事到着した。机に雛鶴あいとキスショットを並べ始めた。2019コンテスト(北大セット)問題A~Cを分担。Aは\(O(N^2)\)がダメなので若干キレたものの、setを使って事なきを得る。Bはみんな嫌いなカッコ列。解法を考えたものの、結局らてあさんの原案をりあんさんが詰めてAC。Dは累積和とにぶたんを組み合わせることをらてあさんが言及していたので、解法を詰めてもらう。Eは周期文字列が現れるなあという気持ちになっていると、りあんさんが既視感があると言ってAOJの問題の解法を引っ張ってくる。LCPとセグ木を組み合わせるとできそうとなるが、定数倍が重そうという気持ちになる。2019そういえばこういうのは線形アルゴリズムがあったよなあ、とJAG夏合宿のことを思い出し、すぬけさんのいつものページを読むとKMP法でできるっぽいので書く。折り返すと回文になるのでManacherも引っ張ってきてそれっぽく書く。