AtCoder で scipy を使って問題を解く

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

計算幾何: scipy.spatial

使うライブラリ

アルゴリズム・問題 Library Checker 提出
ConvexHull 凸包 - -

AtCoder 上の問題

問題 提出
ConvexHull ABC022-D Big Bang Link
ConvexHull AGC021-B Holes Link
ConvexHull yukicoder No.199 星を描こう Link

TODO

  • FFT
  • ボロノイ図・ドロネー三角形分割・KD 木
  • from scipy.ndimage import distance_transform_cdt:
    • https://atcoder.jp/contests/agc033/submissions/5279051
    • https://twitter.com/lily0727k/status/1124964133730783233