問題 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]を計算する。 す ...

Codeforces #279 (Div.2)のCが結構いい問題だと思ったので備忘録的に解説します。 問題 最大100万桁ある数が与えられる。この数をどこかの桁で左右に2つに分割した時に、前側の数がaで、後側の数がbで割り切れるようにしたい。ただし、分割した後の数は先頭に0を含んではいけない。もし、そのような分割があれば、その答えを、なければ-1を出力せよ。 解法(間違い) ものすごく単純に考えると、前後の数を多倍長でもって、その都 ...

問題 星が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軸方向に直進を続け、柵にぶつかったら左右どちらかに柵をよけるということを繰り返す。この ...

今回はSRM 633の解説です。 Easy (250点) 問題 2次元の無限に広いフィールド上をジャンプしながら進む人がいる。この人のジャンプのパターンは決まっていて、例えば{2, 5}というパターンを持っていれば必ず、距離が2のジャンプ、距離が5のジャンプを繰り返しながら進んでいく。今、この人は(0, 0)から(x, 0)に向かいたい。ジャンプは特に格子点を通る必要はないものとするとき、必要なジャンプの最小数はいくつ ...

こんにちはtatsyです。 今回はTCO 2014 Round 2Bの解説です。 Easy (350点) 問題 M個のスイッチを操作するゲームがあり、ゲームは全Nステージからなる。最初スイッチはすべてオフの状態になっている。各ステージでは与えられたスイッチの状態を満たすことでクリアできる。与えられる条件は「オン」、「オフ」、「どっちでもいい」のいずれか。各ステージでプレイヤーが行える操作はオンになっているスイッチを自由に選んでオフに ...

こんにちはtatsyです。 昨日行われましたGCJ2014のRound2。まさかの2byteの違いに泣かされてTシャツを逃しました。 終了直後、悔しすぎて悔し死にするんじゃないかと思うくらい悔しかったです。 とりあえず、何言っているか分からないと思うので、そのあたりも交えながら解説をしていきます。 今回解説する範囲は A Small / Large B Small / Large C Small D Small です。 A. Data Packing (Small: 5pt, Large: 8pt) 問題 ファイルがN個あり、それぞれのファイルの大 ...

こんにちはtatsyです。 今回はSRM622の解説です。 Easy (250点) 問題 ある国にはN個の街があり、このN個の街は完全有向グラフをなしている。この国にはアルゴリズムの日という日があり、この日には全ての街のペア(i, j)の間をバスが運行する。このバスは常に最短のパスを通ってiからjに向かうのだが、もし最短のパスが複数ある場合には運転手が任意の経路を選んでよいことになっている。この国の道路は老朽化が進 ...