進捗
473問 → 514問
ゴールデンウィーク。ちょうど今一番はまっているゲームということで、連休の大部分を注ぐ覚悟は出来ていた。目標の500問突破。ここから先はどこまで進めるか…。そろそろ詰みが近いような気もする。
- 4/29 [610] [517] [367] [621] [456] [497] [632]
- 4/30 [496] [261] [390] [296] [428]
- 5/01 [468] [544] [633] [557] [639]
- 5/02 [420] [445] [446] [556] [582] [580] [432] [255]
- 5/03 [385] [368] [575] [473] [269] [241]
- 5/04 [501] [521] [366] [411]
- 5/05 [668] [295] [662] [431] [476] [569]
感想、勉強したことなど
・無限降下法による整数解の生成。初等的なのに、簡単に解けそうにないものが倒せるのでやっぱり不思議ですごい。手段としては知っているのに思いつくのにかなり時間がかかった。
・素数を数える関数$\pi(n)$を初めて自作。ProjectEulerでは、素数のリストが必要な場合でもたいていは$10^8$程度まで計算できれば足りるように設計されているように思います。一方で、素数の個数や和などについては（素数のリストを作らない方針で求めることで）より大きな値まで計算することを要求されることがあるようです。
いかにもそういう要求の問題をまとめて考えながら、自分で実装。「素数」に制約がついたり「個数」じゃないものを計算させられる場合も含めてある程度対応できるように理解を深める。
・例えば$x$を小数点以下3桁に丸めて出力する場合：
なるほどー、そりゃそうだ。当然指定フォーマットではない形で提出すると不正解を食らいます。
計算に誤りがあることをまず疑ったため、しばらくハマる。
・$\frac{a_1}{n}+\frac{a_2}{n}+\cdots$というような小数の計算をする場合。$(a_1+a_2+\cdots)/n$と除算を1回に済ませた方が計算精度が安定する（パフォーマンスも当然定数倍良い）。
・傾き順に点をソートする場合。そのまま割り算をする、あるいはarctan2の類を使うと計算誤差が気になる（epsilonを設定してやればよいが、有理数として持った方が安心を覚える）。しかし、どうやらFraction型のソートが異常に遅いことが分かった。$a/b$を計算するときに、いったん$\mathrm{gcd}(a,b)$で割って既約分数になおしてから小数にすることで、同一の有理数を同一として扱えた（許容誤差epsilonときちんと向き合う方が適切な処置な気もする）。
・[428] 綺麗な問題、かつ難問。幾何が終わって問題を言い換えたあともそれなりに難しい。幾何パートは、反転の応用として有名な定理の周辺。Eulerで見るとはね。反転の応用っていくつかあるけれど、反転を使う以外の方法では全然証明できなさそうに見える定理としては真っ先にこれが思い浮かびます。
・[468] 自分で考えて、データ構造の応用を作ったけれど、知られている手法だったぽい。6分ほどかかってしまう。Forumを見ても、1分を切れている人は結構少ないようだった。
・[668] 8位。易しい問題だった。必要な実装をちょうど当日に経験していた。人によってはライブラリとして持っていると思われる。一直線な方針だけど、Forumに一応書いたら2桁Kudos貰えた。
