602.1

頭悪いって次元を超越してた...。

250

整数配列が与えられる。現在の値が与えられて、整数配列の要素を順番に足すか引くかしていく。引いたときに負になったら0にする。2200以上の値に二回続けてならないようにしながら、2200以上である状態とそうでない状態が切り替わる回数を最大化したい。最大値を答えよ、という問題。

とにかく2200を連続してオーバーしたらおしまいなので、次の値を即座に引く、という感じで、2200未満の範囲になるようにしてやって、適当にDPすればいいらしい。

頭悪いので、2200までと前の値から2200個くらいの範囲の両方でDPした。頭悪すぎる。

550

たくさんある長方形を同じ数のグループに分けるときに、それぞれのグループについて、全部の長方形が重なっている領域の面積を求めて、その合計の最大値を答えよ、という問題。

ランダムアクセス可能なソート済みリストが作れますか、という問題。実装やるだけゲー。

長方形を短い方の辺の長さ順にソートしてやる。こうすると、最初のグループには最初のヤツが必ず入る。二つ目のグループにはK番目以降を入れることにしてやれば、両方のグループの長方形の重なる領域の短い辺の長さが決まる。なので長い方の辺を決めたいわけだが、最初のグループはK-1番目までの長方形の長い方の辺の最小値以下になることが分かってて、二つ目のグループは残りの長方形の長い方の辺をソートして持っておいて、先頭を最初のグループにあげるか、末尾を最初のグループにあげるかのどっちか。とかそんな感じで解けるはず。

メモ

欲しいヤツの位置が一個ずつしかずれないので、ずれる方向の側に要素追加するか、自分が一個ずれるかのどっちかなので、PriorityQueueで適当に計算できるぽい。ソート済みリストは別の機会に...。

1000

見てない。