https://atcoder.jp/contests/abc416/tasks/abc416_d足してM以上になるペアをなるべくたくさん作ればよいです。Aを降順、Bを昇順にして、尺取り法的に処理すればよいです。 // Match, Mod, Minimize 2 #![allow(non_snake_case)] //////////////////// libra…

https://atcoder.jp/contests/abc415/tasks/abc415_f二分木を使って、各ノードに左端からどの文字が何文字連続しているか、それに右端とそれ以外も保持しておきます。 // Max Combo #![allow(non_snake_case)] //////////////////// library ///////////////…

https://atcoder.jp/contests/abc415/tasks/abc415_e右と下しか進めないのでDPでよさそうですが、xを決めないで計算しようとすると、今の持ちコインとともに今までのパスで最小のコイン数も保持しないといけなくて大変そうです。しかし、xを決め打ちすれば、…

https://atcoder.jp/contests/abc415/tasks/abc415_d今の瓶の数をnとすると、Aがn以上でA-Bが小さいショップを選べばよいです。なので、BTreeSetでA-B順にショップを並べて、別にAで並べたショップVecを持っておき、ショップのAがnを超えたらBTreeSetとVecか…

https://atcoder.jp/contests/abc414/tasks/abc414_ebとcを決めると取り得るaの個数が決まります。例えば、なら、だから9個です。一般には個になります。なので組合せの個数は、となります。とおけば、となります。内側の和は分母がbで分子は連続でb-1個ある…

https://atcoder.jp/contests/abc414/tasks/abc414_dまず基地局を各家に設置します。そして、基地局をMまで減らします。そのとき、d離れた家を基地局がカバーすることにすると、電波の強度もdになります。複数の家をカバーする基地局にもう一つ家をカバーで…

https://atcoder.jp/contests/abc413/tasks/abc413_fゴールからはじめて先入れ先出しすればよいです。取り出したグリッドの隣を見てその隣が2つ以上最小移動回数が確定で、小さいほうから2つ目が取り出したグリッド+1なら、最小移動回数が決まります。 // No…

https://atcoder.jp/contests/abc413/tasks/abc413_eよく反転する範囲を調べると、全体を半分にして右半分の最小値が左半分より大きければ、すなわち右半分に1があれば全体を反転するしかないことがわかります。そして、左半分と右半分をそれぞれ同じことを…

https://atcoder.jp/contests/abc412/tasks/abc412_f外にある靴下も合わせてAにして降順にソートします。今外にある靴下がでを取り出したとき、なら終わり、ならをそのままに、ならをそのままにすればよいので、期待値は、 として、 となります。これは少し…