足跡-sokuseki-

りかの日進月歩の記録

RUPC2018参加記

3/26-28に立命館大学で行われたRUPC2018に参加したので参加記を書きます。

 

day ?

ATND(https://atnd.org/events/94033 )を公開したら尋常じゃないスピードで埋まったので怖かった。(例年の参加者は40人くらいなのに公開3日で60人に到達するというバグが発生、原因不明)

 

day1 立命館大学セット

 

はじめの自己紹介フェーズではTwitterでよく聞く名前の人がたくさんいて楽しかった。

とくに名前を言っただけで笑われてる人とかなりきりして自己紹介してる人とかいて面白かった。

 

コンテストはジャッジ側だったので、とくに何もしてなかった。clar来ないかなーと思ってAOJを眺めてた。

今年は風船配りがなかったのでゆっくりお菓子食べたり全完したチームの人とおはなししたりしてた。

3時間セットなのに40分で全完しててすごいなーと思った。

B問題はね、ぼくも何書いてるかよくわからないね、あれなに。(数学苦手並感)

 

懇親会は学内で立食形式だったので、うしうくびーとらてまるたとかと一緒にいた。

目の前でふぁぼ爆するの面白いね。

 

懇親会終わるの思ってたより早かったし草津のゲーセンに行ってマッチングをしました。

day2 会津大学セット

 

ご注文はうさぎですか?っていう素晴らしい作品があって、その主人公の香風智乃ちゃんっていう子がかわいいです。たくさん写真をとりました。

なんかうさ耳とティッピーのぬいぐるみが好評だった。

 

 

らてあさんとTABさんと事前にチームを組んでいたのでガチャ要素なし。

 

らてあさんがA担当、ぼくがB担当、TABさんがC担当して、終わったらみんなでDやるかーって言ってて、順当にABCを通す。

Dを読んで全然解法が浮かばないし他のも読むかーってなってHくらいまで分担して読む。

Fが一番できそうで、「あみだくじを1つ以上選ぶ」っていうのを見落としていることに気づいた後、3要素の置換だからあみだくじの種類は高々6種類で、それぞれは高々3つを使えば元に戻るってわかったので、あみだくじの種類を数えてあとは場合分けすれば解けるとわかる。らてあさんに実装をたのんで、TABさんと他の問題をみてた。

TABさんがHが解けそうと言っていたので方針を聞く。長さがL以下の数がSにいくつ含まれているかをO(N)で計算できればにぶたんしてできそうみたいな感じだったのでFが終わったら実装してもらうことにする。

Eがなんかグラフっぽいけどコストとかどうするんだってなって詰む。

らてあさんがFの場合分けつらそうだったのでTABさんと一緒にみてた。

Fが通った後、TABさんにHを任せて、らてあさんとGの考察をしてた。いろいろ考えた結果、2つの操作のうち前者をできるだけしてから、後者をいい感じに選んでやるのがいいとわかる。2つの組み合わせを重複無しに作っていくから2部グラフのマッチングみたいになりませんか?って言ってたけどこれ二部グラフとは限らなくない?ってなったので一般マッチングどうするの…ってずっと言ってた。

Iは幾何だしやりたくないねー(´・ェ・`)って言ってた。なんかN個の頂点をM個に分けて、その最小半径を求めて、その最大値の最小値を出せばよくね?ってなったけどこれ計算量間に合うのかなあって言ってた。

 そのままコンテストが終わってABCFの4完でした。

 

始まる前にコンテスト中にどれだけ長くティッピーを頭に乗せていることができるか勝負しようとか言っていた気がする。誰と勝負するつもりだったんだろう。実際はティッピーは観賞用でした。

 

懇親会は南草津駅近くの焼肉で、席が自由だったのでまたうしうくらてまるたと一緒にいました。どうすれば強くなれるかみたいな話をらてさんがしていてためになるな〜と思ってた。ぼくはキャベツを食べていました。

 

懇親会が終わった後は膳所のゲーセンに行ってマッチングをしました。紫レになりました。やったね。

 

day3 北海道大学セット

 

3日目はうしさんとチームを組む約束をしていたんですが、うしさんが2日目に遅刻してて、怖いなあと思ったのでモーニングコールをしました。電話するって事前に言ってたのにビビっててウケる。

お菓子と飲み物が尽きそうだったので学内コンビニに買いに行きました。結局それでも飲み物が足りなかったけど。

 

 うしさんとolpheさんと事前にチームを組んでいたのでガチャ要素なし。

 うしさんはAのFA担当、ぼくがB担当、olpheさんがC担当であとは適当に、っていう戦略だった。

コンテストが開始して、AをFAしてBCも通って、Eはなんかうしさんがライブラリ貼るだけって言ってて通してた。Dはグラフみたいに考えればできるってolpheさんが言ってて通してた。

あとFとGで、Fは最短路に使われる辺のうちいい感じのやつをコスト+1ずつしてあげるとよくて、それってフローに帰着できるみたいなことをolpheさんがいっててすごいなーってなった。

olpheさんがFを実装してる間、うしさんとGを考える。Gはうしさんがこれ蟻本にあるやつと全く同じじゃんって言ってて、制約が大きいのと、Pの文字列に含まれる文字とは違う文字に変換するってところが違うってことがわかる。Pに含まれる文字と違うってことは文字を変えた後に別のPと一致するというのがありえないから貪欲でできそうってうしさんに伝えたら、なんかいい感じに実装してくれた。文字列マッチング?とかよくわからないけどチーム戦なのでまあ。

Fがバグっててつらそうだったのでうしさんが先にGをとおして、みんなでFデバッグした。全完。いえい!w

 

解説が終わって、解散して、運営だったので会場の片付けをして、ゲーセン勢と合流して京都に行った。楽しかったです。

 

まとめ

 

チームガチャはできなかったけどチーム戦は楽しめたのでよかった。

知ってる人と交流するのが多かったので、知らない人にも勇気を出して話しかけような(なおコミュ障

あとうしさんのうさ耳がとてもかわいかったので次のACPCにもうさ耳を持って行こうと思いましたまる