508.1

時間はあったけれど、英語読めなかった...。

250

見てない。

500

整数配列が与えられる。同じ長さの整数配列で、同じ位置には元の整数配列以下の値が入るような整数配列を考え、それが、すべての要素の和が論理和に等しくなるようなものはいくつあるか答えよ、という問題。

加算時にキャリーが出ないようにしなくてはならないので、各ビットは整数配列の要素の高々一つでしか立たない。また、ビットを立てて良いかどうかは、元の整数配列で1が立っているか、それより上位で1が立っていて、そこで既に同じビットを立てていないか。また、上位ビットを使わずに残せば、下位の任意のビットを立てても、元の値を超えない。

つまり上位ビットから順に、どの位置で使用するかを決めながら、上位ビットを使わなかったかどうかを覚えておきつつDPしていけば良い。

1000

凸包が与えられ、内部の点が与えられる。凸包の辺上に無数の点があるとみなし、内部の点のいずれかと対応させ、かつ、内部の点はいずれも同じ数の辺上の点と対応しているようにするとき、一番距離の長い対応の長さの最小値を答えよ、という問題。

求める長さをバイナリサーチすると、各点からその長さで円を描き、凸包の辺を内部外部に分割する。そうすると辺の数の2倍だけ各点について考慮すべき点が生まれ、それぞれがどの内部の点と結合できるかが分かる。結合可能性ごとにクラスタリングすると、2^Nグループに分割でき、それぞれの長さが分かる。それぞれのグループが各点に対してどれだけの結合を行うかをマッチングで求めれば良く、そのようなマッチングが存在する最小の長さを答えれば良い。