立命館大学競技プログラミング合宿2019 参加記

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

立命館大学競技プログラミング合宿2019 参加記

AokabiC
2019年3月9日
No Comments

碧黴(あおかび)です。

立命館大学競技プログラミング合宿(RUPC)2019に参加してきました。

らしいので参加記を書きます。

 

0日目

前日の夜に東京で予定があった(というかRUPCに合わせて立てた)ので東京で前泊することにする。

ギリギリまでお絵描きして駅に向かおうとしたら学割をとっていなかったことに気づいて泣いたが、家の近くのキャンパスでも発行できることに気づいて事なきを得る。

九州大学のOBであるKorenariさん(@Korenari_D)と食事に行った。主に同人関係の話と、業界の諸々の話を聞いたりした。おにくおいしい

ホテルに着いてからは永遠にゴロゴロしていた気がする。翌日は7:30の新幹線だったのでさっさと寝たかったが、Twitterで流れてきたGeoguessrというゲームにハマってしまったのと、深夜アニメが面白いので、結局2時くらいに寝た。

 

1日目

ちゃんと起きれた。爆速で朝の支度を行い、東海道新幹線に飛び乗る。米原に着いてから快速やバスを乗り継ぎ、11:30ちょうどに会場に到着。

至るところにガヴドロのコマが貼られていた。おやつコーナーに最新刊である7巻のコマも貼ってあって”信用可能”だった。

会場には   い   つ   も   の   人々やTwitterで知っていて初めて会う人(社会人勢や高校・高専勢など)もいっぱいいた。

ぼくはチームメイトを決めていたのでその2人がくるまで適当にABCを解いたりする。

えびちゃん(@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時間セットだったので、少し大会を意識して東北大メンバーと組んだ。

異常チームが多くてアレだった(強さとか格好とかね)

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を考えればいいことになる。一度にとれる長さに制限があるやつは典型らしく教えてもらったのを書いたら通った。

DとEも通り、その時点で人類が通しているのがF, Hだったので両方読む。Fは幾何で、Hはなんか2状態を割り当てて、依存関係があるなあと思っていたら燃やす埋めるだった回。辺の貼り方を逆にしていて出力が全部0になったりしたけど通った。

Fはなんもわからんなあ、このままいつものように後半椅子温めマンになってしまうと思っていたら、こたつがめが本質をつぶやく。

想定解は\(O(N)\)(しゃくとり)だったらしいけど\(O(N^2)\)で通ってしまった。

5時間セットで後半2時間にACが出たのは初だったので、ちょっとは成長したかなあという気持ちになる。

結果8/13完オンサイト4位。やったね

コンテストが終わったあとTABさんと話していたけど、弊チームは定数倍が軽いらしい。確かにJAGのときもbitset高速化で通したりしていたなあ。

懇親会

メイドの隣に座った。てんぷらさんとつたじぇーさんがイチャつくのを見ていた気がする。

ゲーセンメイツがめちゃくちゃ多かった。りあんさんが雛鶴あいちゃんに変身し始めていたり、メイドがDrummaniaをやっていたりして完全に異常空間だった。

コスプレイヤー2人と南草津駅まで行き、別れる。終電が20分遅れでアになった。

 

3日目

集合時間が早すぎる。

前日にらてあさんとりあんさんにチーム組みませんか？と誘っていたので待機。

https://twitter.com/AokabiC/status/1103445972703539200

前日にりあんさんがかなり酔っ払っていて若干不安だったものの無事到着した。おもむろに机に雛鶴あいとキスショットを並べ始めた。

 

コンテスト(北大セット)

問題

A~Cを分担。Aは\(O(N^2)\)がダメなので若干キレたものの、setを使って事なきを得る。Cも通る。

Bはみんな嫌いなカッコ列。いろいろ解法を考えたものの、結局らてあさんの原案をりあんさんが詰めてAC。

Dは累積和とにぶたんを組み合わせることをらてあさんが言及していたので、解法を詰めてもらう。Eは周期文字列が現れるなあという気持ちになっていると、りあんさんが既視感があると言ってAOJの問題の解法を引っ張ってくる。LCPとセグ木を組み合わせるとできそうとなるが、定数倍が重そうという気持ちになる。

そういえばこういうのは線形アルゴリズムがあったよなあ、とJAG夏合宿のことを思い出し、すぬけさんのいつものページを読むとKMP法でできるっぽいので書く。折り返すと回文になるのでManacherも引っ張ってきてそれっぽく書く。WA。なんで。Dもバグっていてつらそう。

結局どちらもりあんさんの驚異的な介護力によってACまでこぎつける。

結果は5/7完オンサイト12位。すぐ後ろのbeetさんのチームが全完していてすごかった。

解散後

にぼに行った。

うまいラーメンはうまい

その後レジャ大津まで行って音ゲーとがボムガキボンバーガールをやったりして名古屋から夜行バスで帰った。

 

まとめっぽいもの

JAG合宿より緩い感じでとても楽しかった。特に他大の強い人と一緒に考察すると、「自分もこうなりたい」という気持ちになって無限に精進欲が湧いてきた。

またオンサイトで会おうな。

 

 

 

 

 

 

 

 

 

 

 

おまけの衝撃情報

実は帰りの電車で寝ていて清掃員に叩き起こされて飛び降りた結果、電車内にPC入れたカバンを置き去りにしてしまった

着払いで届けてくれるってよ

 

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です