昨日のCodeforcesはめずらしく良くできた気がするのでざっくり解説しておきます。 A. Vasya and Football 問題 サッカーのようなゲームが行われていて、90分間の間にホーム側の選手、アウェイ側の選手でどの番号の選手がイエローカード、レッドカードをもらったのかが与えられる。なお、イエローカードを2枚もらうと自動的にレッドカードとなる。このとき、各選手が初めてレッドカードをもらった時間を出力せよ。 解法 どうやら、問題の ...
今回はSRM639の解説です。 問題は Easy: 数学っぽい分析 Medium: 組み合わせ となっております。 Easy (250点) 問題 AとBのプレイヤーが交互にあるゲームで戦っている。ゲームはターン1からスタートし、ターンiで勝利した方には2i-1点入る。このときAとBが得た点数がそれぞれx, yと与えられる。これを実現するためにはAは最小何回勝たなければいけないか？もし条件を満たすものが存在しないときは-1を返せ。 制約条件 0 <= x, y ...
今回はSRM637の解説です。問題内容は Easy: 確率(?) Medium: Grandy数 となっております。それでは行きます。 Easy (250点) 問題 1から2Nまでの整数がある。この整数を2人でN個ずつに分けて、1つずつ出して勝負していく。数が大きい方が1ポイントを獲得する。あなたは相手が数を出す順番が部分的にわかっていて、それが数列で与えられる。分からない箇所は-1になっている。あなたはそれを見て最適な数字を出す順番を決め ...
問題 長さが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]を計算する。 す ...
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軸方向に直進を続け、柵にぶつかったら左右どちらかに柵をよけるということを繰り返す。この ...
