結構簡単なセットでした。
小さい方で割り算してもいいし、割り算した結果の大きい方を取っても良い。個人的には前者。
入出力の体裁をちゃんとすること。あと「混ぜて買っても意味が無い」という点に気付くこと。
いわゆるクエリ問題。NもQも100なので、そのままシミュレートしても最悪O(NQ)で間に合う。(最悪ケースは毎回N個全て塗り替えるケース)
実はN=Q=10^5でも間に合う解法がある。O(QlogN)。遅延segment tree。
-
先に(xまでの部分和)というのを全てのxについて取る(1つずつ増やすだけなのでO(N)で求まる)と、 aからbまでの部分和は(bまでの部分和)-(a-1までの部分和)で定数時間で求まる。これを(N-K+1)回。
-
K個が覆う範囲を考えると1個ずつずれていく。1個追加して1個消して、というのを(N-K+1)回。
-
a[i]が何回足されるか、というのを可視化して観察すると、台形になる。これを考えて計算。
なお、毎回K個の和を求めるとN=10^5、K=5*10^4の時などでTLEする。部分点は取れる。
「あるマスから始めた結果は、元データが変わらないなら、変わらない」
「あるマスAはあるマスBに影響を与え、かつ、マスBがマスAに影響を与える、のように、ループが起きない」
という点に気付く。すると、各点においての答えを保存しておけることが分かる。(メモ化)
あるマスの答えを得るために、上下左右の条件を満たすマスの答えを足す、ということをして、答えを保存しておく、というようにする。
もし上下左右のマスで答えが求まっていなかったら、そのマスについての計算を開始する、というようにしていく。(再帰)
この計算量を考えるのは少し難しいかもしれないが、各マスについて1回だけ計算が行われることを考えると、マスの数に比例した計算量O(HW)になる。
1つのマスの計算について、どんどん深く再帰していくと、計算量がO( (HW)^2 )になってしまわないか心配になるが、 あくまで「1つのマスの計算」は、最大でも上下左右の4つの「計算結果」を参照しているので、「定数時間」で終わる。
これをメモ化DFS(DFS:深さ優先探索)、メモ化再帰、などと呼ぶことがあり、頻出テクニックである。
なお、「上下左右」について、同じような処理を4回も書くのは非常に冗長であり、バグの温床となるため、避けたい。
そのため、競プロでは以下の様なテクニックが頻出である。
// int x,y;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
for(int i=0;i<4;i++){
int next_x = x+dx[i];
int next_y = y+dy[i];
}方向のベクトルを配列で保持しておくことで、ループを利用できる。これで処理が1つ書くだけで上下左右に適用できる。
なお、このテクニックに関わらず、座標が範囲外に出る場合については気をつけたい。
条件分岐で処理するか、予め範囲外にありえないデータを配置して条件を満たさないようにする(番兵テク)かしないといけない。
ちなみに、組み合わせの数を求める問題では一般に組合せ爆発が起こるため、素数である10億7で剰余を取った値を解とすることが多い。