進捗
384問 → 408問
2012年頃に300問ほど、基本的にはC++で解いていました。
久しぶりに再開。pythonを学んでからは初めてです。
- 4/8 [659] [650]
- 4/9 [622] [458] [228] [601] [475]
- 4/10 [349] [630]
- 4/11 [613] [451] [618] [511]
- 4/12 [270]
- 4/13 [643] [537] [440] [340] [552] [625] [609]
- 4/14 [282] [612] [455]
- 復習のため解き直し：[1～50] [73] [193]
感想、勉強したことなど
・jupyterに数式書きながら解けるのが新鮮で良い。
・pythonの実行速度の壁に直面する。cythonによる高速化を試す。numbaによる高速化を試す。ボトルネック部分だけ関数として切り出して高速化する感じで。勉強したことはあったがなかなか実践の機会がなかったので、良い練習になる。
・numbaの方がお手軽で使用感が良いように感じた。当分これで。forumでもたまにそういうソースコードがあるので、参考にさせてもらう。
・行列の積$AB$の計算量は普通には$O(n^3)$。一方巡回行列の積は$O(n^2)$。そもそも行列にして$n^2$個の数を持ってる時点で無駄。$n$元で書いて計算規則を整理すれば自然に$O(n^2)$になる。行列にすればいいってもんじゃない。$\mathbb{Z}/n\mathbb{Z}$の群環の演算とも言えるか。
・凸包の計算を実装。一応経験はあった気がするけれど久しぶり。
・sublinear-algorithm、Mobiusの反転公式など、過去問のForum等で復習。
Problem 073の解説pdfも非常によく出来ていて役に立つ。
・[282] あらゆる可能性を想定して、半日がかりで一般に解くための長いコードを書いたが、結果的には実は簡単な問題だった。確かに。
・[537] 解説pdfがよくまとまっていた。熟読。
