冷めたコーヒー

Weniger, aber besser

競技プログラミング

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