Open2
AtCoderメモ
iharu半分全探索
ここでは、半分全探索の一例として、配列の部分和問題を解くコードを示します。
配列が与えられたとき、その部分和が特定の値になる組み合わせが存在するかを探す問題です。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
// 前半部分を全列挙
vector<int> v;
for(int bit = 0; bit < (1<<(n/2)); bit++) {
int sum = 0;
for(int i = 0; i < n/2; i++) {
if(bit & (1<<i)) sum += a[i];
}
v.push_back(sum);
}
sort(v.begin(), v.end());
// 後半部分を全探索
bool ok = false;
for(int bit = 0; bit < (1<<(n-n/2)); bit++) {
int sum = 0;
for(int i = 0; i < n-n/2; i++) {
if(bit & (1<<i)) sum += a[i+n/2];
}
// 前半部分の配列中に、k-sumが存在するか二分探索
if(binary_search(v.begin(), v.end(), k-sum)) ok = true;
}
if(ok) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
このコードでは、まず配列を二つに分けます。それぞれの部分配列に対して全探索を行い、部分和を求めます。全探索の結果は、前半部分はvectorに格納され、ソートされます。後半部分の探索中に、目指す合計値からその部分和を引いた値が前半部分の結果の中に存在するかを二分探索します。存在すれば、その部分和の組み合わせが見つかったことになります。
このように半分全探索を用いることで、大きな問題も効率的に解くことが可能となります。
iharu三分探索（ternary search）は、単峰関数（一つだけ極大値または極小値を持つ関数）の最大値または最小値を見つけるための探索アルゴリズムです。区間を3つに分割し、その中央の2点で関数を評価します。関数の値に基づいて、次の探索範囲を決定します。これを繰り返すことで、極大値または極小値を持つ区間を効率的に特定することができます。
#include<bits/stdc++.h>
using namespace std;
double func(double x) {
// ここに目的の関数を定義する
return x * x; // 例としてx^2を返す関数
}
double ternary_search(double l, double r) {
for(int i = 0; i < 200; i++) { // 十分な回数ループを回す
double c1 = (l * 2 + r) / 3;
double c2 = (l + r * 2) / 3;
if(func(c1) < func(c2)) r = c2;
else l = c1;
}
return l; // 最小値を取るxを返す
}
int main() {
double l = -100, r = 100;
cout << ternary_search(l, r) << endl;
return 0;
}
このコードでは、三分探索を用いて関数func(x)が最小値を取るxを探しています。この例では、関数としてx^2を用いていますが、実際には最適化したい任意の関数をfunc(x)に定義します。三分探索は単峰関数（一つの山または谷を持つ関数）に対して、その最大値または最小値を効率よく見つけることができます。