蟻本初級編まとめ

例題1-1-1 くじびき　joi2007本戦C
半分全列挙

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll 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);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	ll n, m; cin >> n >> m;
	vector<int>p;
	p.push_back(0);
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		p.push_back(a);
	}
	vector<int>key;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (m >= p[i] + p[j]) {
				key.push_back(p[i] + p[j]);
			}
		}
	}
	key.push_back(INF);
	sort(key.begin(), key.end());
	int ans = 0;
	for (int i = 0; i < key.size(); ++i) {
		int x = m - key[i];
		if (x < 0)continue;
		auto iter = upper_bound(key.begin(), key.end(), x);
		int X = iter - key.begin() - 1;
		ans = max(ans, key[i] + key[X]);
	}
	cout << ans << endl;
	return 0;
}
```

部分和問題
整数a1,,,anが与えられますその中からいくつか選びその和をちょうどkにすることができるかを判定しなさい

```
int a[21];
int n, k;
bool dfs(int i, int sum) {
	if (i== n)return sum == k;
	if (dfs(i + 1, sum))return true;
	if (dfs(i + 1, sum + a[i]))return true;
	return false;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i)cin >> a[i];
	if (dfs(0, 0))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}
```
abc 045 c たくさんの数式
https://atcoder.jp/contests/arc061/tasks/arc061_a

```
int main() {
	string S; cin >> S;
	ll ans = 0;
	ll tmp;
	for (int bit = 0; bit < (1<<(S.size()-1)); ++bit) {
		tmp = S[0] - '0';
		for (int i = 0; i < S.size()-1; ++i) {
			if (bit&(1 << i)) {
				ans += tmp;
				tmp = 0;
			}
			tmp = tmp * 10 + (S[i + 1] - '0');
		}
		ans += tmp;
	}
	cout << ans << endl;
	return 0;
}

```
若干書き方がだるかった
abc 104 c all green
https://atcoder.jp/contests/abc104/tasks/abc104_c
abc 002 d 派閥
https://atcoder.jp/contests/abc002/tasks/abc002_4

```
int main() {
	int N, M; cin >> N >> M;
	vector<vector<int>>v(N, vector<int>(N, 0));
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		x--, y--;
		v[x][y]++;
		v[y][x]++;
	}
	int ans = 0;
	for (int bit = 0; bit < (1 << N); ++bit) {
		bool ok = true;
		int cnt = 0;
		for (int i = 0; i < N; ++i) {
			if (bit&(1 << i)) {
				cnt++;
				for (int j = 0; j < N; ++j) {
					if (i == j)continue;
					if (!(bit&(1 << j)))continue;
					if (v[i][j] == 0)ok = false;
				}
			}
		}
		if (ok) {
			ans = max(ans, cnt);
		}
	}
	cout << ans << endl;
	return 0;
}
```
部分和問題
a1=anが与えられる。その中からいくつか選びその和をちょうどkとすることができるか判定せよ

```
int a[21];
int n, k;
bool dfs(int i, int sum) {
	if (i == n)return sum == k;
	if (dfs(i + 1, sum))return true;
	if (dfs(i + 1, sum + a[i]))return true;
	return  false;
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i)cin >> a[i];
	if (dfs(0, 0))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}
```
lake counting
全部でいくつの水たまりがあるか

```
int N, M;
char field[110][110];
void dfs(int x, int y) {
	//今いるところを.に書き換える
	field[x][y] = '.';
	//移動する8方向をループ
	for (int dx = -1; dx <= 1; ++dx) {
		for (int dy = -1; dy <= 1; ++dy) {
			int nx = x + dx, ny = y + dy;
			if (0 <= nx && nx < N && 0 <= ny && ny < M&&field[nx][ny] == 'W') {
				dfs(nx, ny);
			}
		}
	}
	return;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> field[i][j];
		}
	}
	int res = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (field[i][j] == 'W') {
				dfs(i, j);
				res++;
			}
		}
	}
	cout << res << endl;
	return 0;
}
```
arc 031 b 埋め立て

```
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
char A[11][11];
int used[11][11];//もう一つ配列を作る
void dfs(int y,int x) {
	if (y < 0 || y >= 10 || x < 0 || x >= 10) {
		return;
	}
	if (A[y][x] == 'x')return;
	if (used[y][x])return;
	used[y][x] = 1;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		dfs(ny, nx);
	}
}
int main() {
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10; ++j) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < 10 ; ++j) {
			memset(used, 0, sizeof(used));
			bool key = true;
			if (A[i][j] == 'x')key = false;
			A[i][j] = 'o';
			dfs(i, j);
			if (!key)A[i][j] = 'x';
			bool ok = true;
			for (int y = 0; y < 10; ++y) {
				for (int x = 0; x < 10; ++x) {
					if (A[y][x] == 'o'&&!used[y][x]) {
						ok = false;
					}
				}
			}
			if (ok) {
				cout << "YES" << endl;
				return 0;
			}
		}
	}
	cout << "NO" << endl;
	return 0;
}
```
配列をもう一つ用意して頑張る
arc 037 b バウムテスト

```
int N, M;
vector<vector<int>>G;
bool memo[110];
bool flag;
//前のやつを保存しておくという手法
void def(int a,int b) {
	memo[a] = true;
	for (auto i : G[a]) {
		if (i == b)continue;
		if (memo[i]) {
			flag = false;
		}
		else{
			def(i, a);
		}
	}
}
int main() {
	cin >> N >> M;
	G.resize(N);
	for (int i = 0; i < M; ++i){
		int u, v; cin >> u >> v;
		u--, v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 0; i < 110; ++i) {
		memo[i] = false;
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		if (!memo[i]) {
			flag = true;
			def(i, -1);
			if (flag) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```
この手のdfsにおいて、前に通った頂点を引数に持っておくというのは重要な考え方

幅優先探索
JOI 第十回　E　チーズ

```
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const ll INF = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
//1から順にNまで辿る最短経路
int H, W, N;
char C[1010][1010];
ll d[1010][1010];
ll ans = 0;
void def(int sy, int sx, int gy, int gx) {
	for (int i = 0; i < 1010; ++i) {
		for (int j = 0; j < 1010; ++j) {
			d[i][j] = INF;
		}
	}
	queue<pii>Q;
	Q.push({ sy,sx });
	d[sy][sx] = 0;
	while (!Q.empty()) {
		pii P;
		P = Q.front();
		Q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = P.first + dy[i];
			int nx = P.second + dx[i];
			if (C[ny][nx] != 'X'&&ny >= 0 && ny < H&&nx >= 0 && nx < W && d[ny][nx] == INF) {
				Q.push({ ny,nx });
				d[ny][nx] = d[P.first][P.second] + 1;
			}
		}
	}
	ans += d[gy][gx];
}
int main() {
	cin >> H >> W >> N;
	int sy, sx;
	vector<pair<int, pii>>x;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> C[i][j];
			if (C[i][j] != '.'&&C[i][j]!='X') {
				if (C[i][j] == 'S') {
					x.push_back({ 0,{i,j} });
				}
				else {
					x.push_back({ C[i][j] - '0',{i,j} });
				}
			}
		}
	}
	sort(x.begin(), x.end());
	for (int i = 0; i < x.size() - 1;++i) {
		def(x[i].second.first, x[i].second.second, x[i + 1].second.first, x[i + 1].second.second);
	}
	cout << ans << endl;
	return 0;
}
```
01BFS ARC005 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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
int H, W;
char C[510][510];
int sy, sx, gy, gx;
int d[510][510];
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> C[i][j];
			if (C[i][j] == 's')sy = i, sx = j;
			if (C[i][j] == 'g')gy = i, gx = j;
			d[i][j] = INF;
		}
	}
	deque<pii>Q;
	Q.push_back({ sy,sx });
	d[sy][sx] = 0;
	while (Q.size()) {
		pii p;
		p = Q.front();
		int y = p.first;
		int x = p.second;
		Q.pop_front();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < H&&nx >= 0 && nx < W) {
				bool wall = (C[y][x] == '#');
				int d2 = d[y][x] + wall;
				//暫定距離より短い経路が得られた場合は更新して+1なら後ろに+0なら前につける
				if (d[ny][nx] > d2) {
					d[ny][nx] = d2;
					if (wall) {
						Q.push_back({ ny,nx });
					}
					else {
						Q.push_front({ ny,nx });
					}
				}
			}
		}
	}
	if (d[gy][gx] <= 2) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}
```
joi 2007　合宿
http://algoogle.hadrori.jp/aoj/0503/
3**kの漸化式って常識か？

特殊な状態の列挙next_permutation
第９回情報オリ1問

```

2-4int n, k;
vector<string>N;
int main() {
	cin >> n >> k;
	N.resize(n);
	set<string>S;
	int ans = 0;
	for (int i = 0; i < n; ++i)cin >> N[i];
	sort(N.begin(), N.end());
	do {
		string res = "";
		for (int i = 0; i < k; ++i) {
			res += N[i];
		}
		S.insert(res);
	} while (next_permutation(N.begin(), N.end()));
	cout << S.size() << endl;
	return 0;
}
```
一般的なコイン問題
c1,,,cm円のm種類のコインを使ってn円を支払う時の最小枚数を求める


```
int n, m;
int c[21];
int dp[50010];//dp[i]でi円を支払う時の最小枚数
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i)cin >> c[i];
	for (int i = 0; i < 50010; ++i) {
		dp[i] = INF;
	}
	dp[0] = 0;
	for (int i = 0; i <= 50000; ++i) {
		for (int j = 0; j<m; ++j) {
			if (i + c[j] <= n) {
				dp[i + c[j]] = min(dp[i + c[j]], dp[i] + 1);
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}
```
-2 set,map
abc 091 B mapの初歩

```
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll 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);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////


int main() {
	int N, M;
	string s[101], t[101];
	cin >> N;
	for (int i = 0; i < N; ++i)cin >> s[i];
	cin >> M;
	for (int i = 0; i < M; ++i)cin >> t[i];
	map<string, int>ma;
	for (int i = 0; i < N; ++i) {
		ma[s[i]]++;
	}
	for (int i = 0; i < M; ++i) {
		ma[t[i]]--;
	}
	int ans = 0;
	for (auto itr = ma.begin(); itr != ma.end();++itr) {
		ans = max(ans, itr->second);
	}
	cout << ans << endl;
	return 0;
}
```

追加　divertaコン2のB問題

```
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll 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);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////


int main() {
	int N; cin >> N;
	if (N == 1) {
		cout << 1 << endl;
		return 0;
	}
	ll x[51], y[51];
	for (int i = 0; i < N; ++i) {
		cin >> x[i] >> y[i];
	}
	map<pair<ll, ll>, int>ma;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i == j)continue;
			pair<ll, ll> P = { x[i] - x[j],y[i] - y[j] };
			ma[P]++;
		}
	}
	int ans = 0;
	for (auto itr = ma.begin(); itr != ma.end(); ++itr) {
		ans = max(ans, itr->second);
	}
	cout << N-ans << endl;
	return 0;
}
```
abc137 c

```
int N;
int main() {
	cin >> N;
	vector<string>key(N);
	for (int i = 0; i < N; ++i) {
		string a; cin >> a;
		key[i] = a;
	}
	for (int i = 0; i < N; ++i)sort(key[i].begin(), key[i].end());
	map<string, int>ma;
	ll ans = 0;
	for (int i = 0; i < N; ++i) {
		if (ma[key[i]] > 0) {
			ans += ma[key[i]];
		}
		ma[key[i]]++;
	}
	cout << ans << endl;
	return 0;
}
```
同じものが何個あるかって数え上げにはこのやり方はかなり有効な気がする
abc 085 B setの初歩

```
#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>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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 ll dx[4] = { 0, -1, 1, 0 };
const ll 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);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////


int main() {
	int N; cin >> N;
	set<int>st;
	for (int i = 0; i < N; ++i) {
		int d; cin >> d;
		st.insert(d);
	}
	cout << st.size() << endl;
	return 0;
}
```

2-7 gcjの過去問に挑戦
minimum scalar product 2008 round1a a
2つのベクトルv1=(x1,x2,,,,xn)とv2=(y1,y2,,,yn)があります。v1とv2の成分の順番はそれぞれ自由に入れ替えられます。v1とv2の内積x1y1+,,,xnynの最小値を求めなさい

```
int main() {
    ll n; cin >> n;
	vector<ll>v1(n), v2(n);
	for (int i = 0; i < n; ++i)cin >> v1[i];
	for (int i = 0; i < n; ++i)cin >> v2[i];
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end(), greater<ll>());
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		ans += (ll)v1[i] * v2[i];
	}
	cout << ans << endl;
	return 0;
}
```
crazy rows 2009 round2 a

```
int n;
int m[51][51];
int a[51];//a[i]はi行目の最後に現れる1の位置-1<=a[i]<=N-1
int solve() {
	int res = 0;
	for (int i = 0; i < n; ++i) {
		a[i] = -1;
		for (int j = 0; j < n; ++j) {
			if (m[i][j] == 1)a[i] = j;
		}
	}
	for (int i = 0; i < n; ++i) {
		int pos = -1;//i行目に移動する行
		for (int j = i; j < n; ++j) {
			if (a[j] <= i) {
				pos = j;
				break;
			}
		}
		//実際にswapする
		for (int j = pos; j > i; --j) {
			swap(a[j], a[j - 1]);
			res++;
		}
	}
	return res;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> m[i][j];
		}
	}
	cout << solve() << endl;
	return 0;
}
```
bribe the prisoners (2009 round 1c c)
区間dp
※dp[i][j]をi人目の囚人からj人目の囚人まで(両端の囚人は含まない)の部分になったときにその中の囚人を全て解放するのに必要な金貨の最小枚数とする
※端を簡単に扱うため、0人目の囚人を左端、Q+1人目の囚人を右端としている。従ってdp[0][Q+1]が答えとなる。

```
int p, q, a[110];//aには1-indexedaでデータが入っている
//dp[i][j]:=(i,j)を解放するのに必要な金貨
int dp[110][110];
void solve() {
	a[0] = 0;//簡単のため端をAに追加する
	a[q + 1] = p + 1;
	//初期化
	for (int i = 0; i <= q; ++i) {
		dp[i][i + 1] = 0;
	}
	//端が小さい順にdpを埋めていく
	//幅
	for (int w = 2; w <= q + 1; ++w) {
		//左端
		for (int i = 0; i + w <= q + 1; ++i) {
			//右端
			int j = i + w;
			//2番目以降で解放に必要な金貨
			int t = INF;
			//全探索
			for (int k = i + 1; k < j; ++k) {
				t = min(t, dp[i][k] + dp[k][j]);
			}
			dp[i][j] = t + a[j] - a[i] - 2;
		}
	}

}
int main() {
	cin >> p >> q;
	for (int i = 1; i <= q; ++i)cin >> a[i];
	solve();
	cout << dp[0][q + 1] << endl;
	return 0;
}
```