問題 1062 †

解説用のパワーポイントが下に添付されているのでそれを参照されたい。 パワーポイントは読めないがＰＤＦなら読めるという人が居たらその旨をＭＬに投げれば誰かがＰＤＦ化してくれるだろう。

問題概説 †

選手がＫ人居て、それぞれ水泳、サイクリング、マラソンの速度が与えられている。 Ｋ人それぞれについて、「水泳、サイクリング、マラソンの距離」を恣意的に設定 することによってその人を恣意的に勝たせることができるかどうかを出力する。

解法 †

水泳とサイクリングとマラソンの比率が問題であるので、 自由度は２つある。比を x: y: 1-x-y と置くと、 1.0 x 1.0 の空間上で各選手の速度が表せる。 速度が全く同じである選手は最初にまとめておく。 全く同じ速度を持たない選手同士に関しては (x,y)空間上のある直線を境に強弱が入れ替わる。

そこで、初期状態として 0<x,y<1, x+y<1 の指し示す 三角形を作り、残りの選手に対して勝てる領域を順次 生成し、(凸多角形を直線でクリップすることになる) 最終的に領域の面積が残れば、その選手を勝たせる 方法があるということになる。