461.1

10分くらい遅刻したけど、何も変化がなかった。

300

二色の円盤を交互に並べて、長方形を被覆するのにいくつ必要か答えよ、という問題。

大きいヤツから順番に並べていくだけ。どっちの色を先にするかとか。

500

見てない。

950

長さ固定の柵がいくつか与えられて、それで長方形の3辺を作る。その際、一つだけ柵を任意に切って良い。長方形の面積を最大にするような辺の長さを答えよ、という問題。

取り敢えずどれか一辺は切っていない柵から作らないといけない。長方形の一辺の長さが決まると、残りの辺の長さが決まるから面積が求まるはず。

柵を二つのグループに分けると、片方のグループの組み合わせでできる長さは2^(N/2)通りで、残りのグループも同じくらいできる。前者で作った値が大きくなると、後者の値を小さくしてやれば面積は同じくらいになるので、ソートしておくと常に最適値付近になるものが高速に選べるはず。後は一番いいのを拾うだけ、のはず...。