問題文→2104 -- K-th Numbersort()とか使うと間に合わないので 区間ごとのx以下の個数を二分探索で数えます。しかし二分探索にはソートが必要なのでマージソートの要領でセグメント木を作っておき、必要な区間に対してのみ二分探索を行えば間に合うみたいで…

問題文→ AIZU ONLINE JUDGE「あるマスを選んでそこの数字を反転(1 0)させる。 この時そのマスの上下左右も反転する。 すべてを0にするために必要な反転箇所を求めよ」 という問題。普通に考えたら O(2^100)とかで無理。 そこで一番上の行の反転の仕方を一意…

問題文→2385 -- Apple Catchingりんごが1分ごとに2本の木のいずれかから落ちてくる。2本の木を決められた回数内行き来して落ちてくるりんごをキャッチする。 キャッチできるりんごの合計の最大値を求めよ。とりあえずメモ化再帰を書いてみる。しかしこれでは…