ICPC-F そもそも論

2つアルゴリズムを考えて、片方を実装してみて思ったが、この問題で重要なのはアルゴリズムではないのではなかろうか。いくら問題が難しいとはいえ、自分が挙げた2つの方法や、他の人が提唱している方法のいずれかはMakegumiやclax、kitsune-などの上位選手陣は思いついて実装しているはずだ。それなのに通らない(というか誰もFは通過していないという噂も…)ということはそれが根本の問題ではない気がする。

では何が重要なポイントなのか、と考えると、ズバリ有効桁数だと思う。double型はCもC++もJavaも15桁ちょいの精度がある。ここで、問題で要求されているθの精度は10-10。…「15桁あるならイージャン」と思った人は甘い。精度を求められているのはθだが、そのθを求めるために比較すべき値は影の長さなのだ。ということはθが10-11の誤差で動く時の影の長さが同程度の精度を保証しているか…と言われればそんなことは無い気がする。実際実験的には足りてない。だから8〜9桁目から間違った値になる。

ということはどうすればこの問題を回避できるのか…と行きつけば後は簡単、doubleを全部long doubleに置き換えるだけ。ついでに sin() や cos() などの標準関数も sinl() や cosl() に、定数も 0.0 や 1.0e-11 から 0.0L や 1.0e-11L に書き換える。これで(最大値に非常に近い局所解が無ければ)何とか通るんじゃなかろうか。

追記

サンプルインプットの1個目で実験してみた。



2.55359005004223704780119794681   // 出力

0.982793723247340428569876255167  // 出力

f(0.982793723247329054082399579784)=5.60555127546398929311922126747 // 計算結果の影の長さ

f(0.982793723247340428569876255167)=5.60555127546398929311922126724 // サンプル表示で計った影の長さ
見ての通り、求めるべきθでは10-14程度しか違わない(ような設定にしている)のに影の長さは10-28程しか違わない。O(dθ2)で効くんだろうか。