ABC130

所感

ABCD: 簡単 E: DP? 何を状態としてもたせればいいのかわからなかった F: わからん。

解説のようなもの

A

全探索すれば間に合うので割愛

B

同上

C

exampleでテストしてみると、中心を通れば綺麗に半分になることがわかる
よって指定された点が長方形の中心ならば無限に線を引けて、そうでなければ1本のみ引ける
個人的には200点問題だと思う。ココらへんからいつも以上に早解きが重要になると感じる

D

累積和でsumを取っておくだけだと始点と終点を指定しなければいけないのでO(N²)だけ必要になるが、始点を決めた上で最短の終点が決まればそれより長いものはすべて条件を満たすのでO(1)でできる。この最短の終点は二分探索でできるのでO(logN)でできる。よって始点ぎめO(N)*終点ぎめO(logN)で間に合う

（以下通せてない）

E

N<2*10³ってO(N²)間に合うし、O(NM)が間に合う。ある写像i→jにおいて、i-1番目の文字までの場合の数に依存している（その中身には興味がない）ためにDPでできそうってところまでわかって、遷移図が書けなかった

F

わからん。1次元にしか動けないので、固定値があることはわかった。そのうえで時間ごとの関数を定義してmax、minになる点が変わるごとに探索？