プログラミング
AppleScriptとRubyを使って, iTunesの再生回数を取得しグラフ化してみた. やろうと思ったきっかけは, 自分がaikoの曲をどれだけ聞いているか知りたかったから. よって, このあと出て来る例はすべてaikoを検索している. developer.apple.com AppleScriptで曲…
OpenCVを使ってボロノイ分割とドロネー分割をした. 実行環境 Windows7 64bit OpenCV 3.2.0 MinGW CLion 2017.1 特徴点の抽出 画像から特徴点を取り出すのに, Shi-Tomashiのコーナー検出法を利用する. void goodFeaturesToTrack(InputArray image, // 入力画…
問題はこちらから abc061.contest.atcoder.jp 問題A : Between Two Integers #include <iostream> using namespace std; int main(){ int a, b, c; cin >> a >> b >> c; cout << ((a <= c && c <= b)?"Yes":"No") << endl; } 問題B : Counting Roads #include<bits/stdc++.h> #define </bits/stdc++.h></iostream>…
問題はこちらから. abc062.contest.atcoder.jp 問題A: Grouping #include <iostream> using namespace std; int main() { int x, y; int groups[] = {0, 1, 2, 1, 3, 1, 3, 1, 1, 3, 1, 3, 1}; cin >> x >> y; cout << (groups[x] == groups[y]?"Yes":"No") << endl; }</iostream>…
問題はこちらからどうぞ. abc063.contest.atcoder.jp 問題A: Restricted #include <iostream> using namespace std; int main(){ int a, b; cin >> a >> b; if(10 <= a + b) cout << "error" << endl; else cout << a + b << endl; } 問題B: Varied #include<bits/stdc++.h> #define r</bits/stdc++.h></iostream>…
問題はこちらからどうぞ. abc064.contest.atcoder.jp 問題A: RGB Cards #include <iostream> using namespace std; int main(){ int r, g, b; cin >> r >> g >> b; cout << ((r * 100 + g * 10 + b)%4==0?"YES":"NO") << endl; } 問題B: Traveling AtCoDeer Problem #i</iostream>…
第4章 基本的な文法 変数と基本データ型とそのリテラル 型 ビット幅 Double 64 Float 32 Long 64 Int 32 Short 16 Byte 8 Doubleを表現するリテラルは, 123.4e2のような形で表現することができます. 0xを頭につけることで16進数, 0bを付けることで2進数を表…
先日行われたGoogle I/OでKotlinが制式採用されることが発表になりましたね. jp.techcrunch.com ちょっときになったのでKotlinスタートブックを手に入れました. 最初から無理のないペースで読んでいき, メモ代わりにブログを書いていこうと思います. 第1章 K…
問題 1862 -- Stripies 方針 入力された値を降順ソートする. 質量m1とm2の物体があった時, で求められるので, これを先頭から順にやっていく. コード #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> </map></vector></string></iostream></climits></cctype></ctime></cmath></cstring></cstdlib></cstdio>…
問題 ナップザック問題 | 動的計画法 | Aizu Online Judge 方針 各要素を入れる, 入れないというパターンを試して価値を高める. ただし, すべての商品に対して上のパターンを試すととなるため終わらない. 動的計画法を用いることにより, にまで落とすことが…
問題 コイン問題 | 動的計画法 | Aizu Online Judge 方針 動的計画法を用いて解く. dp[i] := i円支払うときのコインの最小枚数 コード #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #incl</list></map></vector></string></iostream></climits></cctype></ctime></cmath></cstring></cstdlib></cstdio>…
問題 Rummy | Aizu Online Judge 方針 数字と記号のペアが与えられるので, 全通り試してセットであるか試す. セットである条件は 3枚とも同じ色であること 番号がすべて同じか連番になっていること（ただし, 8, 9, 1のような連番は認められない） これが3枚3…
問題 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 DFSをして正しい並びになったかを判定し, その時のターン数を返す. 探索した盤面はフラグを立てておき, 同じ状態を２回以上探索しないようにする. mapって比較の"<“が定義されてないと使えないの…
問題 Need for Speed – Kattis, ICPC ある区間の距離と移動速度がそれぞれとして与えられる. は実際の速度s+c(cは定数)として表示されている. 実際にかかった時間tが与えられるので, cが何であるかを求めよ. 方針 となったときのCが答えとなる. 二分探索を行…
問題 Square Route | Aizu Online Judge 方針 道と道の間隔が与えられるので, 正方形の区画がいくつあるか数える問題 すべてのパターンを試す方法では, となり終わらない. そこで, 辺の長さの全パターンを予め求め, その出現個数を元に計算する.（この場合は…
問題 最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 隣接行列を用いたダイクストラ法はグラフG=(V, E)においてとなる. 今回はノード数がであるので, 隣接リストを使った実装を行う. 隣接リストでグラフを表現し, 二分ヒープ(priority_queue…
問題 Polygonal Line Search | Aizu Online Judge 方針 0番目の入力セットと1〜n番目までのセットを比較して同じ形の折れ線であるか判定する. 同じ折れ線であるかの判定は, 以下のいずれかを満たす. xy平面内で回転および平行移動によって(拡大縮小や裏返し…
問題 優先度付きキュー | アルゴリズムとデータ構造 | Aizu Online Judge 方針 優先度付きキューを実装する問題 （体がしんどいので元気になったらしっかり書きます許して） コード #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream></iostream></climits></cctype></ctime></cmath></cstring></cstdlib></cstdio>…
問題 ヒープの構築 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 最大ヒープを作る問題 節点のキーが子のキーよりも大きいという条件を満たすものを最大ヒープという. ボトムアップに関数を適用することで最大ヒープに変換する. コード #include <iostream> u</iostream>…
問題 ヒープ 完全二分木 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 完全二分木とは, すべての葉が同じ深さであり内部節点の次数が2であるような二分木である. 節点番号がiであるとき, 親はi/2, 左の子ノードは2i, 右の子ノードは2i+1で求めるこ…
問題 二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木の削除を実装する問題 削除するノードを以下の3つの条件で場合分けし処理を行う. 子ノードを持たない 子ノードを1つだけ持つ 子ノードを2つ持つ 1, 2の場合は対象ノー…
問題 二分探索木 検索 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木の探索を行う問題 二分探索木の構築(insert)自体は前回のものを流用 muttan1203.hatenablog.com 関数findは, カレントノードがNULLになるまでループし, 値が見つかった…
問題 二分探索木 挿入| アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木を生成する問題 ある節点xの左部分木に属する節点をy1, 右部分木に属する節点をy2としたとき, y1のキー xのキー かつ xのキー y2のキーを満たすものである. コード #inc…
問題 最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge 方針 最小全域木(Minimum Spanning Tree)を作ろう. 全域木は閉路を持たない木(でいいのだろうか) 最小全域木は, 辺のコストの和が最も小さくなる全域木のこと. 頂点数がであることから, プリ…
問題 グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 グラフの連結成分(Connected Components)を求める問題. 連結成分とは, 必ずしも連結でないグラフGに対して, その極大連結部分グラフのことをグラフGの連結成分という. G'がGの極…
問題 Quick Sort | Aizu Online Judge 方針 クイックソートはの高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量はである. それを解するため, しきい値(pivot)をランダムに取る, データ列の中央値を取るなどの工夫が必要. 分割統…
問題 パーティション | アルゴリズムとデータ構造 | Aizu Online Judge 方針 iをA[r]以下の数が格納されている終端を示す変数とする. jをpからr-1まで進めていき, A[j]がxより大きければそのまま, x以下の場合はiを1つ進めてスワップする. 最後にi+1とr番目…
問題 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 バックトラック法を用いて探索を行おう. コード #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #…</deque></queue></list></map></vector></string></iostream></climits></cctype></ctime></cmath></cstring></cstdlib></cstdio>
問題 木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 inorderを先頭から見ていったとき, その値をcとする. そのcの位置をpreorderの中から探し, その値をmとする. prem[m]より左側の値はcを根とする木の左部分木, 右側は右部分木となる. そ…
問題 Tree Walk | Aizu Online Judge 方針 二分木を実装する. 行きかけ順(Preorder Tree Walk), 通りかけ順(Inorder Tree Walk), 帰りがけ順(Postorder Tree Walk)を実装する. 行きかけ順は, 根（接点）→左部分木→右部分木の順で出力を行う. 通りかけ順は左…
