TopCoder SRM 639 Div1

今回はSRM639の解説です. 問題は Easy: 数学っぽい分析 Medium: 組み合わせ となっております. Easy (250点) 問題 AとBのプレイヤーが交互にあるゲームで戦っている.ゲームはターン1からスタ… Continue Reading


TopCoder SRM 637 Div1

今回はSRM637の解説です。問題内容は Easy: 確率(?) Medium: Grandy数 となっております。それでは行きます。 Easy (250点) 問題 1から2Nまでの整数がある。この整数を2人でN個ずつに… Continue Reading


POJ 3378: Crazy Thairs

問題 長さがNの数列が与えられる。その数列の長さ5の部分列で狭義単調増加するものの個数を答えよ。 制約条件 1 <= N <= 50000 解法 まず、答えがどのくらい大きくなるかを考えます。答えが一番大きく… Continue Reading


POJ 3321: Apple Tree

問題 N個のノードからなる木構造が与えられており、初期状態では各ノードにリンゴがなっている。この木構造に対して2種類のクエリが合計M個与えられる。1つ目のクエリは、指定されたノードを根とする部分木に何個のリンゴがなってい… Continue Reading


POJ 2892: Tunnel Warfare

問題 街がN個ならんでいて、ある街iはi-1の街とi+1の街と接続されている(両端は除く)。このとき、街を破壊するクエリ、最後に壊された街を復旧するクエリ、そして、指定された街からみて、連続な破壊されていない街の数を答え… Continue Reading


Codeforces #279 Div.2 – C. Hacking Cypher

Codeforces #279 (Div.2)のCが結構いい問題だと思ったので備忘録的に解説します。 問題 最大100万桁ある数が与えられる。この数をどこかの桁で左右に2つに分割した時に、前側の数がaで、後側の数がbで割… Continue Reading


POJ 2352: Stars

問題 星がN個あって、それぞれにはX,Yという二次元座標が整数で与えられている。それぞれの星にはランクがつけられており、星のランクはその星より左下にある星の数で決まる(同じX座標あるいはY座標を持つものも含む)。このとき… Continue Reading


POJ 2452: Sticks Problem

問題 長さがNの同じ要素を含まない数列Sがある.この数列の中で2つの番号i, j (i<j)を選んだ時,その間に含まれる数がSiより大きくSjより小さくなるような連続した部分列のうち最大の長さの物を求めよ.もしその… Continue Reading


POJ 2374: Fense Obstable Course

問題 ジョンの牧場はx座標が-1000000から1000000,y座標が0からNを取る整数座標と考えられる.各y=1…nについてx軸と平行な方向に柵が作られていて,i番目の柵はa[i]からb[i]まで続いてい… Continue Reading