159.1

SRM

250

N枚のパンを片面ずつ焼ける状況で、M枚のパンを両面焼く。同時に両面焼くことはできない。一面焼く時間が5分の時、全部焼き終わるのは何分後かという問題。


NとMのうち小さい方が実際に焼ける枚数。焼かないといけない枚数は両面なのでM*2枚と考えると、後はそれがなくなるまで焼けばおしまい。

500

整数の配列が与えられて、最長となる単調増加列の長さと、その長さを実現する単調増加列の種類を答えよという問題。


単調増加列の長さは、それぞれの部分配列について計算するDPをすればおしまい。その時に種類も計算すればおしまい。今の500とは比較にならないほど簡単。

1000

二点間の距離の配列が与えられるので、x軸上の正の方向にそれらを満たすような点を配置する。その中で一番小さいものを答えよという問題。


距離のうち大きいものから点数-1個を選択し、それを配置できるかどうかを考える。一番大きい値は右端の点の座標。つまり点数-2個の分だけ、その線分を作れるかどうかを考える。基本的に全体の長さからその線分の長さを引いた長さの線分が残っていればそれを使う。今までに作った辺の長さのうち短い方の辺と組み合わせて残りの部分を作れるなら、1本でそれを作る。(複数本だとそこに点を置かないといけなくなるので、おかしくなる。)ただしこの場合、作れる短い辺の長さをうまく更新しないといけない。


で、全部の点を置けたら、それが正解となるようなパターンがあるかを吟味する。実際には原点と何かしらの点との間に点を置いた場合にうまくいかない気がするので、もう少し吟味しないとダメっぽい。


簡単かと思ったらやっぱり難しかった系。いつかちゃんと解く。