Cまで三完。薄橙に戻れず悲しい。
D. Priority Queue
一応、自力AC。
各数字に関して寄与を求める、というところまでは良くて、その後の立式で詰まった。
ただ、各「+ x」というクエリについて、一遍に（累積和的な何かで）上手くするという方向で考えていたのはまずかった。
各「+ x」というクエリについて、二乗の計算時間をかけて良いのだからDPすれば良いのか、と思えたのは終了10分前くらいだった気がする。
そこまで分かってからも実装には苦労した。が、おおまかにはコンテスト中にやろうとしていた実装で合っていた気がする。
「+ x」というクエリのxに関する和を求めたいとき、DP[i]でxがi番目に小さいようなものの場合の数として、「+ x」の後に、
・「-」というクエリが来たときは、半分の確率で一つ減らす。（つまり、DP[i-1], DP[i]にDP[i]を加算）
・「+ y」（x<y）というクエリが来たときは、半分の確率で一つ足す。
・それ以外の場合、全ての要素を二倍にする。
という感じで。
なお、「+ x」の前のクエリについては、似ているけどちょっと違う処理をしなければいけなかった。上手く書けばまとめられるのかな……。
さらに、同じ数字のときの処理も難しい。コンテスト後の提出ではそこでWAを出して苦労したので、コンテスト中に通すのは厳しかったかもしれない。
こういう、ちゃんと詰めるのって苦手なんだけど、どうすれば向上するのかな。
0 件のコメント:
コメントを投稿