ALGORITHM NOTE 長方形探索： 最大長方形の面積 Largest Rectangle
n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。 これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。
ALGORITHM NOTE デブンキー一家の大活躍
問題 パソコン甲子園2008 08 n 個の都市がり、それらが m 本の橋で繋がっています。各橋の維持費（コスト）が決められています。どの都市にでも行くことができるように橋を残しつつ、橋の維持費の合計が最小になるように、いくつかの橋を壊したときの、維持費の合計を求めて下さい。 001 #include<iostream> 002 using namespace std; 003 #define REP(i, e) for ( int i = 0; i < e; i++ ) 004 #define MAX 100 005 static const int INFTY = (1<<21); 006 int G[MAX][MAX], n; 007 008 int prim(){ 009 int P[MAX], D[MAX]; 010 bool V[MAX]; 011 REP(i, n) { D[
ALGORITHM NOTE ヒストグラム中の最大の長方形の面積
データの離散型分布を表すヒストグラム（柱状グラフ）は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した n 個の要素からなる１次元配列とします。(source: ACM/ICPC University of Ulm Local Contest) 以下のように、２重ループによって長方形の範囲を選び、そこにできる最大の長方形の面積を計算して更新していけば、全体での最大の面積を求めることができます。これはO(n2)のアルゴリズムです。 001 int getRectangleAreaBF( int size, int buffer[] ){ 002 int maxv = 0; 003 for ( int i =
ALGORITHM NOTE 最大正方形の面積 正方形探索
縦に n 行、横に n 列並べられた n × n のタイルがあります。いくつかのタイルには印（汚れ）が着いています。印のついていない（綺麗な）タイルだけから成るような最大の正方形の辺の長さを求めて下さい。各タイルの大きさは 1 × 1 メートルとします。 力任せのアルゴリズム タイルの数が小さければこの問題は以下に示すループの入れ子で解くことができます。 ２重ループによって候補となる正方形の左上角(i, j)を決める ループによって(i,j)から右下方向にできる正方形の幅 width を決める ２重ループによって決められた範囲が正方形であるかチェックし、そうならば maxWidth を更新する 001 int size; 002 char G[MAX][MAX]; 003 004 int getLargestSquareBF(){ 005 int maxWidth = 0; 006 for
ALGORITHM NOTE 最長増加部分列 Longest Increasing Subsequence
東西に並んだ高さの異なるｎ本の木があります。あるキコリがこれらの木を、西から東の方向へ木の高さが小さい順に並ぶように、いくつかの木を切り倒すことにしました。木の数を最大にするにはどの木を切れ（残せ）ばようでしょうか？ このような単純な（くだらない）問題でも、考えられる組み合わせを全て調べようとすると、それは各木を選ぶか選ばないかの組み合わせになるので、計算量はO(2n)となってしまいます。 この問題は、与えられた数列の最長増加部分列 Longest Increasing Subsequence (LIS) を求めることに帰着します。 最長増加部分列とは、与えられた数列 S S = a1, a2 , , , an の増加部分列 （ すべてのi, j (i < j)について ai < aj を満たす部分列 ） の中で長さが最大のものをいいます。 例えば、 S = 4 1 6 2 8 5 7 3
ALGORITHM NOTE 反復深化 Iterative Deepening
単純な深さ優先探索では初期状態から最終状態までの最短経路を求めることは不可能でした。しかし、深さを制限した深さ優先探索（深さ制限探索）を繰り返すことによって最短経路を求めることができます。つまり深さの制限 d を増加させながら深さ制限探索を繰り返します。このアルゴリズムを反復深化といいます。 反復深化及び深さ制限探索では高速化を図るために探索空間（探索木）の枝を刈ることが重要になります。探索アルゴリズムでは、現在の状態 n から最終状態までの最短経路コスト h を見積もることができれば枝を刈ることができます。つまり、現在の状態の深さ g に「ここからあと最低でも h 回の状態変化は必要だろう」というコストh を加えた値が深さの制限 d を超えた場合、そこで探索を打ち切ることができます。h は見積もりであって正確な値である必要はありません。h の値が大きいほど探索の速度は上がりますが、大きく
ALGORITHM NOTE 幅優先探索 Breadth First Search
幅優先探索はグラフにおける幅優先探索と同様に動作し（グラフのノードを状態とみなします）、幅広く状態変化を行います。つまり、現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。 それでは、８パズルを幅優先探索で解いてみましょう。 プログラムの説明 以下のプログラムは、例えば 2 8 3 x 1 5 4 7 6 というような、'x' をスペースとみなしたパズルを読み込み、 ldruuldlu という、l = left, r = right, u = up, d
ALGORITHM NOTE Sum of Different Primes
[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem D [難易度] ★★☆ [解説] 動的計画法（ＤＰ）で解けます。 ナップザック問題をＤＰで解く仕組みを応用します。 T[i][j][k] を 1 ～ i 番目の素数のうち k 個を用いて j を表す組み合わせの数 とすると、 T[i][j][k] = T[i-1][j][k] + T[i-1][j-primes[i]][k-1] となります（primes[i]は i 番目の素数を示す）。 サンプルプログラム 001 #include<iostream> 002 #include<vector> 003 using namespace std; 004 #define PMAX 187 005 #define NMAX 1120 006 #define KMAX 14 007 008 int
ALGORITHM NOTE Gap
001 #include<iostream> 002 #include<stdio.h> 003 #include<queue> 004 #include<map> 005 using namespace std; 006 007 class Gap{ 008 public: 009 short buffer[4][8]; 010 short pos[50]; 011 short space[4]; 012 013 Gap(){} 014 015 bool solved(){ 016 for ( int i = 0; i < 4; i++ ){ 017 for ( int j = 1; j < 7; j++ ){ 018 if ( buffer[i][j] != (i+1)*10 + (j+1) ) return false; 019 } 020 } 021 return true; 02
ALGORITHM NOTE 連結成分 Connected Components
001 #define MAX 1000 002 int size; 003 int adjMatrix[MAX][MAX]; // graph structure 004 bool visited[MAX]; 005 int group[MAX]; 006 007 void visit( int currentNode, int id ){ 008 visited[currentNode] = true; 009 group[currentNode] = id; 010 011 for ( int nextNode = 0; nextNode < size; nextNode++ ){ 012 if ( !adjMatrix[currentNode][nextNode] ) continue; 013 if ( !visited[nextNode] ){ 014 visit( nextN
ALGORITHM NOTE マージソート Merge Sort
マージソートの流れの論理的な構造は、ツリー（木）となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。しかし、データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。 void main(){ mergeSort( 配列全体 ); } void mergeSort( 部分配列 ){ if ( 部分配列の要素数が１以下 ) return; mergeSort( 部分配列の前半 ); mergeSort( 部分配列の後半 ); merge( 部分配列 ); } void merge( 部分配列 ){ すでにソートされている部分配列の前半と後半を昇順に統治（マージ）する. } マージソートのプログラムは、mergeSort と merge の２つの部分から構成されていま
ALGORITHM NOTE ナップザック問題 Knapsack Problem
大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます) この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2N) となります。N が数十個でも、実用的な時間では計算できません。 品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。 C[i][w] が、大きさ w のナ
ALGORITHM NOTE Zigzag
ACM-ICPC 2008 Aizu, Problem J: Zigzag 解説の通り Dijkstra で解いてみました。 与えられた点を通る２つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。 ただし、無駄な交点を作ってしまうとTLEになります。 コードは, Dijkstra の部分のみです。 void dijkstra(){ priority_queue<QState> PQ[5]; bool C[10][MAX][SMAX]; rep(i, nnode) rep(j, n) rep(k, (1<<nnode)) C[i][j][k]= false; rep(s, nnode) rep(i, P[s].size)
ALGORITHM NOTE 難儀な人たちが座る椅子
面倒なシミュレーションの問題です。 A, B, C, D それぞれの国の人の座り方をシミュレートする関数、setLeft, setB, setC, setD を素直に作りました。 椅子の状態を保持する配列（ここでは配列C）の先頭と末尾に番兵として'X'などを入れておくと実装が楽になるかと思います。 setD で使う getDist(int p, int d) は、p 番目の椅子から d 方向 （正が右、負が左）への空席の数を返します。 問題原文にある、椅子のサイズは大きすぎると思うのですが・・・ミスプリントでしょうね（AOJでは修正されています）。 #include<iostream> using namespace std; #define rep(i,s,e) for ( int i = s; i <= e; i++ ) #define MAX 10000 #define INFTY
ALGORITHM NOTE 高校生一人旅 ~青春の片道切符編~
グラフの最短経路（コスト）を求める問題です。残念ながら典型的な問題です。 ワーシャルフロイドが想定解法なのかもしれませんが、 ダイクストラのアルゴリズムで解きました。 #include<cstdio> #include<queue> #include<algorithm> #define rep(i,b,e) for ( int i = b; i <= e; i++ ) using namespace std; #define MAX 1000 #define INFTY (1<<21) int n, C[MAX+1][MAX+1], T[MAX+1][MAX+1]; class State{ public: int p, e; State( int p = 0, int e = 0 ): p(p), e(e){} bool operator < ( const State &s ) co
ALGORITHM NOTE Verbal Arithmetic
Verbal Arithmetic バックトラックで解いてみました。 適当な枝刈りをすれば手元で１０秒くらいorz。 優れた解法はlaycurseさんのブログを参照。 #include<iostream> #include<string> using namespace std; #define MAX 12 int N, L[26], R[26], LT[26][10], RT[26][10]; string S[MAX]; int num[26]; bool used[10]; int cnt, MDL[26], MDR[26]; void setValue( string str, int a[] ){ for ( int i = str.size()-1, p = 1; i >= 0; i--, p *= 10 ){ a[str[i] - 'A'] += p; } } bool z
ALGORITHM NOTE Discrete Speed
Discrete Speed ダイクストラのD。 「現在の場所、前にいた場所、速度」のノードでグラフを作りました。 #include<iostream> #include<cstdio> #include<queue> #define rep(i, n) for ( int i = 0; i < n; i++ ) using namespace std; #define MAX 30 #define VMAX 30 #define INFTY (1 << 21) class State{ public: int pos, from, v; double cost; State( int pos=0, int from=0, int v=0, double cost=0): pos(pos), from(from), v(v), cost(cost){} bool operator < (
ALGORITHM NOTE カード
まず最初に、隣り合う２組の山を重ねるときの最小のコストを計算します（j = 1）。 i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。 つぎに、隣り合う３組の山を重ねるときの最小のコストを計算します(j = 2)。 i = 1, 2, 3 について計算します。 つぎに、隣り合う４組の山を重ねるときの最小のコストを計算します(j = 3)。 i = 1, 2 について計算します。 同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。 i = 1 について計算します。 各 j の値での最小コストの計算方法を考えます。 例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります： カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト ＋ それら２つの山を重ねるコスト (k = i
ALGORITHM NOTE 上司のおごり
典型的な動的計画法の問題です。 K[i] を i 番目の金額、 Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする （1の場合に払えるものとする）と、 T0[j] を 0 で初期化し、 Ti[j] = Ti-1[j] | Ti-1[j - K[i]] となります。 あとは、i が素数で T[i] が 1 である i の最大値を求めます。 #include<iostream> using namespace std; #define KMAX 30 #define VMAX 1000000 int K[KMAX], T[VMAX+1]; void eratos ( int n, bool prime[]){ for ( int i = 0; i <= n; i++ ) prime[i] = false; for ( int i = 3; i <= n; i += 2 )
最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
