AtCoderの基礎問題を解いてみました(解答例あり)

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int a, b, c;
	string s;

	cin >> a;
	cin >> b >> c;
	cin >> s;

	cout << (a + b + c) << " " << s << endl;

	return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int a, b;

	cin >> a >> b;

	if ((a * b) % 2 == 0) {
		cout << "Even" << endl;
	}
	else {
		cout << "Odd" << endl;
	}

	return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int ans = 0;
	string s;

	cin >> s;

	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '1') {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

入力例を見ると、区切りなしの一行で入力されるので文字列で受け取っています。
3桁固定のため、整数で受け取っても問題ありません。

例のように文字列で解答する場合は、1文字ずつ取り出して「1」の数を数えていきます。

数値で解答する場合は、1の位を比較して10分の1していく作業を3回繰り返せば解けそうです。

1. 「101」の 1の位を&演算すると1が残るため、カウントする
2. 「101」を10で割ると、「10」(整数型のため端数切り捨て)が得られる
3. 「10」の1の位を&演算すると0になるため、カウントしない
4. 「10」を10で割ると、「1」が得られる
5. 「1」を&演算すると1が残るため、カウントする
6. カウントが2のため「2」を出力する

ループの方がきれいですが、3桁程度であれば手書きでも現実的な範囲です。

#include <iostream>
#include <string>

using namespace std;

const int LEN = 200;

int main()
{
	int N;
	int A[LEN];
	int ans = 0;

	cin >> N;

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

	while (1) {
		bool is_odd = false;

		for (int i = 0; i < N; i++) {
			if ((A[i] & 1) == 0b1) {
				is_odd = true;
				break;
			}
			else {
				A[i] = A[i] >> 1;
			}
		}

		if (is_odd) {
			break;
		}
		else {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

数学的には各入力を素因数分解できれば、最も2の項の少ないものが解答になります。

解答例ではビット演算をしていますが、剰余算と10で割っていっても同じです。
いずれにしても、2で割り切れなくなるまでループすればOKとなります。

[注意]
入力制約でNが1以上、A[i]も1以上ですが、N=0または A[i], A[i + 1], A[i + …], A[i + N]=0のどちらでも無限ループします。

#include <iostream>
#include <string>

using namespace std;

const int LEN = 200;

int main()
{
	int N;
	int A[LEN];
	int ans = 0;

	cin >> N;

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

	while (1) {
		bool is_odd = false;

		for (int i = 0; i < N; i++) {
			if ((A[i] & 1) == 0b1) {
				is_odd = true;
				break;
			}
			else {
				A[i] = A[i] >> 1;
			}
		}

		if (is_odd) {
			break;
		}
		else {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

この問題では、それぞれの硬貨を考えるためそれぞれの入力枚数分までループさせています。
また、例えば50円硬貨が2枚までとした場合は0〜2枚までが考えられるため、ループ条件には「<=」(以下)を指定しています。

解答の条件がぴったりなので、合計が一致したら内側のループをbreakしています。
計算量が幾ばくか減る程度でなくても問題はありません。

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int sum = 0;
	int N, A, B;
	cin >> N >> A >> B;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < 10; k++) {
				for (int l = 0; l < 10; l++) {
					for (int m = 0; m < 10; m++) {
						int val = m + l * 10 + k * 100 + j * 1000 + i * 10000;
						int digit_sum = i + j + k + l + m;
						if (val <= N) {
							if (A <= digit_sum && digit_sum <= B) {
								sum += val;
							}
						}
					}
				}
			}
		}
	}

	cout << sum << endl;

	return 0;
}

この問題は力技で解きました。
10進数で10^4までなので、時間制限は気にしなくていいです。
あまり考えずに一番外側のループをi <= 10にしていますが、i <= 1の方が無駄がないですね。

一番外側iのループが1万の位、jが千の位、kが百、lが十、mが一と続きます。
各桁の総和(digit_sum)は位ごとに分解してループさせ、解答に使う合計(val)の方を計算で求めています。
メモリの消費量を考えると、合計(val)の方は変数化せずにif内で直接計算した方が効率的です。

他の方の解答をみますと、Nまでをループさせて、各桁の総和を1桁ずつ割り戻しているものが多かったと思います。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int LEN = 100;

int main()
{
	int N;
	int A[LEN] = { 0 };
	int Alice = 0, Bob = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A, A + N, greater<int>());

	int i = 0, counter = 0;
	while(i < N / 2) {
		Alice += A[counter];
		Bob += A[counter + 1];
		i++;
		counter += 2;
	}

	if (N % 2 == 1) {
		Alice += A[N - 1];
	}

	cout << (Alice - Bob) << endl;

	return 0;
}

この問題では、入力値を降順に並び替える「ソート」をする必要があります。
自作しても構いませんが、時間がかかる上チューニングレベルで負けるので素直にライブラリを使いましょう。

ソートをした後は単純で、一人目と二人目に交互にカードを引かせる(=点数を加算する)だけです。

他の解答を見て気づきましたが、効率はあまり良くありません。
上の解答では、交互にカードを引くためループ変数とカウンター変数を用意し、奇数だった場合はループ外で点数を足す処理をしています。

ループ自体を(i < N)に変更し、剰余算を使って(sum[i % 2] += A[i])とした方がループ一つで完結します。
例としては下のような感じでしょうか。

// 合計を解答する配列
int sum[2] = {0};
	for (int i = 0; i < N; i**) {
		Sum[i % 2] += A[i];
	}
cout << (sum[0] - sum[1]) << endl;

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
	int N, di;
	map<int, int> d;
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> di;
		d[di] = 1;
	}

	cout << d.size() << endl;

	return 0;
}

大きい、小さいという言葉が問題文にありますが、ソートは必ずしも必要ありません。
上に載せる鏡餅は少しでも小さければいいので、「重複しない鏡餅の数」をカウントすれば解答を導き出せます。

解答例では、重複を許さないデータ構造の「map」を使っています。
値の重複があれば上書きされるので、要素数がそのまま重複のない鏡餅の合計と同値です。
似たような「set」でも同じように解答できます。
※データ数も少なくわずかな差ですがsetの方が効率はいいです。

ソートは不要としましたが、ソートさせたうえで前の値と比較して同じだったらスキップする、という感じでカウントさせても解答できます。
鏡餅のサイズ制限が100なので、配列を-1などで初期化しておいて、鏡餅のサイズをそのまま配列のインデックスにする方法もあるでしょう。

//#include <iostream>
//#include <string>
//
//using namespace std;
//
//int culc_valid_bills(int per_unit, int max_usage, int now_money) {
#include <iostream>
#include <string>

using namespace std;

const int LEN = 2000;

int main()
{
	int N, Y;
	int money10000 = 0, money5000 = 0, money1000 = 0;
	cin >> N >> Y;

	while (N > 0) {
		if ((double)Y / 5000 > N) {
			money10000++;
			Y -= 10000;
		}
		else if ((double)Y / 5000 < N) {
			money1000++;
			Y -= 1000;
		}
		else {
			money5000++;
			Y -= 5000;
		}

		N--;
	}

	if (Y == 0) {
		cout << money10000 << " " << money5000 << " " << money1000 << endl;
	}
	else {
		cout << "-1 -1 -1" << endl;
	}

	return 0;
}

この問題ではO(オーダー)を考える必要があります。
最大入力の場合2000^3となり、ざっと80億です。
さすがに計算しきれないので、効率よく計算しなければなりません。

私の解答では、お札の種類が3つであることを利用して単純なループで解いています。
お札の種類が3種類より多い場合、またそれぞれが倍数、約数の関係でない場合はこの解法は使えないでしょう。

Y円が全て5000円札であった場合に必要な枚数が、お年玉の枚数として入力された枚数より大きいか小さいかで判定しています。
プログラムの流れとしては減算方式をとっており、1枚ずつどの紙幣かを判定している、といった方が正しいかもしれません。

お年玉が16000で、お札が3枚を想定してみます。

1. 16000円 / 5000円札 = 3.2枚 > 3枚(要は5000円札だけでは足りない)を満たすので、
1. 1枚目は10000円札として確定させる
2. 残りの金額を16000 – 10000 = 6000円, 残りの枚数を3 – 1 = 2枚とする
2. 6000円 / 5000円札 = 1.2枚 < 2枚を満たすので、
1. 2枚目は1000円札として確定させる
2. 残りの金額を6000 – 1000 = 5000円、残りの枚数を2 – 1枚 = 1枚とする
3. 5000円 / 5000円札 = 1枚 = 1枚で、どちらの条件も満たさないので、
1. 3枚目は5000円札として確定させる
2. 残りの金額を5000 – 5000 = 0円、残りの枚数を1 – 1枚 = 0枚とする

限定的な解法であまり汎用性はありません。
他の方の解法では、10000円と5000円までをループさせて、残りを全部1000円札で仮定する、というものが見受けられました。

2000^2で時間内に収まり、考え方としても分かりやすいように思います。
勉強になりました。

#include <iostream>
#include <string>

using namespace std;

const int TARGET_LENGTH = 4;

const string STR_TARGET[TARGET_LENGTH] = {
	"dreamer",
	"eraser",
	"dream",
	"erase",
};

int main()
{
	string S;
	bool is_match = false;
	bool is_loop = true;

	cin >> S;

	while (is_loop == true) {
		int s_len = S.length();

		is_loop = false;
		for (int j = 0; j < TARGET_LENGTH; j++) {
			int sub_len = STR_TARGET[j].length();

			if (sub_len <= s_len) {
				string sub_set = S.substr(s_len - sub_len, sub_len);
				if (sub_set == STR_TARGET[j]) {
					S = S.substr(0, s_len - sub_len);
					is_loop = true;
					break;
				}
			}
		}
	}

	if (S.length() == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

基本的には文字列を逆順にして判定するのが解きやすいと思います。
前から考えると、dreamとdreamer、またdreameraseとdreamereraserなど切れ目の判定が難しいです。

後ろから考えると、文字数別で考える必要がありますが下記のようになります。
※単語は問題文をご確認ください。

• 5文字の場合
• dream
• eamer
• erase
• raser
• 6文字の場合
• _dream
• reamer
• _erase
• eraser
• 7文字の場合
• __dream
• __dreamer
• __erase
• _eraser

いずれも一致しません。
つまり、逆順で考えてどれかに一致した時点で次々確定してしまって問題ないです。

解答では、与えられた単語の文字数分を後ろから切り出して、確定出来たらbreakでもう一度最初の単語から比較し直させています。
文字列を切り出す際に、インデックス外にならないよう注意しましょう。

他の解答では、入力と単語をそれぞれひっくり返して比較しているものがありました。
また直接切り出さなくてもイテレータを使っているものもあり、比較のみ済むため速度のパフォーマンスに優れています。

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int main()
{
	int N;
	int t, x, y;
	int now_t = 0, now_x = 0, now_y = 0;
	bool is_success = true;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> t >> x >> y;
		int distance = abs(x - now_x) + abs(y - now_y);
		int elapsed = abs(t - now_t);

		if (distance % 2 != (t - now_t) % 2 || elapsed < distance) {
			is_success = false;
		}

		now_t = t;
		now_x = x;
		now_y = y;
	}

	if (is_success == true) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

問題のポイントとしては、斜め移動ができないことにあると考えています。
移動の制限はあるものの、障害物はなく同じ地点を何度踏んでも問題ありません。

目的地まで最短でたどり着いた時、残りの秒数が偶数であれば到達可能となります。
目的地までたどり着いたら、横をうろうろするイメージです。

まとめると、条件は下記の通りです。

1. 目的地まで、十分時間がある
1. xの距離とyの距離の合計が、与えられた秒数以下である
2. 目的地が数直線上でマイナスの可能性があるため、距離は絶対値で計算する
2. 目的地までたどり着いた際の残り時間が、偶数である
1. ※解答例では時間も絶対値を取っているが、入力制限があるためなくても動作する

各地点ごとに判定できるため、必ずしも配列で入力をまとめておく必要はありません。
途中で到達不可になった場合ループを抜けられますが、入力と判定を同じループで行う場合は入力も捨ててしまうため注意が必要です。

※途中で入力を切り捨てる方も提出してみましたが、一応成功はしました。記憶が正しければAOJあたりだと弾かれた気がするので、気になる場合は配列などで入力をまとめておきましょう。