JAG Contest 2016 Domestic 参加記 (C, Eレビュー)
kenkooooさん、roitiさんとチームshinsotsuで参加。会場を提供してくださったroitiさんに感謝いたします。
結果：CとEを担当して総合15位。Eはroitiさんの考えた解法を自分が実装した形になり、チーム戦っぽいことができてよかったです。幾何は基本的なライブラリがある程度ないとVerifyだけで時間を取られてしまうので、今回ACできたコードはライブラリに入れようと思います。
C問題
jag2016-domestic.contest.atcoder.jp
解法： 構文解析+DFS。ノードを作って二分木のデータ構造を構築してしまう方法もあるが、DFSをやりながら対応する頂点をマージし、stringを再構築する方法を思いつき、楽そうということもあって途中で方針転換した。
コメント：サンプルが仰々しいせいか、考えを整理するのに時間がかかってしまった。stringそれぞれの処理を愚直に書いてしまったが、プロコンだから許してください
E問題
jag2016-domestic.contest.atcoder.jp
解法： 幾何。最も多くの有権者がX氏を見ることのできる領域の境界上を考えると、各有権者がどこかの障害物の頂点をみて、かつ視線がその障害物によって妨げられない場合のときを考えればよい( * )。各有権者が各障害物に視界を遮られない領域の境界は2本の直線で表現できる(**)。
ここで、有権者A, Bがいて、先ほどの2本の直線をすべての障害物に対して描いたとする。下の図でいうと、赤い4本の直線、青い4本の直線のことである。ここで赤い直線と青い直線の交点(個)を作ることができる(平行の場合は交点がないのでさらに少ない)。極端な話をいうと、( * )の考察から、この交点にX氏がいると仮定してもよい。各交点に対し最高何人から見えるかチェックすればよい(***)。最後にそのmaxを取る。
(**)の計算 有権者からある多角形の障害物のすべての頂点に直線を引き、多角形を貫通しているかどうか調べればよい。計算量は
2人の有権者の組ごとに交点を計算する 直線と直線の交点の計算。これが意外と書くのが大変。計算量は
(***)の計算 各交点から各有権者に線分を引き、ある多角形を貫通しているかどうかを調べればよい。計算量は
コメント：すべて一から実装したのもあり、バグを各所に生んでしまってまるまる2時間かかってしまった。mainの中身は20分程度で実装できたが、結局直線の多角形貫通判定、直線同士の交点導出のデバッグで時間を取られた。直線同士の交点を計算するだけとはいえ、甘く見ては痛い目を見る。誤差死は今回はが小さいので気にしなくてもよいと思われる。
総評：
Team shinsotsu on Sushi pic.twitter.com/CV4a7no06s
— ctyl (@ctyl_0) 2016年4月24日
