本稿では、プログラミングコンテストやアルゴリズム学習で頻繁に利用される基本的なアルゴリズムについて解説します。特に、配列操作を効率化する線形次元削減テクニック、そして二分探索、貪欲法といった重要な解法に焦点を当てます。
線形次元削減のテクニック
累積和と差分配列
累積和（Prefix Sum）は、配列の特定区間の合計値を効率的に計算するための手法です。与えられた配列 $A[n]$ に対して、区間 $A[l,r]$ の和を求める際、単純な方法では $O(n)$ の時間計算量がかかります。しかし、事前に $O(n)$ の処理で累積和配列を作成しておけば、各クエリは $O(1)$ で実行可能になります。
1次元累積和の例
#include <iostream>
#include <vector>
// 1次元配列の累積和を計算し、クエリに応答する例
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int arraySize;
std::cin >> arraySize; // 配列の要素数
std::vector<int> originalArray(arraySize + 1); // 元の配列 (1-indexed)
std::vector<int> cumulativeSums(arraySize + 1, 0); // 累積和配列 (1-indexed, cumulativeSums[0]=0)
// 元の配列を読み込み、同時に累積和を計算
for (int i = 1; i <= arraySize; ++i) {
std::cin >> originalArray[i];
cumulativeSums[i] = cumulativeSums[i - 1] + originalArray[i];
}
// 例: 区間 [L, R] の和を問い合わせる関数 (1-indexed)
// cumulativeSums[R] - cumulativeSums[L-1] で区間和が求められる
// int queryL = 2, queryR = 5;
// std::cout << "Sum from index " << queryL << " to " << queryR << ": "
// << cumulativeSums[queryR] - cumulativeSums[queryL - 1] << std::endl;
return 0;
}
累積和の概念は2次元配列にも拡張可能です。$A[n][m]$ の2次元配列において、部分行列 $A[xl \ldots xr][yl \ldots yr]$ の合計を求める場合、単純な方法では $O(nm)$ の時間が必要ですが、累積和を適用することで効率的な計算が可能になります。この際には包除原理（Inclusion-Exclusion Principle）が用いられます。
包除原理は、複数の集合の要素数を数える際に重複を避けるための原理です。例えば、2つの集合 $A$ と $B$ がある場合、$|A \cup B| = |A| + |B| - |A \cap B|$ となります。この原理は、2次元累積和の計算にも応用されます。
2次元累積和の例
#include <iostream>
#include <vector>
const int MAX_DIM_SIZE = 101; // 配列の最大サイズ
// 2次元配列の累積和を計算し、部分行列の和を問い合わせる例
// sumMatrix[i][j] は (1,1) から (i,j) までの部分行列の和を表す (1-indexed)
int sumMatrix[MAX_DIM_SIZE][MAX_DIM_SIZE];
// 2次元累積和の事前計算
void compute2DCumulativeSums(int rows, int cols, const int originalGrid[MAX_DIM_SIZE][MAX_DIM_SIZE]) {
// 0行目と0列目を初期化
for (int i = 0; i <= rows; ++i) { sumMatrix[i][0] = 0; }
for (int j = 0; j <= cols; ++j) { sumMatrix[0][j] = 0; }
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
// 包除原理を用いて計算
sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sumMatrix[i-1][j-1] + originalGrid[i][j];
}
}
}
// 部分行列の和を問い合わせる関数 (1-indexed)
// (x1, y1) から (x2, y2) までの部分行列の和
int querySubMatrixSum(int x1, int y1, int x2, int y2) {
return sumMatrix[x2][y2] - sumMatrix[x1-1][y2] - sumMatrix[x2][y1-1] + sumMatrix[x1-1][y1-1];
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int rows, cols;
std::cin >> rows >> cols; // 行列の行数と列数
int grid[MAX_DIM_SIZE][MAX_DIM_SIZE];
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
std::cin >> grid[i][j];
}
}
compute2DCumulativeSums(rows, cols, grid); // 累積和の計算
// 例: (r1, c1) から (r2, c2) までの部分行列の和を計算
// int r1=2, c1=2, r2=4, c2=4;
// std::cout << "Submatrix sum from (" << r1 << "," << c1 << ") to (" << r2 << "," << c2 << "): "
// << querySubMatrixSum(r1, c1, r2, c2) << std::endl;
return 0;
}
差分配列（Difference Array）は、累積和の逆演算と見なすことができます。配列 $A[n]$ に対して、差分配列 $D[n]$ を $D[i] = A[i] - A[i-1]$ （ただし $D[1] = A[1]$）と定義します。累積和が区間クエリに用いられるのに対し、差分配列は区間更新（例: $A[i \ldots j]$ の全要素に $k$ を加算）を $O(1)$ の時間計算量で効率的に行うために利用されます。
差分配列を用いた区間更新の例 (洛谷 P2367)
#include <iostream>
#include <vector>
#include <algorithm> // std::min のために必要
const int MAX_ARRAY_SIZE = 5000005;
int main() {
std::ios_base::sync_with_stdio(false); // 入出力高速化
std::cin.tie(NULL);
int arrayLength, queryCount;
std::cin >> arrayLength >> queryCount;
// 元の配列の値を格納（差分配列の初期化に使用）
std::vector<int> initialValues(arrayLength + 1);
// 差分配列 (1-indexed)。区間更新のために +2 のサイズを確保
std::vector<int> differenceArray(arrayLength + 2, 0);
// 差分配列の初期化
// differenceArray[i] = initialValues[i] - initialValues[i-1] となるように設定
for (int i = 1; i <= arrayLength; ++i) {
std::cin >> initialValues[i];
differenceArray[i] = initialValues[i] - initialValues[i-1];
}
// クエリの処理：指定区間への値の加算
for (int q = 0; q < queryCount; ++q) {
int startIdx, endIdx, incrementVal;
std::cin >> startIdx >> endIdx >> incrementVal;
differenceArray[startIdx] += incrementVal; // 区間開始点に加算
differenceArray[endIdx + 1] -= incrementVal; // 区間終了点の次で減算することで、その区間外には影響を与えない
}
int currentElementValue = 0;
// 問題 P2367 の制約 (a_i <= 1000) に基づき、初期最小値を十分に大きな値に設定
int overallMinimumValue = 1001;
// 差分配列の累積和を計算し、元の配列を復元しつつ最小値を探索
for (int i = 1; i <= arrayLength; ++i) {
currentElementValue += differenceArray[i]; // 差分配列の累積和が元の配列の現在の要素の値になる
overallMinimumValue = std::min(overallMinimumValue, currentElementValue);
}
std::cout << overallMinimumValue << std::endl;
return 0;
}
例題
洛谷 P1387 最大正方形
この問題では、元の行列の2次元累積和 sumMatrix[][] を利用します。行列が0と1で構成されていると仮定し、辺長 $k$ の部分正方行列 sumMatrix[r...r+k-1][c...c+k-1] の合計が $k^2$ に等しければ、その正方形内に0を含まず、全てが1で構成されていることになります。可能な辺長と開始点を全て列挙することで、時間計算量 $O(N^3)$ で解くことができ、与えられたデータサイズで十分間に合います。
#include <iostream>
#include <vector>
#include <algorithm> // std::min のために必要
const int MAX_GRID_DIM = 105; // 行列の最大サイズ
// 2次元累積和を格納する配列
int prefixSums[MAX_GRID_DIM][MAX_GRID_DIM];
// 2次元累積和を事前計算する関数
void precompute2DPrefixSums(int rows, int cols, const int originalMatrix[MAX_GRID_DIM][MAX_GRID_DIM]) {
for (int i = 0; i <= rows; ++i) { prefixSums[i][0] = 0; }
for (int j = 0; j <= cols; ++j) { prefixSums[0][j] = 0; }
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
prefixSums[i][j] = prefixSums[i-1][j] + prefixSums[i][j-1] - prefixSums[i-1][j-1] + originalMatrix[i][j];
}
}
}
// 指定された部分行列の合計値を問い合わせる関数 (1-indexed)
int querySubmatrixSum(int r1, int c1, int r2, int c2) {
return prefixSums[r2][c2] - prefixSums[r1-1][c2] - prefixSums[r2][c1-1] + prefixSums[r1-1][c1-1];
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int rows, cols;
std::cin >> rows >> cols;
int matrixData[MAX_GRID_DIM][MAX_GRID_DIM];
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
std::cin >> matrixData[i][j];
}
}
precompute2DPrefixSums(rows, cols, matrixData); // 累積和の計算
int maxSideLength = 0;
// 辺長を1から行列の最小次元まで試す
for (int currentSide = 1; currentSide <= std::min(rows, cols); ++currentSide) {
bool foundSquareOfCurrentSide = false;
// 現在の辺長を持つ正方形が、行列内でどこかに存在するかを探索
for (int r = 1; r <= rows - currentSide + 1; ++r) {
for (int c = 1; c <= cols - currentSide + 1; ++c) {
// 部分正方形の和が currentSide * currentSide に等しいかチェック (全て1の場合)
if (querySubmatrixSum(r, c, r + currentSide - 1, c + currentSide - 1) == currentSide * currentSide) {
foundSquareOfCurrentSide = true;
break; // この辺長で1つでも見つかれば十分
}
}
if (foundSquareOfCurrentSide) break;
}
if (foundSquareOfCurrentSide) {
maxSideLength = currentSide; // 現在の辺長で見つかったので更新
} else {
// 現在の辺長で見つからなかった場合、それ以上の辺長でも見つからない
break;
}
}
std::cout << maxSideLength << std::endl;
return 0;
}
洛谷 P3406 海底高铁
この問題では、鉄道区間の利用回数を効率的に計算し、カード購入の費用対効果を判断する必要があります。
まず、どの鉄道区間でカードを購入すべきかを検討します。$i$ 番目の区間が $x_i$ 回利用されるとします。通常の料金が $a[i]$、カード利用時の料金が $b[i]$、カード購入費用が $c[i]$ の場合、$x_i \times a[i] > x_i \times b[i] + c[i]$ が成り立つならば、カードを購入した方が費用を削減できます。このとき削減できる金額は $x_i \times a[i] - (x_i \times b[i] + c[i])$ となります。
次に、$x_i$ を計算する方法です。駅 $A$ から駅 $B$ へ移動する際（$A < B$ と仮定）、区間 $A$ から $B-1$ までの各鉄道区間を1回ずつ利用することになります。このような区間に対する利用回数の加算は、差分配列を使って効率的に処理できます。
最後に、全区間の通常運賃の合計から、カード購入によって節約できる金額を差し引くことで、最終的な最小費用を算出します。全区間の通常運賃の合計も、累積和を利用して効率的に計算できます。
#include <iostream>
#include <vector>
#include <algorithm> // std::min, std::max のために必要
const int MAX_STATIONS = 100000 + 5; // 駅の最大数
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numStations; // 駅の数 (N)
int numJourneys; // 移動回数 (M)
std::cin >> numStations >> numJourneys;
std::vector<long long> journeyPath(numJourneys + 1); // 移動経路の駅番号 (1-indexed)
for (int i = 1; i <= numJourneys; ++i) {
std::cin >> journeyPath[i];
}
// 鉄道区間の情報 (1-indexed, numStations-1 区間が存在)
std::vector<long long> normalFare(numStations); // 通常運賃 (normalFare[i] は i番目の区間)
std::vector<long long> cardFare(numStations); // カード利用時の区間運賃
std::vector<long long> cardCost(numStations); // カード購入費用
std::vector<long long> cumulativeNormalFare(numStations); // 通常運賃の累積和
cumulativeNormalFare[0] = 0; // 0番目を便宜上0とする
// i番目の区間は駅iと駅i+1の間
for (int i = 1; i < numStations; ++i) {
std::cin >> normalFare[i] >> cardFare[i] >> cardCost[i];
cumulativeNormalFare[i] = cumulativeNormalFare[i-1] + normalFare[i];
}
std::vector<long long> segmentUsageDifference(numStations + 1, 0); // 区間利用回数の差分配列
long long totalExpense = 0; // 合計費用
// 各移動経路について、区間利用回数を差分配列に記録し、通常運賃を合計
for (int i = 2; i <= numJourneys; ++i) {
long long startStation = journeyPath[i-1];
long long endStation = journeyPath[i];
if (startStation < endStation) {
segmentUsageDifference[startStation]++;
segmentUsageDifference[endStation]--; // 区間 [startStation, endStation-1] を利用
totalExpense += cumulativeNormalFare[endStation - 1] - cumulativeNormalFare[startStation - 1];
} else { // startStation > endStation (逆方向移動)
segmentUsageDifference[endStation]++;
segmentUsageDifference[startStation]--; // 区間 [endStation, startStation-1] を利用
totalExpense += cumulativeNormalFare[startStation - 1] - cumulativeNormalFare[endStation - 1];
}
}
long long currentSegmentUsageCount = 0;
// 差分配列から実際の区間利用回数を復元し、カード利用による最適化を検討
for (int i = 1; i < numStations; ++i) { // i番目の区間について
currentSegmentUsageCount += segmentUsageDifference[i]; // i番目の区間の実際の利用回数
// カード購入の方が安い場合、その分の節約額を totalExpense から差し引く
if (cardCost[i] + currentSegmentUsageCount * cardFare[i] < currentSegmentUsageCount * normalFare[i]) {
totalExpense -= (currentSegmentUsageCount * normalFare[i] - (cardCost[i] + currentSegmentUsageCount * cardFare[i]));
}
}
std::cout << totalExpense << std::endl;
return 0;
}
離散化
離散化（Discretization）は、値の範囲が非常に広いが、その相対的な大小関係のみが重要となる場合に、値域を狭い連続した整数空間にマッピングするテクニックです。これは、特定のアルゴリズムにおいてデータの処理効率を向上させる目的で利用されます。
例えば、$ [1, 20, 300, 4234, 51234, 64321, 114514, 1919810] $ という数値の集合があったとき、これらの値の大小関係だけに着目するなら、$ [1, 2, 3, 4, 5, 6, 7, 8] $ といったより小さい連続した整数で表現しても同等に扱えます。元の配列をソートし、重複を除去することで、各要素はそのソートされた配列内での位置（インデックス）によって、新しい離散化された値として表現されます。
離散化の一般的な実装例
#include <vector>
#include <algorithm> // std::sort, std::unique, std::lower_bound のために必要
// 離散化を管理する構造体
struct Discretizer {
std::vector<int> uniqueSortedValues; // 離散化された一意な値のリスト
// 元のデータを基に離散化マップを初期化
void initialize(const std::vector<int>& originalData) {
uniqueSortedValues = originalData; // 元のデータをコピー
std::sort(uniqueSortedValues.begin(), uniqueSortedValues.end()); // ソート
// 重複を除去し、uniqueSortedValues のサイズを更新
uniqueSortedValues.erase(
std::unique(uniqueSortedValues.begin(), uniqueSortedValues.end()),
uniqueSortedValues.end()
);
}
// 元の値を離散化された値に変換（0-indexed のインデックスを返す）
int getDiscretizedIndex(int originalValue) const {
// std::lower_bound は `originalValue` が初めて現れる位置のイテレータを返す
// (または、`originalValue`より大きい最初の要素の位置)
return std::lower_bound(uniqueSortedValues.begin(), uniqueSortedValues.end(), originalValue) - uniqueSortedValues.begin();
// 1-indexed が必要な場合は `+ 1` を追加
// return std::lower_bound(...) - uniqueSortedValues.begin() + 1;
}
// 離散化された値の総数を取得
int getUniqueCount() const {
return uniqueSortedValues.size();
}
};
// 使用例 (main関数は省略)
// int main() {
// std::vector<int> sampleData = {1, 20, 300, 4234, 51234, 64321, 114514, 1919810, 20};
//
// Discretizer disc;
// disc.initialize(sampleData);
//
// // 例: 元の値 20 が離散化されて何になるか
// // std::cout << "Original 20 -> Discretized Index: " << disc.getDiscretizedIndex(20) << std::endl; // 0-indexed で 1
// // std::cout << "Original 300 -> Discretized Index: " << disc.getDiscretizedIndex(300) << std::endl; // 0-indexed で 2
//
// return 0;
// }
離散化は、std::map を用いて実現することも可能です。
例題
CF670C Cinema
この問題では、多くの科学者が持つ言語IDと、映画が持つ言語IDを離散化します。全ての言語IDを集めてソートし、重複を除去することで、各言語IDをより小さい連続した整数値にマッピングできます。次に、各言語IDを持つ科学者の数をカウントします。最後に、各映画が満足させる科学者の数（好む言語を話す科学者の数）と、許容する科学者の数（字幕言語を話す科学者の数）を比較して、最も評価の高い映画を選択します。
#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::unique, std::lower_bound のために必要
#include <map> // std::map を使用して言語カウントを管理することも可能だが、ここではvectorで
// 言語IDを離散化されたインデックスに変換するヘルパー関数 (1-indexed)
int getDiscretizedIndex(int targetID, const std::vector<int>& uniqueLanguageIDs) {
return std::lower_bound(uniqueLanguageIDs.begin(), uniqueLanguageIDs.end(), targetID) - uniqueLanguageIDs.begin() + 1;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numScientists;
std::cin >> numScientists;
std::vector<int> scientistLanguages(numScientists);
std::vector<int> allLanguagesForDiscretization; // 全ての言語IDを集めて離散化に利用
for (int i = 0; i < numScientists; ++i) {
std::cin >> scientistLanguages[i];
allLanguagesForDiscretization.push_back(scientistLanguages[i]);
}
int numMovies;
std::cin >> numMovies;
std::vector<int> moviePreferredLanguages(numMovies); // 映画が好まれる言語
std::vector<int> movieSubtitleLanguages(numMovies); // 映画の字幕言語
for (int i = 0; i < numMovies; ++i) {
std::cin >> moviePreferredLanguages[i];
allLanguagesForDiscretization.push_back(moviePreferredLanguages[i]);
}
for (int i = 0; i < numMovies; ++i) {
std::cin >> movieSubtitleLanguages[i];
allLanguagesForDiscretization.push_back(movieSubtitleLanguages[i]);
}
// 全ての言語IDをソートし、重複を除去して離散化リストを作成
std::sort(allLanguagesForDiscretization.begin(), allLanguagesForDiscretization.end());
allLanguagesForDiscretization.erase(
std::unique(allLanguagesForDiscretization.begin(), allLanguagesForDiscretization.end()),
allLanguagesForDiscretization.end()
);
// 各離散化された言語IDを持つ科学者の数をカウント
std::vector<int> languageSpeakerCounts(allLanguagesForDiscretization.size() + 1, 0); // 1-indexed
for (int langID : scientistLanguages) {
languageSpeakerCounts[getDiscretizedIndex(langID, allLanguagesForDiscretization)]++;
}
int bestMovieResultIndex = 0; // 0-indexedで最初の映画を最適候補とする
int maxPreferredSpeakers = -1;
int maxSubtitleSpeakers = -1;
for (int i = 0; i < numMovies; ++i) {
int currentMoviePreferredLangIdx = getDiscretizedIndex(moviePreferredLanguages[i], allLanguagesForDiscretization);
int currentMovieSubtitleLangIdx = getDiscretizedIndex(movieSubtitleLanguages[i], allLanguagesForDiscretization);
int currentPreferredCount = languageSpeakerCounts[currentMoviePreferredLangIdx];
int currentSubtitleCount = languageSpeakerCounts[currentMovieSubtitleLangIdx];
// 満足させる科学者の数が多い映画を選ぶ
if (currentPreferredCount > maxPreferredSpeakers) {
maxPreferredSpeakers = currentPreferredCount;
maxSubtitleSpeakers = currentSubtitleCount;
bestMovieResultIndex = i;
} else if (currentPreferredCount == maxPreferredSpeakers) {
// 満足させる科学者の数が同じ場合、次に字幕言語を話す科学者の数で比較
if (currentSubtitleCount > maxSubtitleSpeakers) {
maxSubtitleSpeakers = currentSubtitleCount;
bestMovieResultIndex = i;
}
}
}
std::cout << bestMovieResultIndex + 1 << std::endl; // 1-indexedで出力
return 0;
}
その他、離散化は併合探索木（Union-Find）と組み合わせて使用される問題もあります（例: 洛谷 P1955 [NOI2015] プログラム自動分析）。
双方向ポインタ（Two Pointers）
単調スタック・単調キュー
二分探索
二分探索アルゴリズムは、「二分性」と呼ばれる特定の性質を持つ問題の解決に非常に有効です。具体的には、ある区間において、区間の半分が特定の性質を満たし、残りの半分がその性質を満たさない場合、二分探索を利用することで、その性質を満たす最初の（あるいは最後の）要素を効率的に見つけることができます。二分探索には、主に整数に対する二分探索と実数に対する二分探索の2種類があります。
整数二分探索
整数区間 $[L, R]$ において、$[L, X]$ の範囲が何らかの性質を満たし、$[X+1, R]$ が満たさない場合、または $[X, R]$ の範囲が性質を満たし、$[L, X-1]$ が満たさない場合、整数二分探索を用いることで、この境界となる $X$ の値を特定できます。毎回探索範囲を半分に絞るため、アルゴリズムの時間計算量は $O(\log n)$ となります。
コードテンプレート
以下の2つのテンプレートは、競技プログラミングでよく使われる形式です。
#include <iostream> // ダミーの checkCondition のために必要
// #include <vector> // 必要に応じて
// checkCondition関数: ある値 testVal が特定の性質を満たすかを判定します。
// 問題に応じてこの関数を実装する必要があります。
bool checkCondition(long long testVal) {
// 例: testVal の二乗が 1000 以上か
// return testVal * testVal >= 1000;
return false; // ダミーの実装
}
// テンプレート1: 性質 P(x) が単調増加し、P(x) を満たす最初の x を探索します。
// (例: [F, F, T, T] の配列で最初の T を見つける場合)
// 探索範囲 [low, high] において、checkCondition(x) が真となる最小の x を見つけます。
long long findBoundaryType1(long long low, long long high) {
// low が結果を保持する候補となる。
// low < high の間、探索範囲を狭めていく。
while (low < high) {
long long mid = low + (high - low) / 2; // (low + high) / 2 と同じだがオーバーフローを避ける
if (checkCondition(mid)) { // mid が条件を満たす場合、答えは mid かそれより左にある
high = mid; // 探索範囲を [low, mid] に絞る
} else { // mid が条件を満たさない場合、答えは mid より右にある
low = mid + 1; // 探索範囲を [mid+1, high] に絞る
}
}
return low; // 最終的に low == high となり、それが答え
}
// テンプレート2: 性質 P(x) が単調増加し、P(x) を満たす最後の x を探索します。
// (例: [T, T, F, F] の配列で最後の T を見つける場合)
// 探索範囲 [low, high] において、checkCondition(x) が真となる最大の x を見つけます。
long long findBoundaryType2(long long low, long long high) {
// low が結果を保持する候補となる。
// low < high の間、探索範囲を狭めていく。
while (low < high) {
// mid が low にならないように +1 する (low=5, high=6 の時 mid=5 となり無限ループを防ぐため)
long long mid = low + (high - low + 1) / 2; // (low + high + 1) / 2 と同じだがオーバーフローを避ける
if (checkCondition(mid)) { // mid が条件を満たす場合、答えは mid かそれより右にある
low = mid; // 探索範囲を [mid, high] に絞る
} else { // mid が条件を満たさない場合、答えは mid より左にある
high = mid - 1; // 探索範囲を [low, mid-1] に絞る
}
}
return low; // 最終的に low == high となり、それが答え
}
// 使用例 (main関数は省略)
// int main() {
// // 例えば、checkCondition(x) が x >= 5 の場合に真を返すとする。
// // findBoundaryType1(1, 10) は 5 を返す（最初の T）。
// // findBoundaryType2(1, 10) は 10 を返す（範囲内で最後に T）。
// // (ただし、checkCondition の実装に依存)
// // std::cout << "Min value satisfying condition: " << findBoundaryType1(1, 10) << std::endl;
// // std::cout << "Max value satisfying condition: " << findBoundaryType2(1, 10) << std::endl;
// return 0;
// }
例題
- 洛谷 P1873 [COCI2011-2012#5] EKO / 砍树
- P1182 数列分段 Section II
- P1314 [NOIP2011 提高组] 聪明的质监员
- P1083 [NOIP2012 提高组] 借教室
- P4343 [SHOI2015] 自动刷题机
実数二分探索
実数二分探索は、解答が小数点以下 $k$ 桁の精度で求められる場合に利用されます。通常、イプシロン（$eps$）の値を $10^{-(k+2)}$ のように設定し、整数二分探索と同様のロジックで近似解を導出します。
精度 epsilon を用いたテンプレート
#include <cmath> // std::abs のために必要
// checkConditionDouble関数: ある実数値 testVal が特定の性質を満たすかを判定します。
// 問題に応じてこの関数を実装する必要があります。
bool checkConditionDouble(double testVal) {
// 例: testVal の三乗が 27.0 以上か
// return testVal * testVal * testVal >= 27.0;
return false; // ダミーの実装
}
// 実数二分探索テンプレート (精度 `epsilon` を使用)
double findRealValueByEpsilon(double low, double high, double epsilon) {
while (high - low > epsilon) { // 範囲の幅がepsilonより大きい間繰り返す
double mid = low + (high - low) / 2.0;
if (checkConditionDouble(mid)) {
high = mid; // mid は条件を満たす。答えは mid かそれより小さい範囲にある。
} else {
low = mid; // mid は条件を満たさない。答えは mid より大きい範囲にある。
}
}
return low; // または high (十分に近接しているためどちらでも良い)
}
もう一つの実数二分探索の方法として、固定回数のイテレーションを実行するテンプレートもあります。これにより、`double` 型の精度内で十分な近似解が得られます。
固定回数イテレーションを用いたテンプレート
#include <cmath> // std::abs のために必要
// checkConditionDouble関数は上記と同じものを使用
// 実数二分探索テンプレート (固定回数イテレーションを使用)
// 例: 100回繰り返すことで、通常、doubleの精度範囲内で十分な精度が得られます。
double findRealValueByIterations(double low, double high, int iterations = 100) {
for (int i = 0; i < iterations; ++i) {
double mid = low + (high - low) / 2.0;
if (checkConditionDouble(mid)) {
high = mid;
} else {
low = mid;
}
}
return low; // または high
}
例題
- 洛谷 P1024 [NOIP2001 提高组] 一元三次方程求解
STLによる二分探索
C++の標準ライブラリ（STL）には、ソート済み範囲に対する二分探索を行う便利な関数が提供されています。これらを利用するには、ヘッダファイル <algorithm> をインクルードします。
std::lower_bound(first, last, value): ソート済み範囲[first, last)において、value以上の値が初めて現れる位置へのイテレータを返します。std::upper_bound(first, last, value): ソート済み範囲[first, last)において、valueより大きい値が初めて現れる位置へのイテレータを返します（これは、valueが複数存在する場合にその最後のvalueの直後の位置を指します）。
例題: 洛谷 P1102 A - B = C
貪欲法
貪欲法（Greedy Algorithm）は、特定の問題を解決するための設計思想の一つです。このアプローチの基本的な考え方は、各段階でその時点での局所的な最適解を選択していくことで、最終的に問題全体の最適解が得られると推論することです。しかし、貪欲法が常に全体最適解を導くとは限らないため、その正当性を証明する必要があります。貪欲法の正当性を証明するには、反証法や数学的帰納法などがよく用いられます。