誤差と戦う小手先のテク

この記事は, Competitive Programming （その2） Advent Calendar 2015 の 12/16 の記事として書かれました.

12/15 の記事は iwashi31 さんのゲームAIコンテストのすすめで, 12/17 の記事は Respect2D さんの AtCoderでのコンテスト主催者向けのツール紹介です.

イントロ

競技プログラミングでは, 特に計算幾何の問題を解くときなど, 誤差が襲い掛かってくる場面があります. そのとき, 最も簡単な選択肢は "その問題から逃げる" ことで, 実際その選択が正しい場合もあります. しかし, 時には戦わなければならず, 戦うための道具を知っておくことは重要です.

ということで, 僕が知っている, 誤差との戦うための 競技プログラミングにおける 小手先のテクニックを, いくつか紹介したいと思います.

具体的には,

誤差が辛い問題かの判定や, 誤差が出ると辛い場所を見つけるときの, 自分の基本的な思考経路,
誤差が辛そうなとき, それをどうやって克服するか

の二点について書きました.

相対誤差/絶対誤差などに踏み込んだ話や, "こうすれば絶対大丈夫" とかいう話ではなく, "経験的にこうすると避けられる事が多い" 程度の話です.

何度か戦った経験のある人は大体知っているかもしれませんが, ご容赦下さい.

komiyam さんの記事がよく纏まっているので, そちらも読むとよいと思います.

大前提

まず, long double や __float128 など, 精度の高い型を使うのが最初に考えるべきこと.

特に計算幾何の問題など, 計算時間に余裕がある問題では, これをするデメリットは無いので, 誤差を気にしなくてよいときでも, とりあえずそうしておくべき.

誤差と戦うべきか

もちろん, "てきとーにやってもなんとかなる" 場合は, 誤差をあまり気にせず, てきとーに書いて済ませたい. その為には, "てきとーにやってもなんとかなる" かを判断出来なければならない.

基本的な判断基準は, "最終的な出力にどれだけ影響するか" ということ. イメージは, 出力を, 誤差が出そうな計算の項で微分するような感じ.

例: 極座標

例えば, 出力の座標ベクトル $(x, y)$ を, $(x, y) = (r \cos \theta, r \sin \theta)$ として, $r$ と $\theta$ で管理しているとしよう.

$(x, y)$ を $r$ で微分すると $(\cos \theta, \sin \theta)$ だから, $r$ が $\epsilon$ 変わると $(x, y)$ は大体 $\epsilon (\cos \theta, \sin \theta)$ だけ変わる. $-1 \le \cos \theta, \sin \theta \le 1$ だから, $r$ への誤差は, 出力に同じくらいのオーダーでしか影響しないことが解る.

一方で, $(x, y)$ を $\theta$ で微分すると $(-r \sin \theta, r \cos \theta)$ だから, $\theta$ が $\epsilon$ 変わると, $(x, y)$ は大体 $\epsilon (-r \sin \theta, r \cos \theta)$ だけ変わる. 従って, $\theta$ への誤差は, 出力に $r$ 倍くらいの影響を与える.

例えば, 角度に $\mathit{EPS}$ くらいの誤差が乗りうる状況(角度を $\mathit{EPS}$ で摂動したなど)では, 座標になおすと $r * \mathit{EPS}$ 程度の誤差になるから, 座標に対して同じ $\mathit{EPS}$ を使う操作はするべきではない.

もちろん, これは絶対誤差の意味で, 相対誤差は同じオーダーになる.

例: 四捨五入

連続から離散にする時には, かなり注意が必要である. 例えば, 出力は整数だが, それを最後まで浮動小数点数で計算している場合を考えよう.

誤差が無く, $x$ が整数を表しているならば, 単なる切り捨て $\floor{x}$ と四捨五入 $\floor{x + 0.5}$ は同じだが, 普通は四捨五入をして出力する.

これらの違いは "不連続点がどこにあるか" にある.

切り捨ては $x$ が整数の場所で不連続であるが, 後者は $x$ が整数 $+ 0.5$ の場所で不連続であり, 不連続な点を, $x$ のとりうる値である整数 $\pm \epsilon$ からずらしている.

これにより, 整数 $\pm \epsilon$ における微係数を $0$ にできる.

今回は, $x$ の取りうる値が整数 $\pm \epsilon$ のような所であることを利用できたが, 例えば "$x$ に対し, $\floor{\tan x}$ を答えよ" のような状況では, どうしようもない.

例: min と argmin

三分探索をするとき, "$f(x)$ の最小値は求めやすいが, 最小値を与える $x$ を求めるのは誤差が辛い" ことが多いというのを知っている人は多いと思う.

これは, $f(x)$ の最小値を与える $x$ での微係数が $0$ だと, その付近ではほぼ同じ値を取るため, $f$ を求めるときの誤差に影響を受けやすいからである.

似たように, "$p \in S$ を選び, $f(p)$ を最小にする" 系の問題で, 最小値を求めるのはよいが, 最小値を与える $p \in S$ を求めるのは誤差が辛いことがある.

例: 一致判定, 大小比較

$|x - y| < \epsilon$ で一致判定をしたり, $x < y - \epsilon$ と $x > y + \epsilon$ で大小比較をすることが, 非常によくある.

これはもちろん, "あまりに近い数は無い" 場合や, "非常に近い場合はどんな結果を返してもよい" 場合にしか使えない.

ちなみに, よくこれで比較するのを数カ所忘れたりするが, それを防止するのに, 次のような関数を定義し, いつもこれを利用して比較するようにするとよい.

1
2
3
4
5
6
7
8
9
10
11
12
using R = long double;
constexpr R EPS = 1E-11;

// r の(誤差付きの)符号に従って, -1, 0, 1 を返す.
int sgn(const R& r){ return (r > EPS) - (r < -EPS); }
// a, b の(誤差付きの)大小比較の結果に従って, -1, 0, 1 を返す.
int sgn(const R& a, const R &b){ return sgn(a - b); }

// a > 0 は sgn(a) > 0
// a < b は sgn(a, b) < 0
// a >= b は sgn(a, b) >= 0
// のように書く.

誤差と戦う道具

基本的な道具とその特徴を, 表に纏めた. それぞれ, 表そうとするもの(例えば実数全体 $\mathbb{R}$ )があり, それを妥協(有限精度)している.

道具	何を表すか	妥協したところ	出来ない/難しいこと
浮動小数点数	実数	精度	一致判定, 大小比較
整数型	整数	オーバーフロー	除算, 他
有理数型	有理数	分母子のオーバーフロー	平方根, 三角関数, 他
$\bmod p$	$\mathbb{F}_p$	なし	大小比較, 平方根, 三角関数, 他

だいたい, このうち一つを使うか, 浮動小数点数ともう一つを組み合わせて使うことが多い.

組み合わせて使う場合も,

クリティカルな場所だけ他の型を使う,
同じことを複数の型で計算する

の二通りがある.

また, なるべく, これらの道具に置き換えられるような計算方針でライブラリを書くとよい.

浮動小数点数

これで済むならそれでよい. 一致判定や大小比較は, 近すぎる数があると難しい.

eps をてきとーに調節して誤魔化すのは常套手段.

整数

入力が整数で, 途中計算で割り算や平方根などを使わない上に, 途中結果が大き過ぎない場合は, int, long long や __int128 などの整数型を使うことを検討する.

平方根を扱う代わりに自乗を持っておくテクニック (例えば, $\sqrt{a^2 + b^2}$ と $c$ の比較を $a^2 + b^2$ と $c^2$ の比較で行う) などで, 整数の演算に還元することもよくある.

有理数

整数の場合に加えて割り算を扱える. これにより, 点と直線の距離や, 直線同士の交点などを扱うことができる.

大小比較でオーバーフローしないように注意. ( ここを参照)

$\bmod p$

大きい素数 $p$ を取り, 全て $p$ で割った余りで計算する. $p$ で割り切れない数での割り算までなら出来る.

オーバーフローせずに, (差が $p$ で割りきれてしまう場合を除いて)一致判定ができるのが重要. 浮動小数点数と同時に同じ計算を $\bmod p$ で行い, ハッシュのようにして使うことが多い.

複数の $p$ を用いることで, "実際は異なるが同じと判定してしまう" 確率を下げられる. (中国式剰余定理)

有理数より実装が楽なので, 大小比較が無いなら, こちらを選択することも考えるべき.

例えば, (それぞれ格子点二点ずつで指定された)三直線が一点で交わるかを判定することを考えよう.

一番簡単に思いつくのは, 二直線の交点を取り, それがもう一本の直線の上にあるかを判定する方法や, 異なるペアで交点をとり, それらが一致するかを判定する方法だろう. しかし, これを実数で計算するのは, 誤差が怖い.

このようなときは, 入力の $\bmod p$ を取り, 交点の座標を $\bmod p$ で計算し, 直線上かの判定や点の一致判定も $\bmod p$ で行なってしまえばよい.

例: Shortest Bridge

問題文はこちら.

ネタバレを含むので折りたたみ

この問題は, 大雑把にいうと二つのパートにわかれる.

橋の長さが最も短くなるような橋の候補を列挙する.
上で列挙した各橋について, 始点から橋の西側, 橋の東側から終点の最短距離をそれぞれ求め, その和の最小値を求める.

前半パートは, "橋の長さの最小値" ではなく, "橋の長さが最小となるような橋を列挙せよ" というタイプである. ここで誤差が出ると, "橋の長さが最も短い" という条件を満たさない候補が紛れ込む.

橋の長さが近いからといって, 始点から橋の西側, 橋の東側から終点の最短距離の和が近いとは限らないため, 前半パートの誤差は答えに大きな影響を及ぼす可能性があり, 前半パートで誤差を出さないことは重要である.

一方, 後半パートでは, "全体の道のりが最小となる橋の位置を求めよ" ではなく "全体の道のりの最小値を求めよ" なので, ここでの誤差が答えに及ぼす影響は大きくならない. (出た誤差と同程度.)

実は, この問題では long double と小さめの eps を使うと通る(ことがある)が, 不安な場合は, 前半パートだけ, 誤差と戦えばよい.

前半パートでは, 点と点, 点と直線の距離を列挙し, その比較をすることになる. これらは自乗すると有理数(入力の加減乗除のみで表せる)だから, 自乗したものを比較することにする.

今回の場合, "大小比較" が出来なければならず, 除算もあるから, 有理数で扱うとよい.

少し計算すればわかるが, これは分母子を 64 bit の整数型で表した有理数型で扱える範囲の数になる.

おわり

12/15 の記事は iwashi31 さんのゲームAIコンテストのすすめで, 12/17 の記事は Respect2D さんの AtCoderでのコンテスト主催者向けのツール紹介です.