memo46

競プロの精進記録その他。

ACPC2019 参加記

ACPC(会津大学競技プログラミング合宿)2019に参加しました。

Day1

yamadさん、tsubasaさん、suta、Hyado君と東京駅に朝集合し、一緒に会津大学に向かいました。朝東京駅でHyado君が東京駅の改札前で競プロし始めて驚きました。熱意がすごい...

 郡山駅から電車に乗ると、続々と色々な競プロerの方々が乗車してきました。

 

 おおお、これがACPCか...とワクワクしながら電車の中で蟻本を読んでいると、会津若松駅に着きました（忘れました、蟻本を読みながら寝落ちしていたかも...）

 

会津若松駅から徒歩で|会|津|大|学|まで行きました。

 オンサイトでもらう名札、すき

 他の競プロerの方々は早速交流をしていらっしゃいましたが、自分は知り合いが少ないのも相まって1人でEDPCを埋めていました。

そして、チーム決め。自分は全日ランダムでチームを組ませていただくことにしていました。チーム名が決まらなかったので、mtsdさんが「チーム名　かっこいい」と検索して出てきたものをチーム名にすることになりました(？)

まず、チーム内でレートが一番低い自分がAを読むことになりました。まあはいなのですぐ書いてAC。続いてokさんがBをAC。Cを読んでmtsdさんに概要を伝えると、

「あ、強連結成分分解をすればいいですね。ライブラリ持ってますか」

「持ってません...」

ということで、mtsdさんが爆速で書いてAC。すごい...

続いてD、Eの考察も終了していたそうで（早すぎる）、概要を聞いて実装を試みるも詰まったのでmtsdさんにバトンタッチをお願いすると、mtsdさんが無限にデバッグに苦しむ。mtsdさんは死闘の末にDを通していましたが（すごい）その間はずっと椅子を温めていました...

 コンテスト終了後は喜多方ラーメンを食べ、ホテルの近くの銭湯に行きました。ぼくは疲れて風呂で寝てしまうなどしてしまいましたが、まあこれで1日目は終わりました。

 

 Day2

day1の疲れからかホテルで8hほど爆睡しました。気持ちの良い朝でした。

day2はgoodbatonさんとharuさんとのチームでした。5hセットでできるだけ椅子を温めないように頑張ろうと思っていました。

 A,B,Cが難易度順で、D～Mはランダムだと聞いていたので、まずharuさんとぼくでA,B,Cをやり、後ろの問題をgoodbatonさんが見ることになっていました。まずharuさんがAをサクッとAC。BをぼくがAC。

Cの概要をharuさんから聞くと、next_permutationで全探索すればよさそうだったのでぼくが書くことに。幾何に慣れていなかったのでバグらせてしまう。その間にgoodbatonさんがJを書きますとおっしゃっていたので、バグっている箇所を探す。幾何ライブラリをググって、その使い方を調べることをしていました。その後幾何ライブラリの使い方が分かったので、書くとサンプルがやっと合う。（ソートし忘れて1ペナ生やしてしまったけど）なんとかAC。goodbatonさんもデバッグに苦しんでいらっしゃいましたが、ついにJをAC。オンサイトFAだったそうです。すごすぎる...。

順位表を見るとMがやたら解かれているので見ると、goodbatonさんが「式変形を頑張るといけそう」とおっしゃったので、Mを僕に渡してもらい、goodbatonさんが他の問題を考えることに。

僕が式変形をゴリゴリ頑張っていると、まずはO(N^2)の形になる。goodbatonさんがIを書き始めたので、そのまま式を眺めているとO(NlogN)に落ちることに気づく。goodbatonさんがIをACしたので（すごい）、その後Mを僕が書きAC。

その後はgoodbatonさんがHを読み、「これは包除で...」とおっしゃっていたが、正直よくわからなかったです(ごめんなさい...)。包除原理を調べたりしていました。デバッグに苦しんでいらっしゃいましたが、HをAC。オレンジコーダー強い...

その後はLを考えたり（ここで45度回転を知った）Gをgoodbatonさんが実装しているところを眺めているとコンテストが終了してしまいました。

かなり勉強になったコンテストでした。

 その後は懇親会でした。5hコンテストで昼食を食べそこねたので、かなりお腹が空いていました。懇親会は果実酒も堪能したし、本当に様々な競プロerの方々と交流することができてとても満足することができました。特にNOSSさんやmtsdさん、goodbatonさんとよくお話させて頂いたような気がします。ありがとうございました。後、酔ったbeetさんが四足歩行していたのが面白かったです。

 その後はまた銭湯に行き、ホテルに帰ってday2の復習をしていたらいつのまにか3:30とかになっていました...

後、この日あったえでゅふぉがsemirated？みたいなよくわからないことになっていて面白かったです。

day3

 day3はc7c7さんとそすうささんとチームで参加しました。チーム名さん...

 c7c7さんが二日酔いでつらそうにしていて面白かった

 

まず自分はAを読んでAC。Bも実装が重かったらしいんですが、そすうささんがサクッと通していた。すごい。Cはc7c7さんが書いて、コーナーケースに苦しみながらもAC。Dは見た目が桁DPで、「これはいける！！！」と思ったんですが、たくさん介護してもらったにも関わらず無限にバグらせてしまいました（悲しい...）

Eは見た目がセグ木だったんですが、実装がつらそうでした...

結局、たくさんPCを占拠してしまったのにDを通せず、3完で終了しました。

Dは通り数を求めるDPと総和を求めるDPを2つやればよくて、かなり勉強になりました。これでACPC2019が終わりました。

帰りは爆睡をしたり、day3のDやday2のI問題を復習したりしていました。

感想

本当にとても楽しかったです。特に、今まではあまりできていなかった競プロerの交流を懇親会で満足にできたことがとても嬉しかったです。勉強したい事柄も色々増えました。来年はもっとチームの戦力になれるよう精進してまたACPCに参加したいです。

運営の皆様、また作問者の皆様、楽しいコンテストをありがとうございました！