ICPC 2019 模擬国内予選 参加記

JAG の模擬国内予選に参加しました. four-t 全員で出る模擬国内は実は初めて.

コンテスト中の様子

つたさん, えびさん, 僕の順で A, B, C を読む.

A はつたさんがすぐ書いて通し, B はややつらそう？だったけどえびさんが通す.

C を読みながらシミュレーションやるだけか〜？とか思ってると制約に 10⁹ とか書いてあって無理じゃーんってなる. しょうがないので実験を手でやる. パソコンが空くタイミングがあったので実験のコードを書いたらバグる.

えびさんに手伝ってもらったりしながら考察を進めるといけそうな感じになったのでえびさんに書いてもらって AC.

K は多角形のケイっていう問題があるとえびさんから聞いていたので K 問題やるか〜と思うが、問題が H までしかない.

よく見ると G 問題がその問題だと気づくので, G を読む. 構文解析の F がつらいらしく, えびさんと G の考察をする.

凸包を最初にとって, 内部の点を一つづつ追加していくと良さそうな気持ちになる. priority_queue を使って周長が短いのだけ残して BFS をすると良さそう.

パソコンが空いてるので書く.

写経したりして書き終わるも, サンプルが合わない.

周長の短い K 個だけを保存してたけど, とりあえずちょっと多めにもつようにするととりあえずサンプルには合うようになる.

時間もないので出すが WA.

よく見ると priority_queue に要らないものだけ残って, 必要なものを捨てるようになってるのに気づいて直すが間に合わず, コンテスト終了.

反省

• 実験のコードをバグらせない. 計算量悪くても良いからバグらせず, 短い時間で書けるような方針を選ぶべき.

• 幾何があるからといってそればっかりやるのはあんまりよくない. 他の問題も内容くらいは把握した方が良さそう.

• C みたいなやつ実はえびさんに投げたほうが早い？

• タイピングが苦手. 写経で無限に typo する.

終わりに

本番はもっと良い順位をとりたい.

終わった後少し直したら G が多分できた.