累積和
問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…
問題 問題概要 オセロの向きを求める。 解法 一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算…
問題 問題概要 AとBが与えられる。そのなかから、連続するK以上の部分のAの合計と、Bの合計をそれぞれ出して、(Bの合計)/(Aの合計) の最大値を求める。 解法 全探索で通る。単純にすべての区間について、(Bの合計)/(Aの合計)を出していけばいい。これだとn=1…
問題 問題概要 省略 解法 2次元imos法を使えば楽なんですね。 imos法 いもす法 - いもす研 (imos laboratory) BITとかsegtree使うのかな、て感じだった。 2次元BIT http://hos.ac/slides/20140319_bit.pdf ミス imos!! コード 2次元imos法 #include <iostream> #includ</iostream>…
問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。 ミ…
問題 問題概要 2次元累積和。 解法 このサイトを参考にした。 paiza.hatenablog.com 白か黒をマイナスの数字として扱うことで、2次元累積和を用いて計算することができる。やり方は、まず、横方向の累積和を取り、次は、それを縦方向に累積和をとる。この…