yukicoder contest 346

　Cのみ一完。

コンテストへのリンク

No.1964 sum = length

　解説AC。もっと速い解法があるようですが、それは理解できていません。

　DP[長さ][和]の四乗DPを考えていたが、DP[和 - 長さ]を考えれば三乗で済む。その方針も考えたはずなのに、上手くいかない気がして捨ててしまった。なぜ……。

　これが解けなかったのはまずい。

No.1965 Heavier

　解説AC。

　「良い区間」に関して、推移性が成り立つことに気付く必要があった。

No.1967 Sugoroku Optimization

　自力AC。

　いつも「aとして残りのマス数を選ぶ」のが最適、ということに気付けばあとは期待値DP。累積和で高速化できる。