Secrets in Shadows
風呂に入ってぼーっと問題Fについて考えていたら、なんとなくいけそうな方法を思いついたので、実装してみた。
- 得たもの
- Sample Inputに対して正答を出すC++コード
- 失ったもの
- 休日の貴重な時間を3〜4時間ほど
…これ、時間内に解くとか無理。以下、思いついたアルゴリズムについて書きます。
方法をちゃんと説明しようとすると数式のオンパレードになるので、方針だけ書く。
太陽の方角θに対する影の幅をS(θ)とすると、S(θ)は連続。求めたいのはS(θ)が最大・最小になるときのθの値だから、S(θ)が極値を取るようなθの候補、つまりdS/dθ=0になるようなθを列挙して、全てに対して影の幅を計算して比較してやればいい。問題はどうやってdS/dθ=0を解くか。
まず、柱1を座標の原点に持ってきて、太陽はY=∞におく。すると、元々太陽が周りを回っていたのは、太陽が固定で柱2〜nを原点周りで回転させるのと同じになる。
すると、柱が作る影は、柱をX軸上に射影した範囲の集合として素直にイメージできるようになる。こんな感じ。
|-----| |---|=|---| |-----|
1 2 3 4
イコールになっている部分は二つの範囲が重なっているところだと思うべし。Sは、これらの範囲を併合したものの和になる。
上の図の状態から太陽をちょっと動かす、つまりθをθ+dθにすると、おのおのの範囲は左右に移動する。このときのSの微小変化dSは、柱iの影のX座標をXiとすると、dX3 - dX2で表される。両辺をdθで割ると、dS/dθ = dX3/dθ - dX2/dθ。つまり、このような影の位置関係のとき、Sが極値を取るとすれば、必ずdX3/dθ - dX2/dθ = 0が成り立つことになる。Xiはsinθとcosθの線形式でかけるので、方程式は同じくsinθとcosθの線型方程式。だから、三角関数の合成公式を使えば解ける。というか、Asinθ + Bcosθ = 0の形になるのでatanだけで十分。
さて、影の位置関係が決まってしまえばとりあえずθが一意に決まることは分かった。なので、あとは、起こりうる影の配置を全て調べてやればいい。これには、範囲の端点同士が一致するような 0 = θ0 < θ1 < θ2 < ... < θm = π を列挙して、各角度範囲の真ん中あたりを取って配置を調べてやればOK。そういうθはどういうものかというと、ちょっと考えると、柱同士の共通接線の角度になることがわかる。
アルゴリズムをまとめると、
- 全柱の共通接線を求めて、その角度を集める。
- 角度をソート。
- 各角度区間の間の角度をとって、そこにおける柱の影の配置を調べる。
- 配置から三角関数の方程式を作って、それを解いて、候補となるθを計算する。
- 各θについて、あらためて範囲の長さを計算。最大と最小を調べる。
という感じ。
大体の方針としては合ってると思うんだけど... 数学は苦手なので、何かつっこみなどあればコメントをくれると嬉しいです。
