import math
def combinations_count(n, r):
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))#include <functional>
#include <iostream>
void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
if (rest == 0) {
f(indexes);
} else {
if (s < 0) return;
recursive_comb(indexes, s - 1, rest, f);
indexes[rest - 1] = s;
recursive_comb(indexes, s - 1, rest - 1, f);
}
}
// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
int indexes[k];
recursive_comb(indexes, n - 1, k, f);
}
int main() {
foreach_comb(5, 3, [](int *indexes) {
std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << std::endl;
});
}#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 0~k-1のすべての組み合わせに対して処理を行う
void combination(int k, std::function<void(std::vector<int>)> f) {
for (int i = 0; i < (1 << k); i++) {
std::vector<int> nums;
for (int j = 0; j < k; j++) {
if ((1 << j) & i) nums.push_back(j);
}
f(nums);
}
}
int main() {
combination(2, [](std::vector<int> nums) {
for (int i = 0; i < nums.size(); i++) cout << nums[i] << " ";
cout << endl;
});
}import math
def permutations_count(n, r):
return math.factorial(n) // math.factorial(n - r)#include <algorithm>
#include <functional>
#include <iostream>
void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
if (rest == 0) {
f(indexes);
} else {
if (s < 0) return;
recursive_comb(indexes, s - 1, rest, f);
indexes[rest - 1] = s;
recursive_comb(indexes, s - 1, rest - 1, f);
}
}
// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
int indexes[k];
recursive_comb(indexes, n - 1, k, f);
}
// nPnの順列に対して処理を実行する
void foreach_permutation(int n, std::function<void(int *)> f) {
int indexes[n];
for (int i = 0; i < n; i++) indexes[i] = i;
do {
f(indexes);
} while (std::next_permutation(indexes, indexes + n));
}
// nPkの順列に対して処理を実行する
void foreach_permutation(int n, int k, std::function<void(int *)> f) {
foreach_comb(n, k, [&](int *c_indexes) {
foreach_permutation(k, [&](int *p_indexes) {
int indexes[k];
for (int i = 0; i < k; i++) {
indexes[i] = c_indexes[p_indexes[i]];
}
f(indexes);
});
});
}
int main() {
foreach_permutation(
4, 2, [](int *indexes) { std::cout << indexes[0] << ',' << indexes[1] << std::endl; });
}#include <algorithm>
#include <iostream>
int main() {
int nums[] = {9, 3, 4, 2, 6, 1, 7, 8, 5};
// 昇順
std::sort(nums, nums + 9);
// 降順
std::sort(nums, nums + 9, [](const int &a, const int &b) -> bool { return a > b; });
for (auto n : nums) { std::cout << n << ", "; }
std::cout << std::endl;
return 0;
}#include <functional>
#include <iostream>
#include <vector>
class UFTree {
private:
const int N; // 要素数
std::vector<int> par; // 各ノードの親のID（根ノードは自分を参照）
std::vector<int> sizes; // 各ノードを根とする木のサイズ（根でないノードには無関係）
public:
UFTree(int n) : par(n), sizes(n, 1), N(n) {
for (int i = 0; i < n; i++) par[i] = i;
}
// 要素xが属するグループの根ノードのIDを見つける
int find(int x) {
if (par[x] == x)
return x;
else
return par[x] = find(par[x]);
}
// 要素x, yが属するグループ同士を統合する
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (sizes[x] < sizes[y]) {
par[x] = y;
sizes[y] += sizes[x];
} else {
par[y] = x;
sizes[x] += sizes[y];
}
}
// グループのリストを表示する
// (IDが小さい順に表示される, O(n^2)なので最速の実装ではない)
void show() {
std::cout << "Groups : " << std::endl;
std::function<void(int)> f = [&](int x) {
std::cout << x << ',';
for (int y = 0; y < N; y++) {
if (par[y] == x && y != x) f(y);
}
};
for (int i = 0; i < N; i++) {
if (par[i] == i) {
f(i);
std::cout << std::endl;
}
}
}
// 要素x, yが同じグループに属するかどうか
bool same(int x, int y) { return find(x) == find(y); }
// 要素xが所属するグループに含まれる要素の数
int size(int x) { return sizes[find(x)]; }
};
int main() {
UFTree uf(5); // 0~4の5つの要素について
uf.unite(0, 2); // 0と2は同じグループ
uf.unite(2, 4); // 2と4は同じグループ
uf.unite(1, 3); // 1と3は同じグループ
// 1と2は同じグループ？
std::cout << "same(1, 2) : " << (uf.same(1, 2) ? "True" : "False") << std::endl;
// 3が所属するグループのメンバーの数は？
std::cout << "size(3) : " << uf.size(3) << std::endl;
// グループのリストを表示
uf.show();
return 0;
}O(V+E)の実装。
#include <algorithm>
#include <iostream>
#include <sstream>
#include <stack>
#include <vector>
int main() {
const int N = 7;
std::stringstream input;
input << "9\n"
"0 2\n"
"0 3\n"
"2 1\n"
"3 1\n"
"3 2\n"
"3 4\n"
"3 6\n"
"4 5\n"
"5 6";
int graph[N][N];
int indegrees[N];
std::vector<int> s2t[N];
for (int i = 0; i < N; i++) {
indegrees[i] = 0;
for (int j = 0; j < N; j++) { graph[i][j] = 0; }
}
int m;
input >> m;
for (int i = 0; i < m; i++) {
int s, t;
input >> s >> t;
graph[s][t] = 1;
s2t[s].push_back(t);
indegrees[t]++;
}
std::vector<int> topolo_order;
std::stack<int> st;
for (int i = 0; i < N; i++)
if (indegrees[i] == 0) st.push(i);
while (st.size() > 0) {
int i = st.top();
st.pop();
topolo_order.push_back(i);
while (s2t[i].size() > 0) {
int j = s2t[i].back();
s2t[i].pop_back();
indegrees[j]--;
if (indegrees[j] == 0) st.push(j);
}
}
if (topolo_order.size() != N) {
std::cout << "The graph is not DAG" << std::endl;
} else {
for (int i = 0; i < N; i++) { std::cout << topolo_order[i] << ", "; }
std::cout << std::endl;
}
}#include <functional>
#include <iostream>
#include <string>
using namespace std;
int main() {
const int H = 3, W = 3;
long map[H][W] = {{0, 1, 0}, {1, 1, 0}, {1, 0, 0}};
long table[H + 1][W + 1];
for (int i = 0; i < H + 1; i++) { table[i][0] = 0; }
for (int i = 0; i < W + 1; i++) { table[0][i] = 0; }
for (int i = 0; i < H; i++) {
long rsum = 0;
for (int j = 0; j < W; j++) {
rsum += map[i][j];
table[i + 1][j + 1] = rsum + table[i][j + 1];
}
}
// (y1+1,x1+1)~(y2,x2)の範囲の和
const function<long(int, int, int, int)> partsum = [&](int y1, int x1, int y2, int x2) -> long {
return table[y2][x2] + table[y1][x1] - table[y1][x2] - table[y2][x1];
};
cout << partsum(3, 3, 0, 0) << endl;
cout << partsum(2, 2, 1, 1) << endl;
}f(x)の呼び出し回数をlog nに抑えたupper_bound。
#include <algorithm>
#include <iostream>
using namespace std;
// 整数xに対して単調増加の関数f(x)について、k>=f(x)を満たす最大のxを求める
bool upper_bound_f(long k, long &x, long l_x, long r_x, function<long(long)> f) {
long l_val = f(l_x);
long r_val = f(r_x);
if (l_val >= k || r_val < k) return false;
while (r_x - l_x > 1) {
x = (l_x + r_x) / 2;
long val = f(x);
if (val <= k) {
l_x = x;
l_val = val;
} else {
r_x = x;
r_val = val;
}
}
return true;
}
int main() {
long data[] = {1, 2, 3, 4, 4, 6, 9, 10};
long x;
upper_bound_f(3, x, 0, 7, [&](long i) -> long { return data[i]; });
cout << x << " " << data[x] << endl;
}同じくlower_bound。
// 整数xに対して単調増加の関数f(x)について、k<=f(x)を満たす最小のxを求める
bool lower_bound_f(long k, long &x, long l_x, long r_x, function<long(long)> f) {
long l_val = f(l_x);
long r_val = f(r_x);
if (l_val >= k || r_val < k) return false;
while (r_x - l_x > 1) {
x = (l_x + r_x + 1) / 2;
long val = f(x);
if (val >= k) {
r_x = x;
r_val = val;
} else {
l_x = x;
l_val = val;
}
}
return true;
}log2(range/eps)の実装
// 実数xに対して単調増加の関数f(x)について、k<=f(x)を満たす最小のxをeps以下の精度で求める
bool lower_bound_f(double k, double &x, double l_x, double r_x, double eps,
function<double(double)> f) {
long l_val = f(l_x);
long r_val = f(r_x);
if (l_val >= k || r_val < k) return false;
while (abs(r_x - l_x) > eps) {
x = (l_x + r_x) / 2;
long val = f(x);
if (val >= k) {
r_x = x;
r_val = val;
} else {
l_x = x;
l_val = val;
}
}
return true;
}const double PI = 3.14159265358979323;
struct Point {
double x, y;
Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}
Point(const Point &p) : x(p.x), y(p.y) {}
friend std::ostream &operator<<(std::ostream &s, const Point &p) {
return s << '(' << p.x << ", " << p.y << ')';
}
};
inline Point operator+(const Point &p, const Point &q) { return Point(p.x + q.x, p.y + q.y); }
inline Point operator-(const Point &p, const Point &q) { return Point(p.x - q.x, p.y - q.y); }
inline Point operator*(const Point &p, double a) { return Point(p.x * a, p.y * a); }
inline Point operator*(double a, const Point &p) { return Point(a * p.x, a * p.y); }
inline Point operator/(const Point &p, double a) { return Point(p.x / a, p.y / a); }
inline Point rot(const Point &p, double ang) {
return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);
}
inline double dot(const Point &p, const Point &q) { return p.x * q.x + p.y * q.y; }
inline double norm(const Point &p) { return sqrt(dot(p, p)); }
inline double norm_sqrd(const Point &p) { return dot(p, p); }
struct Circle : Point {
double r;
Circle(const Point &p_, double r_ = 0) : Point(p_), r(r_) {}
friend ostream &operator<<(ostream &s, const Circle &c) {
return s << '(' << c.x << ", " << c.y << ", " << c.r << ')';
}
};
std::vector<Point> crosspoint(const Circle &e, const Circle &f, const double eps) {
std::vector<Point> res;
double d = norm(e - f);
if (d < eps) return vector<Point>();
if (d > e.r + f.r + eps) return vector<Point>();
if (d < abs(e.r - f.r) - eps) return vector<Point>();
double rcos = (d * d + e.r * e.r - f.r * f.r) / (2.0 * d), rsin;
if (e.r - abs(rcos) < eps)
rsin = 0;
else
rsin = sqrt(e.r * e.r - rcos * rcos);
Point dir = (f - e) / d;
Point p1 = e + Point(dir.x * rcos - dir.y * rsin, dir.x * rsin + dir.y * rcos);
Point p2 = e + Point(dir.x * rcos + dir.y * rsin, dir.x * -rsin + dir.y * rcos);
res.push_back(p1);
if (norm(p1 - p2) > eps) res.push_back(p2);
return res;
}