SRM 610 Div2 Codeforces #247 Div2

累積和 SRM DP Codeforces

SRM 610 Div2

Easy Divided By Zero

配列のある要素を別の要素で割った商が配列に存在しないなら商の値を配列に追加する

一回全部試しても増えたのとすでに走査してあるのを試して無かったりってのがあるので適当な回数無駄に回すと

Med TheMatrix

市松模様になってる長方形の最大面積

市松模様が成立するにはある範囲内の

  • (y+x)が奇数のセルが黒、偶数のセルが白
  • (y+x)が偶数のセルが黒、奇数のセルが白

のどちらか

累積和をとって計算するO(N4)

Hard MiningGoldEasy

NxMの二次元領域がある。ここでは毎日宝が見つかる。任意のセルからスタートして毎日、xかy軸に沿って任意の距離移動できる。そして、N+M-(宝と自身のマンハッタン距離)だけ利益を得られる。利益の最大化

以後登場するどこかの宝にX座標かY座標をそろえるように動くといい。D2通りの移動する可能性のあるセルがある。D日、D2個。移動候補xy、D通り。O(N4)らしいです。解説読まんと分からん

Codeforces #247 Div2

A Black Square

1,2,3,4だけ含まれるSが与えられる。S[i]の値に対してa[x-1]の利益が与えられる。利益の総和はいくつか。

やるだけ

B Shower Line

5人の人が１つのシャワーを使うために一列に並んでいる。列に並んでいる人たちは前から二人ずつで話している。iとjが話したときの幸福度Gijが与えられた時。幸福度の総和が最大になる並び方のときの幸福度の総和

全ての順列を求めてそれぞれ幸福度の総和を求めていく。

C k-Tree

根付き木だよ。完全なK分木で、各頂点はK個の子を持ちそれぞれの辺へのコストは1,2,3...K。根からの最短到達コストがNでかつコストD以上の辺を一回以上通過しないと辿りつけない頂点の数は？

全部で5完でしたそれなりに解けた方です