ABCEの四完でした。D難しい。
D - Congruence Points
すぬけさんの解説動画を見てAC。Pythonで$O(N^3)$でも65msでした。
いやでも確かに難しいのだけど、Sの一点目から二点目へのベクトルが、Tのどの二点のなすベクトルと対応しているか？ で二乗をかけるという方針は思いつかないといけないですね。
そこまでできていれば、回転を複素数で計算という部分はできたかもしれない。本番中にも複素数を使うことは頭をよぎったはずなので。
コンテスト中は、（他の人も結構ハマってましたが）角度を決め打って云々、という嘘解法にハマってました。
F - Tree Patrolling
すぬけさんの解説動画を見てAC。
二乗の木DPの問題は最近も解いていたのだから、自力でできなくちゃいけなかった。
が、解説を聞いた後なのに、遷移を書くのに苦労したり、modを取り忘れたり、コーナーケースに引っ掛かったりとWAを量産してしまった。
二乗の木DPで、子同士をマージするときの遷移は大体いつも似た感じいなるのね。FFTを使える形になるらしい。以前の二乗の木DPの問題でも、「遷移を書くのが面倒だったからFFTを使った」とか書いているツイートを見かけたけど、なぜそういうことができるか理解できた。
それに気付けたのは収穫。
0 件のコメント:
コメントを投稿