Fまで六完。
コンテスト後のツイート
EはTLEの間違いです。
— titia (@titia_til) December 25, 2021
また、多倍長を利用して上手くやる方法もあったのですね。
G - Strongest Takahashi
解説放送を見てAC。
全然DPを考えなかった。「行か列かで分割して良い」ということに気付くかどうか、というどちらかというと発想の問題ですね。
Codeforcesで既出で、以前コンテストに参加していたものの未ACの問題でした。今回ACできて良かった。
Ex - Manhattan Christmas Tree
解説放送を見てAC。並列二分探索に関するアルメリアさんの解説も参考にしました。
「並列二分探索」というのは、何か自分の知らない特別な手法なのかと思っていたのですが、並列に二分探索するだけでしたね。怯える必要なかった。
ただ、放送を見てしばらく、なんで並列でできるのか分からず困りました。分かってしまえば当たり前なんですが。
最初理解できなかったのは、「答を決め打って二分探索」、という意識があったせいかな……。今回のような問題だと、データ構造を使い回して並列化できるのですね。
各クエリごとに二分探索はできるけど、あまり賢い方法はなさそうなときは、並列二分探索を疑おう。
0 件のコメント:
コメントを投稿