Codeforces Round #683 (Div. 2, by Meet IT) - 人間だけど競プロやる

A. Add Candies

A=[1,2,3,...,N]は図にすると階段状の三角形になるので、逆向きの三角形を足せば四角形になって、値が一致する（和の公式の考え方）。
よって、[N,N-1,..,1]を足せば良い。

B. Numbers Box

気づき

マイナス記号を自由に移動できる

負 $\times$ 負は正。負 $\times$ 正は負になる。
負 $\times$ 正=負より、一つのマイナス記号は、正の値と掛けることで連鎖的に移動することができる。
また負 $\times$ 負=正より、一つのマイナスが移動できる範囲は増えていく。
結局、
初期状態で負数の個数が偶数ならすべての負数に対して、負 $\times$ 負の操作ができるので、全て正になることができる。
奇数なら、負数が一つ残る。
このとき、残る一つの負数は絶対値でみてもっとも小さいものにするのが得（存在する任意の数字を最後に残る負数にすることができる）。
また「0」が一つでもあれば負の値を0にすることができる。（0の位置がどこであっても、その隣に負数を移動することができるので常にこの操作は可能）

以上から、

初期状態で負数の個数が偶数 -> 絶対値の和
初期状態で負数の個数が奇数かつ 0を含む -> 絶対値の大きい方から $N-1$ 個の絶対値の和
初期状態で負数の個数が奇数かつ 0を含まない -> 絶対値の大きい方から $N-1$ 個の絶対値の和 - 絶対値順での最小値

C. Knapsack

まず一つで $\lceil \frac{W}{2} \rceil$ 以上W以下の値があれば可能である。
なかった場合、 $\lceil \frac{W}{2} \rceil$ 未満の値だけ足していくことで判別できる。

$m$ 個足したとき、和sは $\lceil \frac{W}{2} \rceil$ 未満（ $\because \lceil \frac{W}{2} \rceil$ 以上にならその時点で可能とわかるから）
$m+1$ 個目を足したとき、sが $\lceil \frac{W}{2} \rceil$ 以上になったら、和sはW以下である（ $\because$ m+1個目の値は $\lceil \frac{W}{2} \rceil$ 未満だから）
以上で判別可能。

D. Catching Cheaters

DPの遷移や状態をどうすればいいかに囚われすぎた。
気づき

一文字進めたときのスコアの変化（差分）を計算できる
順番に見ていって、S(C,D)がマイナスになったら、スコアを0にしてそこを始点に再開したほうが得

どういうことか。
CとDの文字列を伸ばしていってS(C,D)がマイナスになったとする。さらに伸ばしていけばプラスに転じる可能性はあるけど、その場合、マイナスになった場所を始点にしたほうが明らかにスコアは良くなることに気づく。
（ $マイナス+A < 0 + A$ ( $A > 0$ ) は自明）
あとはLCSを求めるDPとほぼ同じ形で解ける。

dp[i][j] = aのi文字目、bのj文字目までみたときの、S(C,D)の最大値として、遷移はlcsと同じようにしながらスコアを更新する。
DP更新時にlcsが1増えるとき（a[i]==b[j])、スコアの増加分は、 $4 \times 1 - |1| - |1|$ なのでトータルで+2。
lcsが増えないとき（a[i]!=b[j]のときiを一つすすめるか、jを一つすすめるかなので） $0 - |0| -|1|$ または $0 - |1| -|0|$ なのでトータル-1。