進捗
408問 → 444問
歩きながらiPadで解けそうな問題を探し、電車移動時間はノートで問題を考える。
朝昼夜ひたすら問題を考え実装する。久しぶりで楽しくなってきたのか、わりと頭おかしい生活をしていた。
- 4/15 [641] [474] [530] [605]
- 4/16 [379] [592] [238] [350]
- 4/17 [341] [628] [382]
- 4/18 [634] [655] [635]
- 4/19 [596] [540] [624] [647]
- 4/20 [252] [600] [565] [302] [548] [602] [520] [543] [619] [607] [480] [666] [396] [616]
- 4/21 [280] [464] [283] [393]
感想、勉強したことなど
・pythonの二分探索はbisect_left, right。
・階乗の逆数のメモを生成するときは、個別に逆数を計算するのではなく、$\frac{1}{(n-1)!} = n\cdot\frac{1}{n!}$を利用して後ろから埋めていけばよい。昔経験あった気もするけれど忘れていて再発見。$\log$倍も当然、無視していると遅くなる。
・$\pmod{10^9+7}$で行列の積を計算するとき、そのままnumpyの行列の積を呼ぶと、int64型では桁あふれする。要注意。
・マルコフ連鎖の極限を求める場合。行列を書いて何回もかけていって収束させる実装がお手軽だが、2点間の遷移に時間がかかるような場合には連立方程式を作ってしまって解く方が速度も計算精度としても良い。
・疎行列の扱い（scipy.sparse）に慣れる。とにかく状態を記述して行列を作るみたいなのにはなれてきたかも。
・[596] $O(10^{16})$は普通にやると絶対終わらない。と分かっていたはずなのに、定数倍だけ詰めたバージョンを一度そのまま実装してしまうｗ そういえば…美しい定理で知っているやつなのに反応できなかった。検索で割とすぐ見つけられると思います。
・[252] 5年以上前に取り組んでいたときは、200番台が埋められず。プロットしながら丁寧に実装できていい感じ。
・[666] Recentの速解きに参加。30分で9位。成り立つべき式を考えて、あとは自然に。問題文を読むのが大変…。上位速いなぁ。
