SRM 623 Div2 Codeforces #259 Div2

SRM 累積和 Codeforces

SRM 623 Div2

Easy CatchTheBeatEasy

2dゲーム。(0,0)をスタート、x軸上を移動できる。1ずつ。N個のフルーツがY軸マイナス方向に向かってくる。全部取れるか

フルーツのyが0の時にしか取れないのでyの昇順に取っていく。sortする。あとは現在の場所と時間を更新してすべてとれるか

Med CatAndRat

半径Rの円形のチューブがある。Vratの速度で移動するネズミを入れ、時間T後、Vcatで移動する猫を入れる。ネズミは猫から逃げる、猫はネズミを追いかける。ネズミが頑張った場合、猫に追いつかれる時間を求める。無理なら-1.0。

半径Rの円周上を追いかけっこするので C(円周) = 2R * PI。ネズミはできるだけ猫が来るまでに遠くに逃げたい、一番遠いのがC/2、ただたどり着けないこともある。VratT。つまりp =min(C/2, VratT)。あとネズミにpのハンデがあるので追いつくまでの時間を計算する。方程式を解くなりにぶたんもできるかも。

Hard ApplesAndPears

N*Nのグリッドがある。各セルにはりんご、なし、空の状態がある。フルーツを空のセルに移動する処理を最大K回行える。K回以下の処理を行ったあと、ある矩形領域がすべて同じ状態である領域の最大面積を求める。

  • 空のセルにフルーツを入れる。フルーツをどかすには1回の処理が必要。
  • なしからりんご。りんごからなしには、２回。

りんご、なし、空の累積和を計算しておくと、定数時間程度である領域全体をいずれかの状態にするのに必要な処理の回数を求めることができる。すべての矩形領域に対して処理を行うのでO(N4)かかる。N<=50なので間に合う。

どの状態にするかはここに計算する。矩形の最大領域。<= 状態の個数

'.'の個数が0なら移動ができない。K = 0

3完できました。

CF #259 Div2

A

対角線の長さがNの菱型を作る

B

aを単調非減少列にするのにひつような操作数。操作とはaの末尾を先頭に持ってくる。

aを単調非減少列の部分列に分ける。一つならすでに単調非減少列、2つでa[0]よりもa[N-1]が小さいならa[i] > a[i+1]になってるとこでわける。３つ以上は無理

C

m面のサイコロをn回投げてでための最大値がポイントになる。ポイントの期待値。

各xに対してxが最大になる期待値を求める。

2完