Hatena::Grouptopcoder

zerokugi's contest memo

2015-10-01するめも

雑に書いていく

SRM 673 Div1 Med BearPermutations

dp1[N][cost+center] と dp2[N][cost] の二つを同時に計算する

挿入DPだが、端に挿入する時は dp1 を使って、中に挿入する時は dp2 を使って計算する。

中に挿入するときのコストは (左部分木の cost+center) + (右部分木の cost+center) + 2 になる。



SRM 594 Div1 Med FoxAndGo3

'o' と '.' に置く/置かないで最小カット

教育的

2部グラフの最大独立集合でも解けるらしい

SRM 593 Div1 Med MayTheBestPetWin

max(B(S) - A(T), B(T) - A(S)) を最小化してやればよい

1アイテムを移動させた時に差は A[i]+B[i] だけ変わるので、まずA[i]+B[i]でナップサックして作れる数字を列挙してやる

それを使って max(abs(Asum - X), abs(Bsum - X)) の最小値を探せばよい

SRM 592 Div1 Med LittleElephantAndPermutationDiv1

dp[iまでの数字で][合計がj][max側にならなかった数字がk個]=個数でDP

O(n^4)

MLEに注意

典型?DP

SRM 591 Div1 Med PyramidSequences

こういうの超苦手

とりあえず二次元グリッドに射影してみる

gcdが1の場合とそれ以外の場合で分けて考えてみる

頑張って数える

以上

SRM 590 Div1 Med XorCards

0/1 行列と見てとりあえず掃き出して上三角にする

あとはbitを上から見ていって足していく

教育的

SRM 589 Div1 Med GearsDiv1

Rが時計回り GとB が反時計回りだと仮定すると、G-B間に辺が張られないようにすればよい → 二部グラフの最大独立集合

(R, G+B), (G, R+B), (B, R+G) の3通りでチェック

SRM 588 Div1 Med KeyDungeonDiv1

開けた扉の組み合わせを固定した時、

  • 手元にある鍵の総数は固定
  • 白鍵は多いほどよい
  • 赤と緑をどう持っておけばよいかは未確定

なので dp[開けたドア2^n][持ってる赤い鍵] = 白い鍵の最大化 でDP

SRM 587 Div1 Med TriangleXor

図を眺めると、高さが y_i の三角形が i 個あって包除されたそうな配置になっているので包除する

SRM 585 Div1 LISNumber

同じ数を区別つくものとして計算して最後に順列で割っていく

dp[i番目までの数字を並べて][非増加な部分の数がj個] の数え上げDP

新しい数を非増加でない部分に入れると、非増加な部分が増える

遷移時に何倍になるかがちょっとややこしい

典型DP…?

SRM 584 Div1 Excavation

深さ d の not found なアイテムについて、

  • それを採用
  • d 未満のnot foundなアイテムは採用
  • d 未満のfoundなアイテムを最低1つ以上ずつ取る
  • 残りをd以上のものから適当に取る

という条件を満たすものを数え上げていく

SRM 583 Div1 TurnOnLamps

フローの押し戻しのように考えると、パスは伸ばせるところまで伸ばせば良いと分かる




SRM 524 Div1 LongestSequence

累積和を取ると不等号制約になるので、ループ (a[i]<a[i])が存在しない最大の長さをにぶたんで求める</ppp>

(にぶたんしなくても求められる)

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/zerokugi/20151001