ACPC2019 参加記

2019/09/18-2019/09/20に行われたACPC2019に参加してきました。

day1

今年は前泊しませんでした。朝起きて新幹線で郡山まで行きます。そこで数人の競プロerと会いました。

郡山から会津若松まではナンさんとずっと喋っていました。ほかの乗客にかなり迷惑をかけていそう……。

コンテスト

今年は三日ともすでにチームを組んでいました。day1はいづみちはる、mo3tthiさんとacpc_chunithmで出ました。

まずAをmo3tthiさん、Bをいづみちはる、Cを僕が読みます。Aが通るのを待って、CがやるだけなのでBに割り込んで通します。

Bも通ったところで、いづみちはるがDを、mo3tthiさんがGを考えているらしいので、僕はEを考えることにします。

EはたぶんDPで、書けたので投げましたが通りません。笛を見る順番をちゃんと考える必要があることに気づき（それまでは入力された順に処理していた）、3WA出しながらAC。

Dの考察を聞きます。まだ詰め切れていないところがあるそうですが、僕は（いづみちはるとは別アプローチの）DFSしてソートして……みたいなことを考えており、できらぁ！とばかりに書いたら通りました。ええ……。

Gの考察を聞きますが、明らかにヤバそうな場合分けをしています。かといってそれ以外の有効な手段を思いつきもしないので、そのまま任せておいて僕はFを読むことにしました。

mapを使ったらTLEしたので、よくわからないけど早そうなのを書いたら通りました。これどこがボトルネックになっていたのかよくわかっていない。

残りはGで、ヤバい場合分けを書いてもらいます。もはや僕にできることは何もないので、考察に対してウンウン頷く機械のモノマネをします。結局書きあがりませんでした。実装しているのを横から見ているだけで嫌になってしまったのですが、完全にmo3tthiさんにぶん投げてしまって申し訳ない気持ちもあります。

夜

去年と同じくいづみちはるの家に泊まりました。即就寝。

day2

会津の朝が寒すぎる。半袖のTシャツしか持っていなくて凍死していました。

コンテスト

今日はナンさんとてぃーいけさんと組んでACPC_AIZUDAI_DROPOUTで出ます。あわせて読みたい：naan112358.hatenablog.com

ナンさんがA、てぃーいけさんがB、僕がCを読みます。Cを読んでいると突然てぃーいけさんがBについて「こういうのは天才がやったほうがいい」と言い出します。僕はCを詰め切れていないのでスルーし、ナンさんが受け取りました。どんなヤバい問題なのかちょっと心配しましたが、なぜか一瞬で通しています。しかもFAらしい、やはり天才だったか……。

Cは僕の問題パターンマッチングによると90度しか曲がれないはずだったのですが、実際には任意の実数の角度曲がることができるらしいです。atan2を触るのが怖すぎて恐る恐る書いていたらサンプルを合わせるまでかなり時間をかけてしまいましたが、何とか一発AC。

とりあえず全員問題をサラッと読むか、となって読んでいると、MにたくさんACが出ています。僕も読んで式を書きましたが、目がついていないので変数を見間違えていて、二項係数に落とせません。仕方なくナンさんに投げると閉じた式になって返ってきたので、書いてAC。

てぃーいけさんからLの考察を聞きます。絶対値の式を最大化するような点を保持する方法として、符号の付き方8通りを試すのを僕が提案して、良さそうとなります。この間にナンさんがGを通しています。しかもFAらしい、やはり天才だったか……。

Lを書いて提出します。「開けてみたいでしょ～？いきますよ、せ～の！」submit→WA「はぁ～～～！？（大声）」

よく見るとSCCした後のグラフが木になると思い込んでいます。おっ、大丈夫か大丈夫か？気を取り直してAC。FAでした。

ナンさんがIを書いていて、一発ACします。やはり天才だったか……。

Hの包除の式をナンさんからもらって書きます。サンプルが合いません。よく考えると包除するタイミングが違っていそう、直すとAC。

次に解かれているのがEです。ナンさんが考察している横で適当なことを言っていると証明ができたらしい、転倒数を求めるパートだけコードを共有して僕が実装し、AC。

9問解いたこの時点でコンテスト開始してからまだ2時間と5分、2位に2完差をつけての堂々1位です。やったぜ。

当然まだやる気に満ち溢れているので、次の問題を探します。てぃーいけさんは少し前からD問題を考えていて、僕とナンさんはJ問題を考えることにしました。

なんか平方分割したらいけるんじゃないの？となって（これ実は計算量的に全くダメなんですよね）、書きます。

一時間くらいかけてサンプルを合わせましたが、そのあといくらバケットサイズを変えてもTLEになります。途中で解法が全くダメであることに薄々感づきながらも、頑張って書いたので投げたい気持ちに歯止めがきかず、コンテスト終了までに14回提出し、そのほとんどがTLEでした。

てぃーいけさんはD問題がブラスター2つでゴールできることに気づきましたが、そこから進まず、ナンさんとF問題を考えていたそうです。てぃーいけさんのCHTでいろいろやっていたそうですがそちらも実装が重かったらしく、結局3時間椅子を温めるだけになってしまいました。

僕たちが熱心に椅子を温めている間にオンラインのほうでは12完と10完が出ていましたが、オンサイトでは全チーム9完止まりで、ペナ差でオンサイト1位になりました。机の向かいにいたオンサイト2位を煽ります。

夜

懇親会です。テーブルの可動部分を回して料理を取る一般的なテクを使用するタイプの懇親会でした。

我々のテーブルでは料理を取る順番はAtCoderじゃんけんによって決定されました。白熱したじゃんけんだった……（白目）。

9時になると未成年は帰らなければいけない、ということで、ゲーセンに行きました。

いづみちはるの家に帰って即就寝。

day3

今日も寒い。昨日の反省を踏まえてパーカーを貸してもらいました。

コンテスト

今日はday1と同じメンバーのacpc_chunithmです。最初に読む問題の割り振りも同じでした。

Aが通ったところで、Bの実装にかなり時間がかかる予想らしいので、Cを先に書きます。1WAしながら通しました。オンサイトFAらしい。

Bが通るのを待ちつつ、先の問題を読みます。Dが解けてEを考えている最中にBのデバッグで少しパソコンが開くらしいので、ちまちまDを書きます。

BもDもかなり難航しましたが、なんとか両方通ります。Eを考えると、ヤバそうな解法が生えてきます。とりあえず実装してみるとサンプルが合いません。よく考えると真っ赤な嘘であることが分かったので、謝罪しつつ考えなおします。

昨日も平方分割を書いたので、今日も書いてみるか！となって書いたら通りました。後から考えてみると、この時の解法はそのままセグ木に乗る形でした。なんで気づかなかったんだろう……。

Fを考えます。最近開いてないな、と思い立って蟻本を取り出し、適当にSuffixArrayのページを眺めながら考えていると、これが使えることに気づきます。うしさんのライブラリをペタ！ｗしてAC。やったぜ！後から考えるとチェックが甘くて嘘っぽいです。でも通ったしOK。

Gを見ます。mo3tthiさんが考えていたので、その考察を聞きます。全然わからなかったのですが、よく見ると全方位木DPをしろと書いてあったので、その方針で実装を考えます。

手を動かさないと頭が働かなかったので、適当に書きながら考えることにします。が、結局詰め切れませんでした……。

その後

会津大の学食に行きます。PCKぶりっぽい。

仙台に帰っていづみちはると合流します。いづみちはるはその後、僕の家に2日泊っていきました。