模擬国内にQWE_QWE(kort0n,risujiroh,Rubikun)で出て6位でした。
Aを僕、Bをrisujirohさん、Cをkort0nさんが読む。
Aを通し、Dを読む。(6:31)
Bが通って、Eを読んでもらう。(19:23)
C重くないか?と言いながらFAで通してた、すげー。(29:16)
Eが長い、Fが酷いらしい。
Dがわからないのでkort0nさんにhelpを求める。
すぐに浮かんだらしくそれを聞いてわかった気になってじゃあ実装任せていい?と言われて書くが入力を受け取っただけで手と頭が止まり、やっぱり実装を返すことに(は?)
Dが通る。(41:43)
題意がわかったらしくEが通る。(52:32)
たしかこの時点で1位でFGHがどれも通っていなかったはずで、FGHをkort0nさんと僕が知っている状態になっていた。
kort0nさんがFっぽいので任せて、risujirohさんがGっぽいので概要を伝えていろいろ喋る。
多角形の頂点しか使わないだろとなり1ケースあたり3乗の解法が生える。
線分が多角形の中を通ってしまうかの判定が辺と交差しているかだけではできないことに気づいてやばいとなる。
順位表を見たらHが通されているのでこれもrisujirohさんに概要を伝えていろいろ喋る。
後手は1択ということがわかり、暇な時にサンプルを手でやっていたので、閉路があったら0にできるためDAGだけ考えれば良いなどのことがわかる。
(何やってるかわからず)
考察実装をがんばってくれてHが通る(2:03:22)
risujirohさんがGに戻ってkort0nさんがFをやっていて残り問題が2問しかないのでFに適当にガヤを入れるが厳しそう。
ここ並列実装可だからもう少しやりようがあったかもしれない。
コンテスト終了
感想
参加記むずい