585.1

異常に頭悪いことが分かった。(分かってた。)

250

完全二分木が与えられる。同じ頂点を複数回通らないように、二頂点間を結ぶパスで全体をカバーしたい。最小でいくつのパスが必要か答えよ、という問題。

今の根が終端なパスがあるかないかで分岐して、木の大きさに応じたパス数をDPしていく。根が終端なのが二個組み合わされば、一回り大きい根が終端じゃないヤツができたりとか、そういうのを書き下していくだけ。

500

ある数字がいくつかずつある。これらを並べ替えて、狭義単調増加列に分割したときの個数がK個になるようなものを作りたい。何通り作れるか答えよ、という問題。

今何個の狭義単調増加列があるか覚えておけば、その最後にしか追加できないので、それ以外の場所に追加したら狭義単調増加列が増える。という風になるので、小さい数字から順に突っ込んでいけばおしまい。

1000

とある正方形の内部にある格子点がいくつか与えられる。それらをすべて囲むような、各頂点が元の正方形の辺上の格子点にあるような三角形は何通りあるか答えよ、という問題。

めんどくさそうな感じがしてやめた。