RUPC2017
行きました
一日目(朝)
朝寝坊して電車一本逃す(Ω＼ζ°)ﾁｰﾝ
新幹線ブーストしたら間に合った(やったー)
会場に着いたが明らかに話せる人がいなくて冷える
チームメイトガチャでちゃっくさん、葦さんを引いた。
コミュ障なので自己紹介もできず、コンテストが始まる
一日目(コンテスト)
とりあえず問題を読む。ABを二人に投げて、とりあえず後ろの二問以外(C～I)を読んだ。最初の印象は、
C:はい
D:ヤバ
E:ヤバ
F:やるだけ(嘘考察)
G:面倒
H:面倒
I:やるだけ(嘘考察)
という感じで、あーこれは結構ヤバいなあという感じだった。
チームメイトがABをやってる間にDを考える。こういうのはどうせk文字(kは小さい数)くらいまで考えればいいんだけど、それでもkが10くらい必要に見えて、死ぬ。落ち着いて制約を見て考えると、ふつうにk=4でokだとわかったので終わり
とりあえずCを投げて、他を考える。Eはマンハッタン距離のままじゃ明らかにヤバいので、どうにかして消せないかなあと考えたらまあはいとなった。Eも投げる。
チームメイトの実装とデバッグを眺める。実はあまりチーム戦をしたことがなかったのでこの時間はかなり楽しかった。CE両方通ったので終わり。
Fを「やるだけだから」といって投げる。「わかんないんですけど・・・」と言われて一緒に考えると、僕も「わかんないんですけど・・・」となった。
素晴らしいチームワーク。
嘘解法を発明→チームメイトに説明→話してるうちに嘘だと分かる みたいなことが何回かあって、まあ会話するのは自分の考察の整理にもいいのかなあと思った(個人戦だと「話してるうちに嘘だと分かる」が「実装してるうちに嘘だと分かる」になって爆発するので)
結局Fが分かったので通す。長年培ってきたdijkstra力で瞬殺する
順位表みたら結構この時点で解きまくってる人がいて怖いなあとなる。でもあまりHJが解かれていないっぽい？(Kは結構解かれているみたいだったので簡単なのかな？となった)
この後一応JKにも目を通して、J:ヤバい K:流すだけ となった。さすがにこのKがフローじゃなかったら解くの諦めるレベルだなあという気持ちだったので、まあ最小費用流でしょという感じ
とりあえずコンテスト開始直後からやるだけだと主張していたIを書き始める。まあ終了時にいる頂点を決め打ちするみたいなノリはあってて、到達判定を書いたところでスコアの計算ができないことに気付く。あーヤバいなあと言いながら(チームメイトに悟られないように)涼しい顔で考えていると、まあUF持って逆からやればいいねとなる。終わり。これみんな簡単だったと言ってた気がするけど個人的には難しかったし良問だった
Kを流します。たのしー！
Gはさすがにまあ面倒なだけなのでやる。結構楽に書けてよかった。
問題の量が無限にあるような気持ちになっていて、この時点であと2問しかなくてアレ？？となった
あと一時間しかなかったのでまあHを頑張ったら終わりかなあと思った
Hの想定解はダブリング+二分探索で、まあ言われてみたらそれはそうとなった。
そんなものは思いつかないので、なもりグラフの木の部分と輪の部分を別に考えて、木で衝突するケースはマージテク、輪で衝突するケースは二分探索でやった。実装量が爆発したけど一発で通ってうれしー！
Jだけ残ったんですがこの時点で20分しか残ってなくて、解法も思いつかない。コンテストはここで終わりです。ありがとうございました。
ここでセグ木を使う嘘解法を発明したので、「あっこれ行けるかも！ｗ」(!wはフィクション)と言って書き始める。
テンションが上がってセグ木を書いたあたりで嘘に気付いて泣く。
ここでセグ木を使う嘘じゃない解法を思いついて、先ほどのセグ木が生きる。勝ち。全完
残りの5分で自己紹介をしました。怖い大学の人だったっぽくてヒエッ＞＜という感じ
一日目(コンテスト後)
ウクニキアさんを見つけます。コミュ力あってびっくりした(失礼)
twitterでしか知らなかった人が結構いて楽しかった(でもコミュ障なのであまり話せない)
家に帰って寝る。なかなか眠れないのでatcoderで問題探して考察をしていた。→朝5時になってた、atcoder許さん。
2日目(朝)
らてさんいない気がするんですけど…
— ウクーニャ@マスコット (@ukuku09) 2017年3月23日
寝坊した(完)。楽しい合宿でした。皆さんありがとうございました！！
卒業式のため2日目に参加できなかったbtkさんとチームを組むことになる(やったぜ)
ホテルと卒業式から参加する謎のチームになった。
急いで近くのコンビニにお菓子と水を買いに行く。
2日目(コンテスト)
Gを開きます。→不可能
Hを開きます。→い つ も の(AC)
なんかbtkさんから続々と解法が送られてくる。
卒業式中のチームメイトから次々に解法が送られてくるのウケるんだよな
— てりらし (@MochaLatvia) 2017年3月23日
Aが分からない。Bはやるだけ、Cは面倒。Bを処理する。
Dを書くが、WA。するとslackで落ちるケースが送られてきた。最高か(というか僕に頭がなかった)。
そのあとFとCを頑張って処理。Aはbtkさんに投げる。
Eは平均最小化だね、終わり。「KがSCCして二部グラフ判定してDFSするといけそう」と言われて、そんな面倒なわけないやろ！ｗとなりKを読む。
そうでした。これハマると虚無が生まれてコンテスト終わるやつだなあとなる。絶対にバグらせないという強い意志をもって30分くらい実装したら一発で通って感動した。
明らかに自分の得意分野に見えるIが解けなくて悲しくなるが、まあbtkさんに投げる。こっちはLを考えていて、まあお互いWAが出て不穏な感じだった。
→2人とも通ってうれしい
一応Mを読んだりするが、何もアイデアが出てこない。Jはどうせヤバいフローだろうなあとなっていて、Gも解けないなあという感じだった。
Jは最小流量制約のある最大流をすればよさそうとなる。蟻本見ても理解できないのでまあ無理かなあとなった。でも最小費用流にしたら頭使わなくてもできるじゃんとなり書いてみる→通る。やったぜ
完
Gはちょっと思いつきませんね。本番中は集合をマージしながらヒープ持って気合でやるみたいなことしか考えてなかった。
Mは、まあ二部グラフに気付かないとそもそも無理だなあという感じ。でも二部グラフだと気付くためには「二部グラフかな？」と疑問に思う必要があって(それはそう) ちょっと厳しいなあと思った。自然な考察の流れは、「最大安定集合求めたいんやけど・・・」→「二部グラフかな？」という感じかなあ。
まあ結局辞書順最小にするところでフロー力(二部マッチング力?)が問われるのでどちらにしても解けないですね。
こういうやつの練習が足りてない感じがあるので頑張りたい
二日目(コンテスト後)
コンテスト終わった後に急いで会場に行ったら懇親会参加できた
RCOの金で飯を食べる。
nvipさんがいた。こわい(失礼)
酒が入って不思議なテンションになった人たちの横で小さくなっていた。
三日目(朝)
public_latteをやろうということになる。
public_latteに名前負けしない人を探す→胡 桃 沢 ウ ク ニ キ ア マ ク ド ウ ェ ル
public_latte_mcdwlで出る(大悪魔の名前を削る悪魔的行為)
三日目(コンテスト)
E→実 家 のよ う な 安 心 感
ウクさんにABを投げて、さてさんがCDをやっていた。
僕はとりあえずFを読んだが、まあ木の同型判定するだけだなあとなる
→根が指定されてないやん！ｗ困った
頂点の番号付けによらないというか、不変量(?)みたいなものを探すと、まあ直径の真ん中でいいやとなる。
さてさんがCDをエイッとやって通した。Aも通る。ウクさんがBでハマっていてつらそうだった。
Fでロリハを使った同型判定を書く→RE
あーこれスタックオーバーフローしてるんちゃう？ｗとなる。再帰をすべてスタックで書き直すとREが取れてWAになった。
ハッシュ値の衝突を疑ったので基数とmodの値をいっぱい用意する→WA
落ち着いて考えるとハッシュ値の取り方がヤバいので直すと通った。
Bも通ってあとはGだけとなった。明らかに解ける問題に見えない。
→さてさんが通した。ウケる、天才か？？
全完
三日目(コンテスト後)
G嘘解法やん！ｗ(運命)
まあ通れば勝ちなのでね、(?)
さてさん、btkさんとラーメン屋に行く。斬新な味がした。
そのあとみんプロのために東京に行った。親戚となかなか会えなくて結局深夜三時に親戚宅についた。
おわり
