srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

累積和

aoj 1176 Planning Rolling Blackouts

問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…

ABC 035 C - オセロ

問題 問題概要 オセロの向きを求める。 解法 一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算…

SRM 690 div2 medium GerrymanderEasy

問題 問題概要 AとBが与えられる。そのなかから、連続するK以上の部分のAの合計と、Bの合計をそれぞれ出して、(Bの合計)/(Aの合計) の最大値を求める。 解法 全探索で通る。単純にすべての区間について、(Bの合計)/(Aの合計)を出していけばいい。これだとn=1…

yukicoder No.60 魔法少女

問題 問題概要 省略 解法 2次元imos法を使えば楽なんですね。 imos法 いもす法 - いもす研 (imos laboratory) BITとかsegtree使うのかな、て感じだった。 2次元BIT http://hos.ac/slides/20140319_bit.pdf ミス imos!! コード 2次元imos法 #include <iostream> #includ</iostream>…

ABC 014 C - AtColor

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。 ミ…

ARC 025 B - チョコレート

問題 問題概要 2次元累積和。 解法 このサイトを参考にした。 paiza.hatenablog.com 白か黒をマイナスの数字として扱うことで、2次元累積和を用いて計算することができる。やり方は、まず、横方向の累積和を取り、次は、それを縦方向に累積和をとる。この…