問題概要
正整数 $N$ が与えられる．$N$ に対し，以下の一連の操作を繰り返し行うことを考える．
- 以下の条件を満たす整数 $z$ を選ぶ
- ある素数 $p$ と正整数 $e$ で $p^e$ と書ける
- $z \mid N$ である（$z$ は $N$ を割り切る）
- 過去に $z$ として選んだことがない
- $N \leftarrow \frac N z$
最大で何回操作を行えるか？
制約
- $1 \leq N \leq 10^{ 12 }$
AtCoder Beginner Contest 169, B : Multiplication 2
問題概要
$N$ 項からなる整数列 $\{ A_i \}$ が与えられる．$\prod A$ を求めよ．ただし，値が $10^{ 18 }$ を超える場合は，代わりに $-1$ を出力せよ．
制約
- $2 \leq N \leq 10^5$
- $0 \leq A_i \leq 10^{ 18 }$
浮動小数点数の誤差に怯えながらも比較をしたい場合がある話
はじめに
最近出題された某問題の影響で，浮動小数点数の誤差について注目が集まっています．さて，あの問題では入力を受け取っただけ・乗算しただけで誤差が出るという話でしたが，幾何問題など，更に比較などの演算も行いたい場合があります．しかしながらもう知られているように，何も考えずに書くと誤差で壊れます．そこで今回は，誤差を考慮しながら等値比較・大小比較を行う際のイディオムについて書いてみます．
なお，そもそも論としては整数演算だけでやれるならその方が安全です．後述の $\epsilon$ の値を変えるだけで通ったり通らなかったりすることがあるので……．
準備
誤差を考慮しての比較ではよく EPS という名前の極小の定数（$10^{-8}$ とか $10^{ -12 }$ とか）を定義しておいてこれを足したり引いたりすることで「許容誤差」のようなものを実現します．EPS は epsilon から来ているようなので，本文中では $\epsilon$ と書きます．
等値比較
2 つの実数 $a, b$ が等しいかどうかを判定したいとします．これを $a = b$ とそのまま書いてしまうと数学的には等しいはずの値であっても蓄積した誤差によって等号が成り立たないかもしれません．等値比較では，「等しい」と言う代わりに「差が十分小さい」と言い換えることで「大体同じなら等しい」とします．つまり，$| a - b | < \epsilon$ かどうかを見ます．
abs( a - b ) < EPS
大小比較
2 つの実数 $a, b$ の大小関係を知りたいとします．こちらも，$a \leq b$ や $a < b$ のようにそのまま書いてしまうと壊れる可能性があります．こちらは適切な方に $\epsilon$ を足し引きして調整します．
$\leq$ を判定する場合は，値が十分近いときに誤差のせいで順序が入れ替わってしまっても $\epsilon$ 分余裕をもたせる気持ちで $a - \epsilon \leq b$ か $a \leq b + \epsilon$ とします．これで，数学的には $a \leq b$ だけど浮動小数点数の値としては $a > b$ のときでも $b < a \leq b + \epsilon$ ぐらいになってくれるといい感じの $\epsilon$ なら上手くいきます．
a - EPS <= b a <= b + EPS
$<$ を判定する場合は，$\epsilon$ だけ近づけても $<$ が成り立つ，といった気持ちで $\epsilon$ をつけると $\leq$ のときと符号が逆になって，$a + \epsilon < b$ や $a < b - \epsilon$ となります．
a + EPS < b a < b - EPS
コードの上で < と <= を書き分ける必要はありませんが，わたしは，その方が EPS の付け方が分かりやすいので書き分けています（やりたい演算をまず書いて，後から EPS を書く）．
おわりに
まとめてみたはいいものの，最近使った記憶もあんまり無いような……？
AtCoder Grand Contest 044, B : Joker
問題概要
$N \times N$ のグリッド状の盤面の各セルに人が $1$ 人ずつ，合計 $N^2$ 人いる．人は $1$ から $N^2$ の整数で，左上から row-oriented で番号付けされている．
入力でサイズ $N^2$ の順列 $P$ が与えられ，この順序に従って人々は一人ずつ盤面の外に出ていく．このとき，他の人がいるセルを通った回数分のコストがかかる．人々がコストを最小化して移動したときのコストを求めよ．
制約
- $2 \leq N \leq 500$
- $1 \leq P_i \leq N^2$
