Beta

良く分からない謎のSRMのようなもの。

250

ある人から見て、友達関係が与えられるのでホップ数を計算しましょう、という問題。

BFSするだけだと思うけれど、文字列ベースなので面倒そう。

550

見てない。

1000

ロボットが壁をのぼる。壁にはつかめる場所がいくつかあり、ロボットは手を4本持っている。少なくとも三つつかんでいないと壁はのぼれない。このときどこまで手が届くか、一番高いy座標を答えよ、という問題。ロボットは半径Rの円形で、その内部の任意の点に手を移動させられる。

取り敢えず地面にいるときに、3点つかめるかどうか調べる。高さRの位置に最初中心があるので、その点をつかんだときに、中心の取り得るx座標の範囲を調べてやれば、つかむ必要のある点集合について、つかめるかどうかが分かる。後は、つかめる3点からBFSする。

BFSについては、もう一点追加した4点について、その4点を含む最小の円の半径がR以下ならば遷移可能で、いらない一点を取り除いた3点について移動できる。4点を含む最小の円は、2点の中心か、3点からなる三角形の外心のいずれかと必ず一致するはず。(最小の円は少なくとも2点以上と接するはず。)

で、つかめる3点がすべて求まるので、後はその状況で、一番中心を上に持って行けばよい。ここで最初にやった3点つかめるかどうかと同じ判定を高さバイナリサーチしてやったら、精度がひどくてダメだった。これを厳密解求める方法をこれから考える...。