なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

競技プログラミング

ゼロから始める動的計画法 - コイン問題

問題設定 Project Euler Problem 31 考察 動的計画法による解答 問題を簡単にする なぜ動的計画法か? まずは2次元配列で Rubyのコードに落とし込む プロジェクトオイラー用に微調整 問題設定 Project Euler Problem 31 ターゲットとする問題は以下 Project…

アルゴリズムまとまってるサイト

メモ用、他にあれば追記する ポータルサイト www.geeksforgeeks.orgwww.csegeek.com 大学の授業シラバス系 ヨークカレッジ・ペンシルベニア校 Lecture Notes イリノイ大学アーバナ・シャンペーン校 Jeff Erickson's Algorithms, Etc. このサイトにあったサイ…

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

アルゴリズム 経路圧縮 rankによる木のマージ処理 ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要で…

AtCoder - AtCoder Beginner Contest 012 (バスと避けられない運命) を解いてみた

前回の競プロ! 解法 Rubyによる解答 TLE D言語による解答 AC! 前回の競プロ! ダイクストラ法を学んでようやくスタート地点に立てました。ダイクストラ法については以下のエントリを参照。nantonaku-shiawase.hatenablog.com 解法 Rubyによる解答 TLE アル…

AOJ - ALDS1_12_B (ダイクストラ法) を解いてみた

問題設定 最短経路問題の分類とアルゴリズムの使いどころ グラフをGraphvizでビジュアル化する アルゴリズム 疑似コード 自分の解答 AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Onlin…

AOJ - ALDS1_12_A (プリム法) を解いてみた

問題設定 グラフをGraphvizでビジュアル化する アルゴリズム 疑似コード 自分の解答 コードの工夫など AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge 問題設定 最小全域木というのは、 重…

AOJ - ALDS1_11_A,B,C (グラフアルゴリズム) を解いてみた

ALDS1_11_A (隣接行列) 自分の解答 ALDS1_11_B (深さ優先探索) アルゴリズム 自分の解答 ALDS1_11_C (幅優先探索) アルゴリズム 自分の解答 AOJ - ALDS1_11は、グラフアルゴリズムです。グラフの表現 | アルゴリズムとデータ構造 | Aizu Online Judge 深さ優…

AOJ - DPL_1 D (最長増加部分列) を解いてみた

最長増加部分列の基本 問題設定 アルゴリズム 線形探索版のプログラム - O(N^2) 二分探索版のプログラム - O(N log N) サンプルプログラム 線形探索版のプログラム - O(N^2) 二分探索版のプログラム - O(N log N) AOJ - DPL_1 Dは、最長増加部分列(Longest I…

AOJ - ALDS1_7_A, B, C (木構造) を解いてみた

勝手に解いてろとか言わないで… 木構造を使うときの基本 ALDS1_7_A - 根付き木 get_depth ( id, nodes ) get_children ( id, nodes ) ALDS1_7_B - 二分木 get_depth ( id, nodes ) get_height ( id, nodes ) get_sibling ( id, nodes ) ALDS1_7_C - 木の巡回…

アルゴリズム学びフローを作成してみる

AOJの本 本の内容とレビュー 見通しを立ててみる プロコンで解いた問題を格納 AOJの本 この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆,Oz…

AOJ - DSL_1_A (Union-Find) を解いてみた

AOJ - DSL_1_A quick find で求めてみる quick-unionで求めてみる DSL_1_Aは、Coursera Algorithm I で最近習ったばかりのUnion-Findです AOJ - DSL_1_A 互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge quick find で求めてみる 自分…

AOJ - ITP1_7_D (行列の積) を解いてみた

AOJ - ITP1_7_D 行列の積をプログラムに起こすと? 問題の内容 問題の解法 行列計算の参考リンク ITP1_7_Dは、今自分の中でブームの行列の積の問題です。生で計算しないにしても、機械学習にも大いに関係があります。 AOJ - ITP1_7_D Matrix Multiplication …

AOJ - ITP1_7_B (組み合わせ) を解いてみた

偉そうに書いてるが、これは序の口の問題である。。。 AOJ - ITP1_7_B 解法1 algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow アルゴリズム 処理フロー 結果 解法2 Given an array A[] and a number x, …