mayoko’s diary

プロコンとかいろいろ。

2016-02-07から1日間の記事一覧

Codeforces Round #219 (Div. 1) B. Counting Rectangles is Fun

問題 codeforces.com 解法 累積和の鬼になります。 まず, ok[y1][x1][y2][x2] = (長方形 (y1, x1, y2, x2) が good rectangle であるかどうか) というのを考えたいですが, これは長方形 y1, x1, y2, x2 内の値の cell の値の合計が 0 であれば良くて, これは…

AtCoder Beginner Contest 033 D - 三角形の分類

問題 abc033.contest.atcoder.jp 解法 各頂点 i について i 以外の頂点について偏角ソートします。あるペア (j, k) (j pi/2 であったら, 三角形(i, j, k) は確実に鈍角三角形であると言えます。また, 直角や鈍角になる場所はたかだか 1 つしかないので, 重複…

SRM 681 div1 med: LimitedMemorySeries2

問題 TopCoder Statistics - Problem Statement 解法 愚直にやって普通に解が得られます。配列 X の最大値を xmax とすると, xmax 未満の値は xmax を超えて半径が飛んでいくことはないので, xmax で配列が分割されることになります。xmax が真ん中にあると…

SRM 681 div1 easy: FleetFunding

問題 TopCoder Statistics - Problem Statement 解法 二分探索で答えを求めていきます。ok(x) = (x 個の spaceship を作ることが出来るか?) とします。b の小さいのから順にパーツを作っていくと, 後ろのパーツを作るのになるべく余裕をもたせられるように…