アルゴリズム始めた

とりあえず暇なので今日から何かと役立ちそうな競技プログラミングの勉強を始めてみようと思う。僕は記憶力がとても悪いからやった問題をブログに残しておくことでぼちぼち覚えられたらいいなっておもう。とりあえず初歩っぽい奴らを。著名なひとのブログを写すだけだけど。
（１）二つの正整数a,bが与えられますaとbの積が偶数か奇数か判定せよ
[制約]
.1≤a,b≤10000
.a,bは整数
[解法]
.特にない

```
　　#include<iostream>
    using namespace std;

    int main() {
	int a, b;
	cin >> a >>b;
	int c = a * b;
	if (c % 2 == 0)cout << "Even";
	else cout << "Odd";
	return 0;
    }
```
a人をb人ずつグループに分けると何グループできるかは、まとめると(a+b-1)/bで表記できてこれは後々使えるらしい

(2)０と１からのみ成る３桁の番号sが与えられます。１が何個含まれるかを求めよ
[解法]
for文を使わない程度の全探索

```
#include<iostream>
#include<string>
using namespace std;

int main() {
	string s;
	cin >> s;
	int counter = 0;
	if (s[0] == '1')++counter;
	if (s[1] == '1')++counter;
	if (s[2] == '1')++counter;
	cout << counter << endl;
	return 0;
}
```
string型の時はs[0]とかはint型じゃないことに注意
(3)
黒板にn個の正の整数A1,...,Anが書かれています。すぬけ君は、黒板に書かれている整数がすべて偶数である時、次の操作を行うことができる。
・黒板に書かれている整数すべてを、２で割ったものに置き換える。
すぬけ君は最大で何回操作を行うことができるか？
[制約]
・１≤ｎ≤２００
・１≤Ai≤10**9
for文の利用。

```
#include<iostream>
using namespace std;
int n;
int A[210]; //最大200なので余裕を持って210

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> A[i];

	int res = 0;
	
	//操作が行える限り操作を繰り返す
	while (true) {
		bool exist_odd = false;
		for (int i = 0; i < n; ++i) {
			if (A[i] % 2 != 0) exist_odd = true;
		}
		if (exist_odd) break;//奇数があったらbreak

		//操作を行えるなら操作を実際に行う
		for (int i = 0; i < n; ++i) {
			A[i] /= 2;
		}
		++res; //操作回数をインクリメント
	}

	cout << res << endl;
	return 0;
}
```
繰り返しは次の順序で行われる
1,初期化
2,継続条件の検査
3,文の実行
4,増分処理
5,2へ
まずは操作が行えるかどうかを判定する。行えないならbreakで操作終了。行えるなら実際に行い回数をインクリメント

(4)
５００円玉をA枚、１００円玉をB枚、５０円玉をC枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りあるでしょうか？
[制約]
.0≤A,B,C≤50
.A+B+C≧１
.50≤X≤20000
.A,B,Cは整数である
.Xは５０の倍数である
[解法]
.二重、三重のfor文

```
#include<iostream>
using namespace std;
int main() {
	int A, B, C, X;
	cin >> A >> B >> C >> X;
	int res = 0;
	for (int a = 0; a <= A; ++a) {
		for (int b = 0; b <= B; ++b) {
			for (int c = 0; c <= C;++c) {
				int total = 500 * a + 100 * b + 50 * c;
				if (total == X)++res;
			}
		}
	}
	cout << res << endl;
	return 0;
}
```

(5)
1以上N以下の整数のうち、１０進法で各桁の和がA以上B以下であるものについて、総和を求めよ
[制約]
.1≤N≤10**4
.1≤A≤B≤36
.入力はすべて整数
[解法]
.整数の１０進法表記の扱い方
.for文

```
#include<iostream>
using namespace std;
int findsumofdigits(int n) {
	int sum = 0;
	while (n > 0) {
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	int total = 0;
	for (int i = 1; i <= N; ++i) {
		int sum = findsumofdigits(i);
		if (sum >= A && sum <= B) {
			total += i;
		}
	}
	cout << total << endl;
	return 0;
}
```
まず総和を計算する関数を定義する。
こういうの慣れていきたいな
(6)
N 枚のカードがあり、i 枚目のカードには Ai という数が書かれています。Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。
[制約]
.Nは１以上１００以下の整数
.Aiは１以上１００以下の整数
[解法]
ソートをする。

```
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	int N;
	int a[110];
	cin >> N;
	for (int i = 0; i < N; i++)cin >> a[i];
	sort(a, a + N, greater<int>());//a[0:N]を大きい順にソート
	int Alice = 0;
	int Bob = 0;
	for (int i = 0; i < N; ++i) {
		if (i % 2 == 0) {
			Alice += a[i];
		}
		else {
			Bob += a[i];
		}
	}
	cout << Alice - Bob << endl;
	return 0;
}
```
greater<int>()を付けないと小さい順に並べられてしまうから。a[0:N]をsort(a,a+N)でソートする。includeするのはalgorithm

(7)
N個の整数 d[0],d[1],…,d[N−1]が与えられます。この中に何種類の異なる値があるでしょうか？
【制約】
.1≤N≤100
.1≤d[i]≤100
.入力値はすべて整数
[解法]
配列numを用意しておいて、num[i] :=　値iが何個あるか

```
//バケット法による解
#include<iostream>
using namespace std;

int main() {
	int N;
	int d[110];
	cin >> N;
	for (int i = 0; i < N; ++i)cin >> d[i];

	int num[110] = { 0 };
	for (int i = 0; i < N; ++i) {
		num[d[i]]++;
	}
	int res = 0;
	for (int i = 1; i <= 100; ++i) {
		if (num[i]) {
			++res;
		}
	}
	cout << res << endl;
	return 0;
}
```
値iが何個あるかをnum[i]で表すことがポイント。最後は何個の値があるかをresで表す。
(8)
10000 円札と、5000 円札と、1000 円札が合計でN枚あって、合計金額がY円であったという。このような条件を満たす各金額の札の枚数の組を1つ求めなさい。そのような状況が存在し得ない場合には-1-1-1と出力しなさい。
【制約】
.1≤N≤2000
.1000≤Y≤2∗10**7
.Nは整数
.Yは1000の倍数
[解法]
全探索すると、
for (int a = 0; a <= N; ++a) {
　for (int b = 0; b <= N; ++b) {
　　for (int c = 0; c <= N; ++c) {
　　　int total = 10000*a + 5000*b + 1000*c;
　　　if (a + b + c == N && total == Y) {
　　　　見つかった！
　　　}
　　}
　}
}
だがこれだと計算時間がかかりすぎる。
一分間で処理できるfor文ループの回数は10**8回程度。
ここで、a,bが決まればc=N-a-bと自動的に決まることに着目する

```
#include<iostream>
using namespace std;

int main() {
	int N, Y;
	cin >> N >> Y;
	int res10000 = -1, res5000 = -1, res1000 = -1;
	for (int a = 0; a <= N; ++a) {
		for (int b = 0; b <= N-a; ++b) {
			int c = N - a - b;
			int total = 10000 * a + 5000 * b + 1000 * c;
			if (total == Y) {
				res10000 = a;
				res5000 = b;
				res1000 = c;
			}
		}
	}
	cout << res10000 << " " << res5000 << " " << res1000 << endl;
	return 0;
}
```

(9)
英小文字からなる文字列Sが与えられます。
Tが空文字列である状態から始めて、以下の操作を好きな回数繰り返すことでS=Tとすることができるか判定してください。

.Tの末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。
【制約】

.1≤|S|≤10**5
.Sは英小文字からなる
[解法]
端っこから順に考えると芋づる式に全体が決まっていく。後ろから考えるとやりやすい

```
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string divide[4] = { "dream","dreamer","erase","eraser" };
int main() {
	string S;
	cin >> S;
	reverse(S.begin(), S.end());//全ての文字列を左右反転する
	for (int i = 0; i < 4; ++i) 
		reverse(divide[i].begin(),divide[i].end());
	bool can = true;
	for (int i = 0; i < S.size();) {
		bool can2 = false;
		for (int j = 0; j < 4; j++) {
			string d = divide[j];
			if (S.substr(i, d.size()) == d) {
				can2 = true;
				i += d.size();
			}
		}
		if (!can2) {
			can = false;
			break;
		}
	}

	if (can)cout << "Yes" << endl;
	else cout << "NO" << endl;
	return 0;
}
```
substr関数を使うには<string>ライブラリをインクルードする必要があるstr.string(開始位置,取り出す長さ)で文字列を取り出せる。これを利用する

(10)
シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻0に 点 (0,0)を出発し、1以上N以下の各iに対し、時刻tiに点(xi,yi)を訪れる予定です。

AtCoDeer くんが時刻tに点(x,y)にいる時、時刻t+1には点　(x+1,y),(x−1,y),(x,y+1),(x,y−1) のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

【制約】

.1≤N≤10**5
.0≤xi,yi≤10**5
.1≤ti≤ti+1≤105
.入力はすべて整数
[解法]
偶奇に注目

```
#include<iostream>
using namespace std;

int main() {
	int N;
	int t[110000], x[110000], y[110000];
	cin >> N;
	t[0] = x[0] = y[0] = 0;
	for (int i = 0; i < N; ++i)
		cin >> t[i + 1] >> x[i + 1] >> y[i + 1];
	bool can = true;
	for (int i = 0; i < N; ++i) {
		int dt = t[i + 1] - t[i];
		int dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		if (dt < dist) can = false;
		if (dist % 2 != dt % 2)can = false;
	}
	if (can)cout << "Yes" << endl;
	else cout << "No" << endl;
		return 0;
}
```

[i+1]-[i]をfor(int i=0;i<N;++i)でしらみつぶして、偶奇を考える。

最初はこんなもん