Heno World practice - てんぷらのぷらはC++のぷら

久しぶりに5時間コンテストをやったので。

2018-2019 Hanoi Regional をやりました。https://hanoi18.kattis.com/standings

コンテストの流れ

やむなくが前から、てんぷらが後ろから読む。へのくんはテンプレとかを書き次第真ん中くらいから

C AC(12:24)

へのくんがテンプレ書いたあとそのまま書いてた

H AC(20:38)

後ろのほうを読みながら順位表眺めてたらちょっと解かれてたので読んだら解けた

D WA, WA, AC(72:20)

Iが包除原理をしてくださいと問題文に書いてあるがよくわからないのでへのくんにぶん投げる(まじでごめん)。へのくんが実装を始めるも辛そう。やむなくとDのインタラクティブを考えると普通に中間値の定理からできるね、となる。適当に書いて出すとWA。オーバーフローっぽい何かに気づいて出しなおしたけどWA。冷静になってクエリ数を数えると1回オーバーしてました(完)。最後の処理を丁寧にしてAC。この辺の戦犯度合いやばいね

I TLE, WA, AC(97:41)

結局へのくんが解いてくれました。bitDP的な感じなんですけど最初のは計算量がやばくてTLEしたのでちゃんと必要なところだけ残すようにしたらWA。原因はintのオーバーフローでした(完)。なおしてAC。ここまでがかなり辛かった。

B TLE, AC(116:01)

僕とへのくんがI詰めたりしてる間にやむなくが実験しまくってGrundy数がこれな気がしますって見せてきたので、2人で証明を試みるとできる。気づいてしまうと実装はないので適当に書く。適当に書きすぎて二分累乗でk/=2を忘れてTLEを出す。は？競技プログラミングをやめろ。なおしてAC。5完時点で全体最速ではあったがペナルティがinfで厳しいねという気持ち。

L WA, AC(147:44)

Iの実装を終えたへのくんがLの考察をしてなんかいい感じらしいのでちょっと相談して考察を詰めて書いてもらう。わりとすぐ書けててすごかった。配列外参照で1WA出したのでめちゃくちゃはすごくなかった。

J AC(156:40)

Lをへのくんに書いてもらってる間にやむなくと相談する。完全グラフと輪っか以外にないだろとか言ってたら完全2部グラフでもできることにやむなくが気づく。色々書いてみるが他はダメそう。証明もできたつもりになったのでLが通ってすぐやむなくが書いてAC。

A 4WA, AC(259:56)

最小費用流でいいことは分かっていたがライブラリの写経とかが面倒で後回しになっていたのをへのくんに書いてもらう。書き終わって、手作りしたテストケースもちゃんと通ったが投げてみるとダメ。細かい修正をいろいろするも全然合わなくてだいぶ経ってからフローの復元がバグってたことに気づく。僕が書き直してなんとかAC。Aをバグらせてる間に他のチーム(本番のオンサイト優勝チーム)に先に8完されて焦ってたけど結局ペナ差で逆転して1位になる。まぁ本番ではネットワークがぶっ壊れてた時間があったらしいのであまりあてにならない。

G 3WA, AC(295:47)

Aの実装待ちの間に、辺数が多いほうは完全グラフでできて(こっちは証明もできた)、辺数が少ないほうはトリボナッチでどうにかなりそうな気がしていたので書いてみる。だいたいあってそうなので出してみるとWA。後者の辺の数が全然おさまってないことに気づく。フィボナッチじゃ頂点数足りないよなぁ→足りるやんけ！となって急いで書き直して提出してAC。4分前AC、心臓に良くない。

結局単独9完の1位でした。やったね。

反省

・全体的にペナルティが多すぎる

・てんぷらIできないの何？

・フローの復元の実装がやばそうなのにもう少し早く気づくべきだった。

・9完はえらいのでRegional本番もこれをやろうね