ABC127に参加しました - りつくろいす

最近累積和を覚えて、その有能さに感動しているせーりつです

今回のABCは勉強の成果が出たんじゃないかという回でした

結果はABCDの4完です

初めて4完したのでとても嬉しかったです

それぞれについて解説していこうと思います

問題文を読んで以上・以下について理解していればできる問題です

最初、「6歳以上」を「5歳以上」と見間違えたまま提出しようとしたのは内緒です

これも問題通りにやれば解くことができます

配列で値をいちいち保持しておかなくてもx = x * r - Dを出力しながらループを回していくことで答えがでます

全てのゲートを通ることが条件でありL,RはN以下が保障されているので、Lはできるだけ大きくRはできるだけ小さくしてR - L + 1を出すことで答えが出ます

R - L + 1が0未満の時は答えは0です

上から大きいのをもっていってやるだけなんですが、Cの最大値未満のものが全て置き換わるわけではないので注意します

この問題、初めはCの最大値未満のものを全て置き換えていたのですが、これだとうまくいかないし、置き換えるものと換えないものの判定が面倒だったので没に

次に考えたのは、結局上から取っていくのでCiの分BiをAに追加してやり、降順にsortして上から取っていく方法でした

これは確かに正しい値が求まるのですが、配列の数が多すぎて実行時エラーになってしまいました

次に、実行時エラーになるならいらない奴は消してあげればいいじゃないかと考え、毎回追加するたびにsortして、後ろから追加した分抜いてやるというようにしたら予想通りTLEになってしまいました

最後に思いついたのが、pairで同じ数値のカードの枚数を保持する方法でした

vector<pair<ll, ll>> pairsに対して(Ai, 1)、(Bi, Ci)でpairを作り、1番目の要素について降順sortをしてpairs[i].secondの和がnになるまでpairs[i].first * pairs[i].secondをしたものを足せば答えとなります

ちなみに、priority queueというものを使えばもっと楽にできるみたいです

僕は名前しか知らなかったので思いつきもしませんでした

ABが5分で終わり、Cが終わった時点で15分ぐらいだったので大分成長を感じました

さらに残り10分でDの解答を思いつくことが出来たため優勝できました

レートが順調に伸びてくれているので、この勢いをなくさないようにしていきたいところです

明日のABCも頑張ります