CodeForces #Pi Div.2

今回は2完でCを解くことができなかった。特にDは解法のアイデアが浮かんでいたが本番では実装できず残念。焦りすぎず、コンテストに慣れる、生活リズムをデチューンする必要が感じる。(1672->1601)Div.1が遠ざかる。

A. 

Aにしては多少難しい？とりあえずソートをして各要素ごとに最大値、最小値をチェック。

最大値：　要素の一番端っこの要素

最小値：　要素の隣の要素

O(nlogn)

B.

いる人数の配列をとる。ログイン、ログアウトを記録していく。データ構造はsetを使っとく。明記されてないIDがログアウトしたときはそれ以前の人数を1足す。

C.

b*k^0,b*k^1,b*k^2がポイント。真ん中を基準にして考えるとb/k,b,b*kとなるので、それ以前にb/kが何回あって、それ以降にb*kが何回あるかわかればよい。

bは負の値もとるのでmapをつかってやるのがよい。それ以降のcountとそれ以前のcountをしらべるのは典型的なので省略。

D.

領域を分割すると考えてやるとわかりやすい。shotsがされるたび領域が分割されていく。入れることができる船の数がkより小さくなればそこが答え。

|............|............|

|....|.......|............|

ここでshotsされて分割される領域以外に入る船の数はかわらないので分割されたときの差分を考えてやればいい。shotsされた点はsetで保持しておく。shotsがどの領域

にあるかはupper_boundでしらべればいい。

門番として0,n+1をsetにinsertすると楽。