問題 長さがNの数列が与えられる。その数列の長さ5の部分列で狭義単調増加するものの個数を答えよ。 制約条件 1 <= N <= 50000 解法 まず、答えがどのくらい大きくなるかを考えます。答えが一番大きくなるのは1, 2, 3, …, 50000の時で、その時の解は$_{50000} C_5 \approx 2 \times 10^{31}$になるので、64bit整数でも収まりません。 なのでおとなしく多倍長演算を書きます。今回は足し算だけあればいいと思います。 つづいて、 ...
問題 N個のノードからなる木構造が与えられており、初期状態では各ノードにリンゴがなっている。この木構造に対して2種類のクエリが合計M個与えられる。1つ目のクエリは、指定されたノードを根とする部分木に何個のリンゴがなっているかを答えるもの、もう1つは指定されたノードのリンゴの状態を反転させるもの(リンゴがあったら無くなり、もしあれば新しく実る)である。このクエリを高速に処理せよ。 制約条件 1 <= N, M <= 100000 解 ...
問題 街がN個ならんでいて、ある街iはi-1の街とi+1の街と接続されている(両端は除く)。このとき、街を破壊するクエリ、最後に壊された街を復旧するクエリ、そして、指定された街からみて、連続な破壊されていない街の数を答えるクエリの3つがM個与えられる。素早くクエリを処理せよ。 制約条件 1 <= N, M <= 50000 解法 情報の見方を少し変えて、左からi番目の街までに壊された街の数を配列a[1],…,a[N]を計算する。 す ...
問題 星がN個あって、それぞれにはX,Yという二次元座標が整数で与えられている。それぞれの星にはランクがつけられており、星のランクはその星より左下にある星の数で決まる(同じX座標あるいはY座標を持つものも含む)。このとき、ランク0からランクN-1までの星の個数を答えよ。 制約条件 1 <= N <= 15000 0 <= X, Y <= 32000 解法 早とちり常習犯の僕は、問題を読んだ瞬間に「二次元BIT」でいけると思い、コードを書いてSubmit ...
問題 長さがNの同じ要素を含まない数列Sがある。この数列の中で2つの番号i, j (i<j)を選んだ時、その間に含まれる数がSiより大きくSjより小さくなるような連続した部分列のうち最大の長さの物を求めよ。もしそのような部分列が存在しないときには-1を返しなさい。 制約条件 1 <= N <= 50000 1 <= Si <= 1000000 解法 まず単純に考えると、適当に番号iとjを選んで、その間の数がSiとSjの間の数になっているかどうかをbru ...
問題 ジョンの牧場はx座標が-1000000から1000000、y座標が0からNを取る整数座標と考えられる。各y=1…nについてx軸と平行な方向に柵が作られていて、i番目の柵はa[i]からb[i]まで続いている。ある牛は原点(0, 0)をスタートしてゴールである座標(s, n)に向かう。この時、牛は柵にぶつかるまではy軸方向に直進を続け、柵にぶつかったら左右どちらかに柵をよけるということを繰り返す。この ...
