AtCoder で scipy を使って問題を解く
Table of contents
AtCoder で scipy を使って解いた問題をメモ代わりに残しておきます．一部 yukicoder や Library-Checker も含まれています（タイトル詐欺）．
AtCoder に入っている numpy / scipy のバージョンはコードテストに以下を入力して実行することで確認できます．
import numpy as np
import scipy as sp
print(f"numpy {np.version.full_version}")
print(f"scipy {sp.version.full_version}")
出力結果（2020/02/28 時点）
numpy 1.18.2
scipy 1.4.1
グラフアルゴリズム: scipy.sparse.csgraph
使うライブラリ
| アルゴリズム・問題 | Library Checker | 提出 | |
|---|---|---|---|
| connected_components | 強連結成分分解（トポロジカルソート） | 問題 | Link |
| dijkstra | 単一始点最短路 | 問題 | Link |
| floyd_warshall | 全点対最短路 | - | - |
| minimum_spanning_tree | 最小全域木 | - | - |
| maximum_flow | 最大フロー | - | - |
| maximum_bipartite_matching | 二部グラフの最大マッチング | 問題 | Link |
AtCoder 上の問題
| 問題 | 提出 | |
|---|---|---|
| connected_components | Educational DP Contest-G Longest Path | Link |
| dijkstra | ABC035-D トレジャーハント | Link |
| dijkstra | 第一回アルゴリズム実技検定-J 地ならし | Link |
| floyd_warshall | ABC143-E Travel by Car | Link |
| minimum_spanning_tree | 第一回アルゴリズム実技検定-L グラデーション | Link |
| maximum_flow | ABC010-D 浮気予防 | Link |
| maximum_flow | ABC193-F Zebraness | Link |
| maximum_bipartite_matching | ARC092-C 2D Plane 2N Points | Link |
- 要検証事項等
- maximum_flow は特殊なケース（source と sink が連結でない場合など）で ValueError が投げられて RuntimeError になることがあるっぽい？
最適化: scipy.optimize
使うライブラリ
| アルゴリズム・問題 | Library Checker | 提出 | |
|---|---|---|---|
| minimize_scalar | 関数の最小値 | - | - |
| newton | ニュートン法（関数の根） | - | - |
| linprog | 線形計画法 | - | - |
| linear_sum_assignment | 割当問題 | 問題 | Link |
AtCoder 上の問題
| 問題 | 提出 | |
|---|---|---|
| minimize_scalar | ARC054-B ムーアの法則 | Link |
| minimize_scalar | ARC049-B 高橋ノルム君 | Link |
| newton | ABC026-D 高橋君ボール1号 | Link |
| linprog | yukicoder No.453 製薬会社 | Link |
- 要検証事項等
- linprog を用いる試みは他にもあるが，再現しようとしても Wrong Answer が取れなかった
計算幾何: scipy.spatial
使うライブラリ
| アルゴリズム・問題 | Library Checker | 提出 | |
|---|---|---|---|
| ConvexHull | 凸包 | - | - |
AtCoder 上の問題
| 問題 | 提出 | |
|---|---|---|
| ConvexHull | ABC022-D Big Bang | Link |
| ConvexHull | AGC021-B Holes | Link |
| ConvexHull | yukicoder No.199 星を描こう | Link |
- 要検討事項
- ABC022-D を kd-tree で最近点対を求める解法でやってみたが，提出してみると TLE だった
TODO
- FFT
- ボロノイ図・ドロネー三角形分割・KD 木
- from scipy.ndimage import distance_transform_cdt:
- https://atcoder.jp/contests/agc033/submissions/5279051
- https://twitter.com/lily0727k/status/1124964133730783233