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_componentsEducational DP Contest-G Longest PathLink
dijkstraABC035-D トレジャーハントLink
dijkstra第一回アルゴリズム実技検定-J 地ならしLink
floyd_warshallABC143-E Travel by CarLink
minimum_spanning_tree第一回アルゴリズム実技検定-L グラデーションLink
maximum_flowABC010-D 浮気予防Link
maximum_flowABC193-F ZebranessLink
maximum_bipartite_matchingARC092-C 2D Plane 2N PointsLink
  • 要検証事項等
    • maximum_flow は特殊なケース（source と sink が連結でない場合など）で ValueError が投げられて RuntimeError になることがあるっぽい？

最適化: scipy.optimize

使うライブラリ

アルゴリズム・問題Library Checker提出
minimize_scalar関数の最小値--
newtonニュートン法（関数の根）--
linprog線形計画法--
linear_sum_assignment割当問題問題Link

AtCoder 上の問題

問題提出
minimize_scalarARC054-B ムーアの法則Link
minimize_scalarARC049-B 高橋ノルム君Link
newtonABC026-D 高橋君ボール1号Link
linprogyukicoder No.453 製薬会社Link

計算幾何: scipy.spatial

使うライブラリ

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

AtCoder 上の問題

問題提出
ConvexHullABC022-D Big BangLink
ConvexHullAGC021-B HolesLink
ConvexHullyukicoder No.199 星を描こうLink

TODO