冷めたコーヒー

Weniger, aber besser

Python

非線型一変数関数の最小化(SciPy 使用)

これは何? 一変数関数 $f\colon\mathbb{R}\to\mathbb{R}$ を与えられた閉区間 $\Omega \subseteq \mathbb{R}$ 上で最小化する $x^\star$ を求める方法について扱う 最適化問題として記述すると以下のように表される: \begin{align} \min \quad &f(x) \\ \ma…

フルランク行列をランダムに生成する手法(Python による実装付き)

フルランクな行列をランダムに生成する手法を教えて頂きました: https://t.co/mp7HaadpwZランダムなゼロでない固有値を対角にならべてから、ランダムなユニタリー行列で相似変換すれば良さそうです。ランダムなユニタリー行列はランダムなエルミート行列から…

CVXPY を用いた等式制約付き最適化問題の求解

CVXPY による制約付き最適化問題を求解

yukicoder No.1077「Noelちゃんと星々4」in Python

yukicoder No.1077「Noelちゃんと星々4」

AtCoder ABC 021 C - 正直者の高橋くん (300 点) in Python

以前の記事で ABC167-D について扱いました。ここで出題された問題は幅優先探索を用いることによって綺麗に解くことができました。今回はほぼ同様の実装で解くことのできる例題を見つけたので扱ってみたいと思います。 問題の概要 $N$ 個の町(町 $1,$ 町 $2…

Dijkstra 法の隣接行列による実装 in Python

概要 前回の記事において、単一始点最短経路(Single Source Shortest Path; SSSP)の重みを求めるプログラムである Dijkstra(ダイクストラ)法のpythonによる実装例を紹介しました。そこでは、隣接リストを用いて実装をしましたが、隣接行列を用いても同様…

単一始点最短経路問題を Dijkstra 法で実装する in Python

概要 単一始点最短経路(Single Source Shortest Path; SSSP)の重みを求めるプログラム、通称 Dijkstra(ダイクストラ)法のpythonによる実装を提示します。 アルゴリズム アルゴリズムについては蟻本をはじめ多くの書籍や記事で詳しく扱われているので、こ…

Python における element in list が遅い件について

はじめに element in listについて 例題 問題概要 制約 解答 おわりに はじめに 以前の記事で、pythonにおいてelement in listという書き方は非常に遅いので気を付けましょうと書きました。これについて、実例とともに見ていきたいと思います。 element in l…

AtCoder ABC 168 C - : (Colon) (300 点) in Python

話題になった^1問題なので取り上げてみます。 a, b, h, m = map(int, input().split()) from math import sqrt, cos, radians angle = abs(30 * (h + m / 60) - 6 * m) c = sqrt(a**2 + b**2 - 2*a*b*cos(radians(angle))) print(c) 針の動きは次のように考…

AtCoder ABC 168 D - .. (Double Dots) (400 点) in Python

幅優先探索を使う典型的な問題でした...。pythonではcollectionsモジュールのdequeを用いることによって実装してあげるのが最も自然なのかなと思うので、そのように実装してあげます。「幅優先探索ってそもそも何?」という方は、けんちょんさんの記事を一度…

AtCoder ABC 167 D - Teleporter (400 点) in Python

AtCoder ABC 167 D - Teleporter (400 点) in Python

AtCoder ABC 164 D - Multiple of 2019 (400 点) in Python

AtCoder ABC 164 D - Multiple of 2019 (400 点) in Python

AtCoder ABC 150 C - Count Order (300 点) in Python

AtCoder 150 C in Python

リーマン多様体上の最適化の初歩と Pymanopt による数値実験

リーマン多様体上の最適化問題を,PythonのPymanoptソルバーを用いて実装する.

相補性問題の初歩と Python による数値解法

はじめに 相補性問題の定式化 相補性問題の再定式化 相補性問題に対するアルゴリズム アルゴリズム実装における注意点 B 劣微分 $V \in \partial_B \Phi(x)$ の導出 勾配ベクトル $\nabla\Psi(x)$ の導出 Python による実装 実装: 関数の定義 実装: 相補性問…

Python による数理最適化モデリングツール CVXPY の初歩

はじめに 数理最適化とは CVXPY 導入 数値実験 例1:線形計画問題(Linear Programming Problem; LP) Python によるサンプルコード 例2:最小二乗問題(制約付き) Python によるサンプルコード 例3:半正定値計画問題(Semidefinite Programming Problem; SDP) …