TopCoder SRM578

250

盤面上にいくつか鳥がいて、そのうち何羽かは goose である。goose は 1 羽以上存在し、偶数羽存在する。goose から Manhattan 距離 D 以下の鳥は goose である。goose の場所のパターンは何通りあるか。

距離 D 以下の鳥の属性(goose or not) は同じでないといけないことが示せる。
Union Find したあと DP した

500

直線状のマス目の上に何頭か wolf がいる。1 マスに wolf は高々 1 頭いる。いくつかの、「この範囲には wolf は高々 2 頭しかいない」情報が与えられる。wolf の場所は何通り考えられるか。

[位置][最後の wolf の位置][その前の wolf の位置] で DP

1000

わからない

challenge phase

あたしのいくじなし〜＞＜

結果

oox 633.67 (14 位)
rating: 2783 -> 2824