ACM-ICPC 2018 Asia Yokohama Regional 参加期

チーム catsatmat で参加して ABCDGK の6完12位でした。アジア地区予選には2016年も参加していて11位だったので、今回の結果は残念なものでした。感想文だけ送るのが面倒なので簡単な参加記も残しておくことにしました。参加記を書き書き。

まず、チームは catupper と satashun と shiatsumat で構成されていて、まあ3人とも橙のどこかみたいな実力してると思います。

  • コンテスト前

shiatsumat が来なくて焦った。maroonとcatupperがスマブラをしていて草。US配列に前日必死で慣れた。

  • コンテスト

catupperがemacs、satashunとshiatsumatがgeditを使う予定だったのでとりあえずAをcatupperに任せてあとの2人は後ろを読む。

読んでないけど実装が怠いみたいなことを言っていた気がするがA AC(0:14)。

satashunはBを、shiatsumatはCを読んでいたがまだどちらも解けていなかった。

shiatsumatがCはsatashunの方が得意そうというので見たら、マンハッタン距離で個数をカウントして、小さい方から繰り上がらせていけばいいのではということになった。配列サイズが半分しかなくて1WAののち、C AC(0:27) 。

Cが通ったことで落ち着いたのか、続いてBも(今の要素, 前の要素)の組は1回ずつしか見なくていいことに気づき実装。B AC (0:38)。初めmathっぽく考えてしまった(初項を固定してみたりとか)

Dが一瞬で解かれていたのでshiatsumatに読んでもらいつつ後ろを見ていく。自分はJとかKとかを読んだがDをもらう。Gはcatupperが出来たということでG AC(1:08)

この辺まではそこまで悪くなかったのに詰まり始める。

しばらくして satashun さんがDは出来たと主張して実装してバグらせてくれました。アイディアは割とすぐ出たのに遷移がとてもバグってしまった(2つともを処理して終わったかどうかが適当だった) catupperはK出来たというのでパソコンの奪い合いのち、D AC (2:41), K AC (3:04)

Eは苦手なので2人に投げて、パソコンが空いている時間にJをしばらく考えていたらLCAが書ければできることに気付いた。

Jはsatashunさんが担当してバグらせてくれました。Eはcatupper、Fはshiatsumatが書いてた。

残りの時間はJを実装したりEを実装したりFを実装したりという感じだったがどれも通せず。Hもshiatsumatにより解法っぽいものが出てたが色のflipが詰めきれてなかったっぽい。

  • 反省

Fは2人とも嘘をついたせいで重いだけに見えてしまったのがミスだった(EとJが手詰まりに見えたからなんですが、冷静に幾何なんてやるべきではないだろ)

Eは自分は見てないけど2人の解法のいいところを取るといい感じだったっぽくて残念。

Jはほとんど合ってたが、lcaが変わる場合の処理が甘かった。終盤時間が足りなくて手元でサンプルを作る余裕がなかった。

Hみたいなの残り2人は得意っぽいので前半を早くして余裕が作れたらチャンスなんだけどなあ(2年前もskinny polygonが終わらなかった)

まあでも学内topが離れすぎていたためとりあえず手を付けた問題を全部解き切るための動きだったので、人を適宜マージしたら1問は増えた(上手く行けば+2)かなあというのがあるが、シンプルに実力不足だと思いました。中盤が多いコンテストだったので少し実力が伸びればだいぶ変わりそうなセットでした。

来年も出られれば5年連続同じチームということになるのでいい結果が残せるといいですね(赤くなろうね)