きままにものづくり

日々の気付いたことなんかを書いてます。

2013-01-01から1年間の記事一覧

順列列挙-再帰

コード 実装日 1回目:11/27

Bellman-Ford

コード 実装日 1回目:11/25 テスト POJ3268 関連問題 POJ3268

Dijkstra

コード 実装日 1回目:11/25 テスト POJ3268 関連問題 POJ3268

クイックソート-ループ

コード 実装日 1回目:11/25 テスト ALDS-LESSON 5B 関連問題 ALDS-LESSON 5B

クイックソート-再帰

コード 実装日 1回目:11/25 2回目:1/31 テスト ALDS-LESSON 5B 関連問題 ALDS-LESSON 5B

C++でN次元の配列を引数として受け取る方法

C++

普通なら配列はvectorを使用するべきだけど、訳あってSTLが使えないといった時に使える。

セグメント木

コード 実装日 1回目:11/15 テスト POJ3368 関連問題 POJ3368

挿入ソート

コード 実装日 1回目:11/15 テスト ALDS LESSON 2 A 関連問題 ALDS LESSON 2 A

バブルソート

コード 実装日 1回目:11/15 テスト ALDS LESSON 2 A 関連問題 ALDS LESSON 2 A

マージソート-ループ

コード 実装日 1日目:11/14 テスト ALDS-LESSON 5B 関連問題 ALDS-LESSON 5B

マージソート-再帰

コード 実装日 1回目:11/14 テスト ALDS-LESSON 5B 関連問題 ALDS-LESSON 5B

最大流(Ford-Fulkerson)

コード 実装日 1回目:11/13 テスト POJ1274 関連問題 POJ1274

全点対間最短路(Floyd Warshall)

コード 実装日 1回目:11/13 テスト POJ2139 関連問題 POJ2139

Binary Indexed Tree

コード 実装日 1回目:11/11 テスト POJ1990 関連問題 POJ1990 POJ3109 POJ2155 POJ2886

Union Find Tree

コード 実装日 1回目:11/11 2回目:1/18 テスト POJ 1703 関連問題 POJ1703 POJ2236 POJ2170

最長部分増加列 O(n log n)

コード 実装日 1回目:11/11 テスト POJ1631 関連問題 POJ1631

最長部分増加列 O(n^2)

コード 実装日 1回目:11/11 テスト 関連問題 POJ1631

アルゴリズム

一般的なアルゴリズムのC++実装の一覧を示す。アルゴリズムは実装しないとすぐに忘れてしまうので、一日ひとつのアルゴリズムを実装する。繰り返し実装することで定着させる。 動的計画法 ナップサック問題 01ナップザック問題 O(N W) O(N V) 個数制限なしナ…

POJ 3264 : Balanced Lineup

問題 要素数N()の数列が与えれる。[a,b]区間の最大値と最小値の差分を求めなさい。 解法 セグメント木を使う。最大値を保持する配列と最小値を保持する配列の2つを持つ。 計算量 更新: クエリ: コード

POJ 2886 : Who Gets the Most Candies?

問題 N()人の名前と値が与えられる。初めにK番目の人(1から始まる)からスタートし、選ばれた人は抜ける。抜ける際に、p番目の人はpの約数だけ飴がもらえる。次の人は、その人の値分だけ時計回りした番号の人になる。マイナスの場合は逆回転となる。飴の最大…

POJ 2155 : Matrix

問題 N*N()の配列が与えられる。各要素は、1か0しか値をとることができない。ふたつのクエリに対する処理を実行せよ。 (x,y)の要素が1なのか0なのか求めよ (x1,y1,x2,y2)の範囲をフリップせよ 解法 二次元のBITを使い、範囲操作をするために4つの二次元BITを…

POJ 3109 : Inner Vertices

問題 無限平面上にN()個の黒点が与えられる。それ以外は白点である。上下左右に黒点がある場合は、その点は黒点になる。黒点の総数を求めよ。 解法 座標圧縮と範囲操作可能なBITを使用する。はじめ、yの値でソートする。その後、逐次xでソートしxに囲まれて…

POJ 1990 : MooFest

問題 距離xと値vを持つN個の要素が与えられる。を全ての要素の組み合わせで算出し、その総和を求めよ。 解法 Binary Index Treeを使う。以下の記事を参考にした。 http://d.hatena.ne.jp/komiyam/20110223/1298457263 c1はx以下の数を示し、c2はx+1以上の数…

SRM570 Div1 Easy

問題 無限に広い平面を考える。命令セットaが与えられ、T回命令セットを実行した時の原点からのマンハッタン距離を求めよ。 解法 aの総和から、方向の周期fを求める。 周期fの回数だけaを実行し、マンハッタン距離の変化量を計算する。 Tを周期fで割り、上で…

AOJ 0531 : Paint Color

問題 幅W()高さH()の平面を考える。この平面内にN()の矩形が存在する。与えられた平面は、矩形により、いくつに分割されるか求めよ。 解法 座標圧縮を用いて計算量を減らす。与えられる数字は整数だが、分割されているかを判断する際には小数を考慮しなけれ…

POJ 2549 : Sumsets

問題 要素数N()の数列が与えられる。この中でa+b+c=dを満たす最大のdを求めよ。 解法 a+bを全列挙し、d-cを二分探索する。a+bで選んだ要素とd-cで選んだ要素は互いに違わなければならない。値と共に、インデックスを持たせることで同じ要素を使ってる場合を…

POJ 3977 : Subset

問題 要素数N()の数列が与えられる。その数列の中で空でない、総和がの絶対値が最小の部分列を求めよ。 解法 半分全列挙と二分探索。以下、注意点 2つに分割した集合のどちらか片方のみに答えの数値が含まれている場合を考慮する。つまり、集合1と集合2の組…

POJ 2674 : Linear World

問題 一直線上に左右それぞれに進行する物体がある。直線の長さLと物体の速度Vと初期位置Pと進行方向が与えられる。最後に落ちる物体の名称と時間を求めよ。 解法 貪欲法を使う。衝突により方向は変わるが速度は変わらない。注目物体以外に何もないと仮定し…

POJ 3185 : The Water Bowls

問題 要素数20の数列が与えられる。各要素は1か0である。すべての要素を0にする。ただし、注目点と隣接する要素は同時に反転される。 解法 反転される一番左の要素に注目する。各要素を見ていき1なら反転させる。ひとつめの要素に関してはそのままでは決定で…

POJ 1222 : EXTENDED LIGHTS OUT

問題 縦5×横6の配列が与えられる。配列の要素は1か0である。与えられた配列の要素を全て0にする。ただし、注目点と四近傍は同時に反転される。 解法 貪欲法で解ける。ひとつ上の要素が1ならその注目点で反転させる。一番上の要素の状態を全探索し、全て0にで…