Eまで五完でした。
E - Red Polyomino
この問題を思い出したので、この解法で解いた。
ただ、DPしているけど、別に計算量は良くないね。
解いているとき、Kの制約をあまり見ていなかったのだけど、たとえばN=8, K=32ならTLEするので、この解法で解く意味はあまりなかったよう。
ただ、コンテスト中、全探索もちょっと考えたものの実装がよく分からず避けた、という面もあるので、うーん。
F - Rectilinear Polygons
コンテスト中に考えていた方法で自力でACできました。
つい二次元累積和（imos法）を考えたくなるけれど、この問題では座標圧縮もきかないため間に合わない。
そこで、平面走査を思い付くのが重要。
x座標が小さい順に見よう、と思えば後はポリゴンの処理が悩むところ。
そこは、縦の線分を順番に見て行ったとき、前の線分と重なる方向か、同じ方向か、で場合分けすると上手くいきます。
Eまでに時間がかかったのと、平面走査を思い付くまで時間がかかったため解き終わらなかったけど、これは解けなくてはいけない問題でした。
今度からABC八問体制になるそうで、そうすると全完はかなり厳しくなりそう。今回はチャンスだったと思うので、もったいなかった。
0 件のコメント:
コメントを投稿