586.1

やれることはやったのでまぁ仕方ないという気分。(いつまでもそのままじゃダメだけども。)

250

折れ線グラフが与えられるので、x軸に平行な直線と交わる回数の最大値を答えよ、という問題。

当然、折れ線の一部がx軸に平行だったら無限に交わる。それ以外のケースを考える。基本的には登場するy座標全部と、その近傍を調べてやればおしまい。

500

見てない。

1000

大文字のアルファベットからなる文字列について、同一の文字が複数回登場する場合に、その両端の座標の差分がコストとして計上される。すべての文字についてコストを合計した値が文字列全体のコストとなる。文字列の長さが与えられるので、一番コストが小さい文字列のいずれかを任意に選ぶことができるものとする。このとき、文字列の長さが複数与えられるので、そのような文字列を結合した結果の文字列のコストの最小値を答えよ、という問題。

多分全部の文字について、1回ずつ登場させて、最後に残った文字数だけ特定の文字を繰り返すというのが文字の選び方としては最小のはず。後は同じ文字がどこに並ぶかとか、を考えてやる。

貪欲に割り当ててくのはダメみたい。