しばらく忙しくて，更新が途絶えてしまいました． 少なくとも今年度中は，2週間に1回更新を続けていきたいです． 本題． 競技プログラミングで，ダイクストラアルゴリズムを実装する機会があったので，ソースコードを載せておきます． ダイクストラアルゴリズムとは？ ダイクストラアルゴリズム(ダイクストラ法)とは，重み付きグラフの探索アルゴリズムの一種で，すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです． グラフの始点が与えられた時，そこから他の(すべての)頂点までの最短経路と，そこまでの重みの和(最短距離)を求めることができます． ダイクストラ法 - Wikipedia ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが，プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで，O(|E|log|V|)程度で最短経路を求められます． 優先度つ

まえがき 使ってるもの クラウド 言語 アーキテクチャ やったことを簡潔に お金がやばくなる 無料運用する方法をググってみる 自分でapp.yamlを書いてみる お金が減り続ける お金が減り続ける2 GAEの動作環境 スタンダード環境を試してみる Future Contestをスタンダード環境に切り替える 定期的に更新する その他 AtCoderのAPIサーバーを立てる ページがプレーンテキストとして表示される ページが更新されない 結果 感想 これから まえがき Future Contestとは？→これ 初めてWebサイト作ってみたで作ったサイトを無料運用にしたのでログを取っておく。 ただのメモなので技術的なことは詳しく書いてない 時系列順に書いてく たぶんめっちゃアホみたいなことやってる 使ってるもの クラウド GAE 言語 Go アーキテクチャ 最終的には以下のようなアーキテクチャに

今回は素集合データ構造であるUnion-Find木に重みを付けた、Weighted（重み付き) Union-Find木についてまとめます。 Union-Find木についてよくわからないという方は、 at274.hatenablog.com こちらを先に見ていただいた方がいいかと思います。 Weighted Union-Find木について Pythonによる実装 準備 検索（find） 併合（union） 完成形 Weighted Union-Find木について 実装前に、Weighted Union-Findがどんなものかざっくり説明しておきましょう。 まずはイメージ図を見てやってください。 特に深い説明はいらないかと思います。 イメージ図通りです。 例えば、「AさんはBさんより3歳年上。CさんはBさんより2つ下。ではAさんはCさんよりいくつ上？（もしくは下？）」みたいな問題に対して使えま

はじめに 標準入力 input と sys.stdin.readline ソート sort と sorted ソートの key ループ for と while リスト リストの初期化 二次元配列の場合 リストの値参照 リストへの値追加 それぞれの処理速度 まとめ はじめに 最近、PythonでAtCoderなどの競技プログラミングに挑戦しています。これまであまりに気にしなかったけど、ちょっとした書き方で処理速度が変わってくることに気づいたので、これを気に少し調べてみました。 目次にあるように、標準入力、ソート、ループ、リストについて、計8個の処理の速度比較を行いました。処理速度の計測方法は、Mac Book Pro*1を使い、timeitでそれぞれ100回計測*2し、平均と標準偏差を求めています。 結果だけ知りたい方は、まとめへどうぞ。 計測に用いたコードは以下にあります。 github.

本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造　(通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト

この記事はCompetitive Programming (その2) Advent Calendar 2015の21日目の記事です（遅れてすみません） 20日目はMさんの高速なビット行列乗算、 22日目はir5さんのtopcoder ボツ問供養です。 なにを書くのか? Competitive Programming Advent Calendar 2015で11日目のn_knuu6さんがpythonで競技プログラミングをする際に便利な関数とか5選を紹介されてました。 今回はその記事では紹介されていなかった競プロに便利な関数・データ構造をいくつか紹介したいと思います。 sys.recursionlimit pythonで競プロを使い始めた人がよくハマる落とし穴として再帰関数の再帰深さ制限があります。 >>> def mysum(n): ... if n == 1: return 1 ...