GCJ 2018 round2

A 問題

i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。

B 問題

丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。
(i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置くと言い換える。駒がおいてある場所の総和が R, B 以下なら良いわけだけど、もし駒の上が空になっていたら上に動かしたほうが得である。
つまり駒の置いてある形はヤング図形のようになっている。また、ヤング図形の幅、高さは 40 程度である（これは 1+2+3+...+40 > 500 から言える）。
以上を踏まえると DP で解ける。

C 問題

値ごとにバラして考えて、変えない場所を最大化することを考える。これは単純な最大二部マッチングに帰着される。

D 問題

単なる場合分けだと思うけど通らなかった…。