KUPC 2020にチーム参加した

Kyoto University Programming Contest 2020 - AtCoder に machy, leign (敬称略) と チーム名 maajign で参加しました

チーム編成

1週間くらい前に、社内の競プロ部channel(最近全然活動できてない)でチーム参加したい! って言ったら集まった

コンテスト中

• Cは配点が明らかにやばいので、最初は A: machy, B: aajisaka, D: leign が読むことにした
• A: AC (4:45)
• Bを実装してAC (9:25)
• 合間にCをチラ見したけどやばそう
• 他を読んでいる間にDがAC (41:38)
• E: machy, G: aajisakaと読んでいる (FよりGのほうが先にACが出ていたため)
• E: AC (60:53 + 1ペナ, 2分探索の上界下界の設定ミス)
• Gを実装するも、サンプルが合わない
• 誤読に気づく (最終的な数列の数だけ求めていた)
• Gよくわからないし、Fはleignが読んでて解けそうになってるのでFを実装してもらう
• F: AC (108:00)
• ときどき考察していたCで解法がようやく思いつく。実装してAC (116:38)
• この時点でG, Mがまぁまぁ通されている状況
• Gはleignと一緒に考察がかなり進み、手厚い介護を受けながら実装してなんとかAC (180:11)
• (leignも途中まで誤読していて、考察の最初の方は話が噛み合わなかった)
• ここで自分はようやくMをちゃんと読むと、カタラン数入れてNTTをlogN回やるだけで O(MlogMlogN) で解けることがわかる
• 実装してサンプルが合ったので投げると TLE (205:42)
• butterflyとbutterfly_inv()を1回だけにして内部でべき乗するとO(M(logM+logN))になるからいけるかなと思ったけど壊れてサンプル合わない
• leignが https://judge.yosupo.jp/submission/7833 を見つけてきて、貼ってコンパイルエラー直すとAC (239:57)
• きっと想定じゃないけどACしたのでOK
• その後は HとJ(部分点) を狙っていたけどわからずにコンテスト終了

結果

8完で20位でした。 前回WUPCにチームで出たときは22位だったので、1ページ目に残れてよかったです

Cについて

提出したやつ

13
anaoapaqarasa
tbubvbwbxbybz
cncocpcqcrcsc
tdudvdwdxdydz
eneoepeqerese
tfufvfwfxfyfz
gngogpgqgrgsg
thuhvhwhxhyhz
inioipiqirisi
tjujvjwjxjyjz
knkokpkqkrksk
tlulvlwlxlylz
mnmompmqmrmsm

n=13 だからアルファベットの前半と後半に分けられて、適当にそれっぽいものをいろいろ作っていると偶然 anaoapaqarasa ができて、これ並べたらできるのでは、ってなった。

まとめ

• ひさびさの5時間コンテストで疲れたけど楽しかった
• 休日だと社会人でもチーム参加できるので助かる
• D,E,Fは一切考察してないのであとで復習します...