119. AtCoder参加記録（AtCoder Beginner Contest 256）

24回参加でレート 1245 です。

今回はパフォーマンス 1357 です。

ABCDEを通して、FGExは未解答です。Eで2ペナ。

各問題の感想など。

A

50秒。

256と掛けた問題？普通に計算すればOK。

B

4分17秒。

単純にシミュレートすればOK。駒を進める時は逆順に走査するとバグりにくいです。

C

10分39秒。

左上から $2 \times 2$ マスが決まれば残りのマスは和の情報から算出できます。よって、この4マスについて全探索すればよいです。計算量は $M = 30$ として $O(M^4)$ 。

若干バグらせて3分ほど時間取られました。

D

6分16秒。

図を書いて考えると、ああこれ imos 法だな…とすぐ分かりました。左 +1、右 -1 として、最後に累積和を取るフェーズで 1 以上になっている連続した区間が求めるものです。

E

初回提出13分1秒、そこからACまで38分16秒。

入力例を見て、「最もヘイトを買わない人から順に配っていけばよいのでは？」と直感。ただ、あまり証明は見えませんでした。とりあえずそのように実装してみるとサンプルは合うので投げてみる。半分以上 WA で、一旦撤退しました。

そこからしばらくFを考えていて、Eへ戻ってきたときに「配るたびに "最もヘイトを買わない人" って変わるやん」と気付く。PriorityQueue に突っ込んで、配った人がヘイトを持つ人の分だけ減らして…とやるが、PriorityQueue は一度取り出してもう一度突っ込む必要があったことに気付く（ここで 2WA 目）。仕方ないので MultiSet に変更して、1800ms とギリギリで通せました。