再帰練習

ABC 015-C

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int N, K;
int T[10][10];
bool flag;
void dfs(int i, int x) {
	if (i == N) {
		if (x == 0)flag = true;
		return;
	}
	for (int m = 0; m < K; ++m) {
		dfs(i + 1, x^T[i][m]);
	}
}
int main() {
	cin >> N >> K;
	flag = false;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			cin >> T[i][j];
		}
	}
	dfs(0, 0);
	if (flag){
		cout << "Found" << endl;
	}
	else {
		cout << "Nothing" << endl;
	}
	return 0;
}

```

abc 119-c

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int N, A, B, C;
vector<int>l;
int rec(int i, int a, int b, int c) {
	if (i == N) {
		if (!a || !b || !c)return INF;//A,B,Cいずれも竹は1本は必ず使ってないとダメ
		return abs(a - A) + abs(b - B) + abs(c - C);
	}
	//今ある竹を採用しない場合
	int res = rec(i + 1, a, b, c);
	//A,B,Cを使う場合
	//(a?10:0)とかは最初の１本目は合体コストなし2本目からはコスト10
	chmin(res, rec(i + 1, a + l[i], b, c) + (a ? 10 : 0));
	chmin(res, rec(i + 1, a, b + l[i], c) + (b ? 10 : 0));
	chmin(res, rec(i + 1, a, b, c + l[i]) + (c ? 10 : 0));

	return res;
}
int main() {
	cin >> N >> A >> B >> C;
	l.resize(N);
	REP(i, N)cin >> l[i];
	cout << rec(0, 0, 0, 0) << endl;
	return 0;
}
```

abc114-c

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int N;
int ans;
void rec(int x) {
	if (x>N)return;
	int num[10] = {};
	int t = x;
	while (t > 0) {
		num[t % 10]++;
		t /= 10;
	}
	if (num[3] && num[5] && num[7]) {
		ans++;
	}
	rec(x* 10 + 3);
	rec(x * 10 + 5);
	rec(x * 10 + 7);
}
int main() {
	ans = 0;
	cin >> N;
	rec(0);
	cout << ans << endl;
	return 0;
}
```
TLE.....

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N;
vector<ll>v;//nが条件を満たす場合vに入れるkは桁数
void dfs(ll n, ll k) {
	if (k > 1e9)return;
	int f[10] = {}, t = n;
	while (t) {
		f[t % 10]++;
		t /= 10;
	}
	if (f[3] && f[5] && f[7])v.push_back(n);
	dfs(n + 3 * k, k * 10);
	dfs(n + 5 * k, k * 10);
	dfs(n + 7 * k, k * 10);
}
int main() {
	int N;
	cin >> N;
	dfs(0, 1);
	sort(v.begin(), v.end());
	ll i = 0;
	int ans = 0;
	for (; i < v.size(); ++i) {
		if (v[i] > N)break;
		ans++;
	}
	cout << ans << endl;
	return 0;
}
```
これだと大丈夫だけど違いがよくわからん
abc119 C

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int N, A, B, C;
int l[10];
int d[10];
int def(int n) {
	if (n == N) {
		int p = 0, q = 0, r = 0;
		int cost = 0;
		for (int i = 0; i < N; ++i) {
			if (d[i] == 1) {
				if (p > 0)cost += 10;
				p+=l[i];
			}
			else if (d[i] == 2) {
				if (q > 0)cost += 10;
				q+=l[i];
			}
			else if (d[i] == 3) {
				if (r > 0)cost += 10;
				r+=l[i];
			}
		}
		if (p*q*r == 0)return INF;
		else return cost + abs(A - p) + abs(B - q) + abs(C - r);
	}
	int r = INF;
	for (int i = 0; i <= 3; ++i) {
		d[n] = i;
		r = min(r, def(n + 1));
	}
	return r;
}
int main() {
	cin >> N >> A >> B >> C;
	REP(i, N)cin >> l[i];
	cout << def(0)<< endl;
	return 0;
}
```

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int N, A, B, C;
int l[1000];
int ans = 1e9;
void dfs(int n, int a, int b, int c, int s) {
	if (n == N) {
		if (a != 0 && b != 0 && c != 0) {
			int t = s - 30;
			t += abs(a - A) + abs(b - B) + abs(c - C);
			ans = min(ans, t);
		}
		return;
	}
	dfs(n + 1, a, b, c, s);
	dfs(n + 1, a + l[n], b , c, s + 10);
	dfs(n + 1, a, b + l[n], c, s + 10);
	dfs(n + 1, a, b, c + l[n], s + 10);
}
int main() {
	cin >> N >> A >> B >> C;
	for (int i = 0; i < N; ++i) {
		cin >> l[i];
	}
	dfs(0, 0, 0, 0, 0);
	cout << ans << endl;
	return 0;
}
```
こっちのがしっくりくるな。voidのほうが好き