332.1

やった身に覚えがまったくない釣り堀セット。

250

整数配列が与えられるので、高々2個のグループに分け、各グループ内での積の和の最大値を答えよ、という問題。

出来るだけ絶対値の大きい乗算を優先する。2以上と0以下と1にグループ分けして、1は孤立させる。

550

平行な線分が与えられるので、そのうちいくつかを選択して、垂直方向に線分を追加して、一つのループを作成したい。ループは自分との交差をしない。このとき、ループの線分数の最大値を求めよ、という問題。

2^K通り全部試して、ループができるかどうか判定すれば良い。ループができる必要十分条件は、二つの線分の端点が垂直方向に見て同じ座標にあり、それは他の線分を横断せず、最終的にすべての線分が結合される、こと。結合判定はくっつけるときに同一グループにしてやれば良い。(くっつけ方はユニークに決まる。)

950

見てない。後でやる。