278.1

これの1000もテンプレ的な問題のような気がする。SRMでは同じ解き方が連続する傾向にある気がする。

250

凸包が入力として与えられるので、角を一つずつ落としていくとき、最後に残る三角形の面積の最大値を答えよ、という問題。

回りくどく書いてあるけれど、結局は凸包の3点を選んでできる三角形の面積の最大値を答えるだけ。外積を使って計算すれば良い。整数溢れは起きないので、何も気にする必要はなかった。

450

矩形がN個与えられるので、どの矩形にも属さないが、上下左右に矩形に属する点が存在するかどうかを答えよ、という問題。

矩形の数*2がそれぞれの座標に現れるので、その領域分割をして、各領域が矩形に属するかどうか判定する。後は上下左右に矩形に属するが、自分が属さない領域があるかどうかを判定するだけ。O(N^3)で解ける。

1000

N人がN個の異なる目的地に向かって移動する。全員が目的地に到達するまでにかかる最小の時間を答えよ、という問題。

それぞれが各目的地に到達するまでにかかる時間を求め、ソートする。その時間以内にある人がある目的地に到達可能ならば、枝があり、そうでなければない、というような二部グラフを作成して、そのマッチングを行う。完全マッチングがあれば、その時間での到達が可能。そうでなければ不可能なので時間を進める。

グラフのマッチングはグラフを拡大しながらやっても状態が保存できるので、下から組んでいく方が良い。(バイナリサーチしてグラフを作り、その後で一からマッチングというのでもいいけれど、問題サイズがもう少し大きくなったら間に合わなくなる。)

マッチングに使うbfsのルーチンをちょっと間違えたせいで、デバッグが面倒だった。バックトラックの関係でグラフにアクセスするインデックスが逆転するのに注意が必要。一度ライブラリ化したいのだけれど...。