paizaラーニングレベルアップ問題集をC++でやってみた

paiza×Qiita記事投稿キャンペーンということで、キャンペーン対象問題25問をC++で解いてみました。
- - -
###### [文字の一致](https://paiza.jp/works/mondai/d_rank_skillcheck_sample/diff_str)
```cpp
#include <iostream>
using namespace std;

int main() {
	string a;
	cin >> a;
	string b;
	cin >> b;
	cout << (a == b ? "OK" : "NG") << endl;
	return 0;
}
```
- - -
###### [一番小さい値](https://paiza.jp/works/mondai/d_rank_skillcheck_sample/min_num)
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector<int> n(5);
	for(int i = 0; i < 5; i++)
		cin >> n[i];
	cout << *min_element(n.begin(), n.end()) << endl;
	return 0;
}
```
- - -
###### [足し算](https://paiza.jp/works/mondai/d_rank_skillcheck_sample/addition)
```cpp
#include <iostream>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	cout << a + b << endl;
	return 0;
}
```
- - -
###### [Eメールアドレス](https://paiza.jp/works/mondai/d_rank_skillcheck_archive/email_address)
```cpp
#include <iostream>
using namespace std;

int main() {
	string s;
	cin >> s;
	string t;
	cin >> t;
	cout << s << "@" << t << endl;
	return 0;
}
```
- - -
###### [N倍の文字列](https://paiza.jp/works/mondai/d_rank_skillcheck_archive/square)
```cpp
#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	string s(N, '*');
	cout << s << endl;
	return 0;
}
```
- - -
###### [宝くじ](https://paiza.jp/works/mondai/c_rank_skillcheck_archive/lottery)
```cpp
#include <iostream>
using namespace std;

int main() {
	int b;
	cin >> b;
	int n;
	cin >> n;
	while (n--) {
		int a;
		cin >> a;
		if (a == b)
			cout << "first" << endl;
		else if (abs(a - b) == 1)
			cout << "adjacent" << endl;
		else if ((a - b) % 10000 == 0)
			cout << "second" << endl;
		else if ((a - b) % 1000 == 0)
			cout << "third" << endl;
		else
			cout << "blank" << endl;
	}
	return 0;
}
```
- - -
###### [野球の審判](https://paiza.jp/works/mondai/c_rank_skillcheck_archive/umpire)
```cpp
#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int strike = 0;
	int ball = 0;
	while (n--) {
		string s;
		cin >> s;
		if (s == "strike")
			if (++strike == 3)
				cout << "out!" << endl;
			else
				cout << "strike!" << endl;
		else if (s == "ball")
			if (++ball == 4)
				cout << "fourball!" << endl;
			else
				cout << "ball!" << endl;
	}
	return 0;
}
```
- - -
###### [みかんの仕分け](https://paiza.jp/works/mondai/c_rank_skillcheck_archive/mikan)
```cpp
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	while (m--) {
		int w;
		cin >> w;
		cout << max((w + n / 2) / n, 1) * n << endl;
	}
	return 0;
}
```
- - -
###### [Fizz Buzz](https://paiza.jp/works/mondai/c_rank_skillcheck_sample/fizz-buzz)
```cpp
#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		if (i % 3 && i % 5)
			cout << i << endl;
		else if (i % 5)
			cout << "Fizz" << endl;
		else if (i % 3)
			cout << "Buzz" << endl;
		else
			cout << "Fizz Buzz" << endl;
	return 0;
}
```
- - -
###### [残り物の量](https://paiza.jp/works/mondai/c_rank_skillcheck_archive/leftover)
```cpp
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	double m, p, q;
	cin >> m >> p >> q;
	cout << setprecision(7) << m * (100 - p) * (100 - q) / 10000 << endl;
	return 0;
}
```
- - -
###### [3Dプリンタ](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/3d_printer)
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int X, Y, Z;
	cin >> X >> Y >> Z;
	vector<vector<string>> s(Z, vector<string>(X));
	for (int z = 0; z < Z; z++) {
		for (int x = 0; x < X; x++)
			cin >> s[z][x];
		string bar;
		cin >> bar;
	}
	while (Z--) {
		for (int y = 0; y < Y; y++) {
			char c = '.';
			for (int x = 0; x < X; x++) {
				if (s[Z][x][y] == '#') {
					c = '#';
					break;
				}
			}
			cout << c;
		}
		cout << endl;
	}
	return 0;
}
```
- - -
###### [神経衰弱](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/concentration)
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int H, W, N;
	cin >> H >> W >> N;
	vector<vector<string>> t(H, vector<string>(W));
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> t[i][j];
	int P = 0;
	vector<int> C(N, 0);
	int L;
	cin >> L;
	while (L--) {
		int a, b, A, B;
		cin >> a >> b >> A >> B;
		if (t[--a][--b] == t[--A][--B])
			C[P] += 2;
		else
			P = -~P % N;
	}
	for (int i = 0; i < N; i++)
		cout << C[i] << endl;
	return 0;
}
```
- - -
###### [みんなでしりとり](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/word_chain)
```cpp
#include <iostream>
#include <unordered_set>
#include <set>
using namespace std;

int main() {
	int N, K, M;
	cin >> N >> K >> M;
	unordered_set<string> d;
	while (K--) {
		string s;
		cin >> s;
		d.insert(s);
	}
	set<int> alive;
	for (int i = 1; i <= N; i++)
		alive.insert(i);
	int P = 1;
	string bef = "";
	while (M--) {
		string s;
		cin >> s;
		if (d.count(s) && (!bef.size() || bef[~-bef.size()] == s[0]) && s[~-s.size()] != 'z') {
			d.erase(s);
			bef = s;
		} else {
			alive.erase(P);
			bef = "";
		}
		do {
			P = -~(P % N);
		} while (!alive.count(P));
	}
	cout << alive.size() << endl;
	for (int i : alive)
		cout << i << endl;
	return 0;
}
```
- - -
###### [長テーブルのうなぎ屋](https://paiza.jp/works/mondai/b_rank_skillcheck_sample/long-table)
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<bool> seats(n, false);
	int ans = 0;
	while (m--) {
		int a, b;
		cin >> a >> b;
		bool can_sit = true;
		for (int i = 0; i < a; i++) {
			if (seats[(b + i) % n]) {
				can_sit = false;
				break;
			}
		}
		if (can_sit) {
			for (int i = 0; i < a; i++)
				seats[(b + i) % n] = true;
			ans += a;
		}
	}
	cout << ans << endl;
	return 0;
}
```
- - -
###### [名刺バインダー管理](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/name_card)
```cpp
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	cout << 2 * n * ((m - 1) / (2 * n) * 2 + 1) + 1 - m << endl;
	return 0;
}
```
- - -
###### [本の整理](https://paiza.jp/works/mondai/real_event/book_sort)
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> A(-~N);
	vector<int> B(-~N);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		B[A[i]] = i;
	}
	int c = 0;
	for (int i = 1; i <= N; i++) {
		if (A[i] != i) {
			B[A[i]] = B[i];
			A[B[i]] = A[i];
			c++;
		}
	}
	cout << c << endl;
	return 0;
}
```
- - -
###### [山折り谷折り](https://paiza.jp/works/mondai/real_event/origami)
```cpp
#include <iostream>
using namespace std;

string reverse(const string& s) {
	string t = "";
	int n = (int) s.size();
	while (n--)
		t += ('0' + '1' - s[n]);
	return t;
}

string origami(int n) {
	if (!n)
		return "";
	string s = origami(~-n);
	return s + '0' + reverse(s);
}

int main() {
	int N;
	cin >> N;
	cout << origami(N) << endl;
	return 0;
}
```
- - -
###### [ハノイの塔](https://paiza.jp/works/mondai/real_event/hanoi)
```cpp
#include <iostream>
#include <vector>
using namespace std;

void hanoi(int n, int& t, vector<int>& src, vector<int>& dst, vector<int>& tmp) {
	if (!t)
		return;
	if (n == 1) {
		dst.push_back(src.back());
		src.pop_back();
		if (!(--t))
			return;
	} else {
		hanoi(~-n, t, src, tmp, dst);
		hanoi(1, t, src, dst, tmp);
		hanoi(~-n, t, tmp, dst, src);
	}
}

int main() {
	int n, t;
	cin >> n >> t;
	vector<vector<int>> piles(3, vector<int>());
	for (int i = n; i > 0; i--)
		piles[0].push_back(i);
	hanoi(n, t, piles[0], piles[2], piles[1]);
	for (vector<int> pile : piles) {
		if (pile.empty()) {
			cout << "-";
		} else {
            cout << pile[0];
			for (int i = 1; i < pile.size(); i++) {
				cout << ' ' << pile[i];
			}
		}
		cout << endl;
	}
	return 0;
}
```
- - -
###### [じゃんけんの手の出し方](https://paiza.jp/works/mondai/a_rank_skillcheck_sample/janken)
```cpp
#include <iostream>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	string s;
	cin >> s;
	int G = 0;
	int C = 0;
	int P = 0;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'G') G++;
		else if (s[i] == 'C') C++;
		else if (s[i] == 'P') P++;
	}

	int ans = 0;
	for (int p = M % 2; p <= M / 5; p+=2) {
		int c = (M - 5 * p) / 2;
		if (c > N) continue;
		int g = N - c - p;
		if (g < 0) continue;
		ans = max(ans, min(g, C) + min(c, P) + min(p, G));
	}
	cout << ans << endl;
	return 0;
}
```
- - -
###### [お菓子の詰め合わせ](https://paiza.jp/works/mondai/a_rank_skillcheck_archive/school_hiking)
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int X;
vector<int> x;
int M = 0;

int dfs(vector<int>& A, int amount) {
	if ((int) A.size() == M) {
		if (amount <= X)
			return amount;
		else
			return -1;
	} else {
		int res = 0;
		for (int i = (A.empty() ? 0 : -~A.back()); i < N; i++) {
			A.push_back(i);
			res = max(res, dfs(A, amount + x[i]));
			A.pop_back();
		}
		return res;
	}
}

int main() {
	cin >> N >> X;
	x.resize(N);
	for (int i = 0; i < N; i++)
		cin >> x[i];
	sort(x.begin(), x.end());
	int S = 0;
	while (M < N) {
		S += x[M];
		if (S > X)
			break;
		M++;
	}
	vector<int> A;
	cout << X - dfs(A, 0) << endl;
	return 0;
}
```
- - -
###### [十億連勝](https://paiza.jp/works/mondai/real_event/continuous_winning)
```cpp
#include <iostream>
#include <vector>
#include <map>
#include <utility>
using namespace std;

const long MOD = 1000000000;
const vector<bool>& B = {false, true};

int main() {
	int N, X;
	cin >> N >> X;
	vector<map<int, long>> states(2);
	states[0][0] = 1L;
	while (N--) {
		int a;
		cin >> a;
		vector<map<int, long>> temp(2);
		for (bool b : B) {
			for (pair<int, long> p : states[b]) {
				int w = p.first;
				if (w + a <= X) {
					temp[b][w + a] = (temp[b][w + a] + p.second) % MOD;
					temp[b][0] = (temp[b][0] + a * p.second) % MOD;
				} else {
					temp[1][0] = (temp[1][0] + p.second) % MOD;
					temp[b][0] = (temp[b][0] + (X - w) * p.second) % MOD;
				}
			}
		}
		states = temp;
	}
	long ans = states[0][X];
	for(pair<int, long> p : states[1])
		ans = (ans + p.second) % MOD;
	cout << ans << endl;
	return 0;
}
```
- - -
###### [文字列収集](https://paiza.jp/works/mondai/real_event/word_collection)
```cpp
#include <iostream>
#include <map>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	map<string, int> dict;
	while (N--) {
		string s;
		int p;
		cin >> s >> p;
		int l = (int) s.size();
		for (int i = 1; i <= l; i++)
			dict[s.substr(0, i)] += p;
	}
	while (M--) {
		string q;
		cin >> q;
		cout << dict[q] << endl;
	}
	return 0;
}
```
- - -
###### [mod7占い](https://paiza.jp/works/mondai/s_rank_skillcheck_sample/mod7)
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<long> C(7, 0L);
	while (N--) {
		long a;
		cin >> a;
		C[a % 7]++;
	}
	long ans = 0;
	for (int i = 0; i < 7; i++) {
		for (int j = i; j < 7; j++) {
			int k = (14 - i - j) % 7;
			if (k < j) continue;
			if (i == j && j == k)
				ans += C[i] * (C[i] - 1) * (C[i] - 2) / 6;
			else if (i == j)
				ans += C[i] * (C[i] - 1) * C[k] / 2;
			else if (j == k)
				ans += C[i] * C[j] * (C[j] - 1) / 2;
			else
				ans += C[i] * C[j] * C[k];
		}
	}
	cout << ans << endl;
	return 0;
}
```
- - -
###### [島探し](https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island)
```cpp
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

const vector<pair<int, int>>& D = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

void dfs(vector<vector<bool>>& A, int y, int x) {
	A[y][x] = false;
	for (pair<int, int> d : D) {
		int i = y + d.first;
		int j = x + d.second;
		if(0 <= i && i < (int) A.size() && 0 <= j && j < (int) A[i].size() && A[i][j])
			dfs(A, i, j);
	}
}

int main() {
	int M, N;
	cin >> M >> N;
	vector<vector<bool>> A(N, vector<bool>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int a;
			cin >> a;
			A[i][j] = (bool) a;
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (A[i][j]) {
				dfs(A, i, j);
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```
- - -
###### [村人の友好関係](https://paiza.jp/works/mondai/s_rank_skillcheck_archive/group_popularity)
```cpp
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <tuple>
#include <unordered_set>
using namespace std;

int root(vector<int>& A, int i) {
	if (A[i] < 0)
		return i;
	A[i] = root(A, A[i]);
	return A[i];
}

bool unite(vector<int>& A, int v, int u) {
	int rv = root(A, v);
	int ru = root(A, u);
	if (rv == ru)
		return false;
	if (A[rv] > A[ru]) {
		A[rv] = ru;
	} else {
		if (A[rv] == A[ru]) {
			A[rv]--;
		}
		A[ru] = rv;
	}
	return true;
}

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	priority_queue<pair<int, pair<int, int>>> PQ;
	while (M--) {
		int a, b, f;
		cin >> a >> b >> f;
		PQ.push({ f, { a, b } });
	}
	vector<pair<int, pair<int, int>>> MST;
	vector<int> A(N, -1);
	while(!PQ.empty()) {
		pair<int, pair<int, int>> e = PQ.top();
		PQ.pop();
		int a, b;
		tie(a, b) = e.second;
		if (unite(A, --a, --b))
			MST.push_back(e);
	}
	unordered_set<int> S;
	while (Q--) {
		char op;
		int q;
		cin >> op >> q;
		if (op == '+')
			S.insert(q);
		else if (op == '-')
			S.erase(q);
		int p = 0;
		for (pair<int, pair<int, int>> e : MST) {
			int f = e.first;
			int a = e.second.first;
			int b = e.second.second;
			if (S.count(a) != S.count(b)) {
				p = f;
				break;
			}
		}
		cout << p << endl;
	}
	return 0;
}
```