Problem D the Phantom 解説:菅原 悠 概要 鏡を使って、お化けを驚かせよう！ 概要 鏡を二枚使って、お化けをより驚かせよう！ 概要 平らな鏡を二枚置いたとき、見える像の数を 答えなさい。 解法 像の現れる場所を計算 • ２次元図形での反射の計算方法 • 角度を使ってがんばる • 射影ベクトルでがんばる • 複素平面の複素共役を取る 解法 像と初期位置とを結ぶ直線上に、鏡が正しい 順で配置されることを確認 • 鏡の中の鏡の位置を計算 • 交差判定 解法 鏡は二枚 • 反射後の世界にはもう一方の鏡しかいない 反射は鏡A→B→A→B→A→…だけ 鏡の中にはもう一方の鏡しかいない • 遮蔽ははじめの一枚だけしかない 鏡 虚像 鏡 おばけ 例 #17 鏡 虚像 例 #18 見えない 見えないからといって、 探索を打ち切ってはい けない. 像 例 #19 同じ配置でも 立ち位置しだいで 見える像の数は大 きく異なります 解法 1.Ad hoc に n回見えなかったら打ち切り • 危険な例:Test caseに n=1000で 突破できないものが存在(後述) 2.図形的に見えないことが確定したら 打ち切り 系の考察 α 複素平面で考える。 0 • M1(z) = conj(z) • M2(z) = α conj(z/α) = α/conj(α) conj(z) 1 M1・M2(z) = α/conj(α) z → zを2arg(α)回転 鏡の交点を中心に回転した位置に像が出る 系の考察(cont) 反射を先に進むと一方向に曲がっていく →視線が途中の像を通らなくなったら打切 : もう戻ってくることはないので →視線がもう一方の鏡で遮蔽されたら打切 例 #15 境界例 ここに像 例 #116 以下ランダムデータ 像が 出ず 見えないからといって 打ち切る勿れ 例 #78 二枚の鏡の外側から襲撃 像 像 像 像 例 #56 この辺に見えなかった像が1000以上も!! 例 #34 手入力の難関例 難関例の作り方 初期配置 難関例の作り方 拡大 傾き(21, 20) 傾き(20, 19) 難関例の結果 ここに像が15個 出典 オリジナル 原題 : Mirrors against each other 原作 : 三廻部 改題、入力生成 : 菅原 被害者 : 野田、稲葉 可視化 : gnuplot 4.0 結果 1st submitted : kitsune たぶん見えなくなったらあきらめていた Accepted / submit : 0/2
© Copyright 2024 ExpyDoc
