takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

AtCoder Beginner Contest 085

はじめに

AtCoderのBeginner Contest 085の解説と勉強です。
問題はこちらを参照してください。

A - Already 2018

文字列を入れ替えるだけの問題。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

string str;

int main() {
	cin >> str;

	if (str.substr(0, 4) == "2017") {
		str[3] = '8';
	}

	cout << str << endl;

	return 0;
}

改善点

特になし

B - Kagami Mochi

「どの餅もその真下の餅より直径が小さい」ということなので、「大きさの違う餅が何種類あるか」という問題に帰着できます。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int N;
int d[100];
int num = 0;

int main() {
	cin >> N;
	rep(i, N) {
		cin >> d[i];

		bool check = true;
		rep(j, i) {
			if (d[i] == d[j]) {
				check = false;
				break;
			}
		}

		if (check) num++;
	}

	cout << num << endl;
	return 0;
}

改善点

特になし

C - Otoshidama

指定されたお札の枚数ちょうどで、指定された金額を決定する問題です。

指針としては、まず初めに一番少ない枚数で指定された金額を作り、そのあとに両替を繰り返します。

この両替では、大きなお札から段々と崩す(=お札の枚数が増える)両替だけを行います。したがって、両替としてあり得るのは「10000円→5000円」「5000円→1000円」「10000円→1000円」の3つの選択肢があります。

しかし、「10000円→1000円」の両替は、「10000円→5000円」と「5000円→1000円」の両替で表現できます。したがって、考える必要がありません。

さらに、両替によって両替によって減る枚数が大きい「5000円→1000円」から順番に両替します。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int N, Y;
int _N;
int x = 0, y = 0, z = 0;

int main() {
	cin >> N >> Y;

	// 最小の枚数を決定する
	x = Y / 10000;
	Y = Y % 10000;
	
	y = Y / 5000;
	Y = Y % 5000;
	
	z = Y / 1000;
	Y = Y % 1000;
	
	if (Y != 0) { x = -1, y = -1, z = -1; }
	else {
		while (x + y + z != N) {
			if (N - (x + y + z) >= 4 && y >= 1) {
				z += 5;
				y -= 1;
			}
			else if (N - (x + y + z) >= 1 && x >= 1) {
				y += 2;
				x -= 1;
			}
			else {
				x = -1, y = -1, z = -1;
				break;
			}
		}
	}

	cout << x << " " << y << " " << z << endl;

	return 0;
}

改善点

特になし

D - Katana Thrower

複数個ある刀が与えられ、それぞれの刀に攻撃方法が二つあり、「振る」は何回もでき、「投げる」は1回しかできなく、それ以降その刀は使用できなくなる状態で、最速で魔物を倒す問題。

複数回できる「振る」攻撃は、最も強い「振る」攻撃を持つ刀で行うのが最も効率的です。

一方で、1回しかできない「投げる」攻撃は、最も強い「振る」攻撃力以上の攻撃力を持っている場合は、使用する方が効率的です。

しかし、「振る」より「投げる」の方が攻撃力が強いという制約から、最も強い「振る」攻撃力を持つ刀によって「振る」攻撃をしている時、もしその刀を「投げる」ことで魔物を倒すことができる場合、その刀は「投げる」べきです。したがって、最後の一撃は最も強い「振る」攻撃力を持つ刀による「投げる」攻撃です。さらに、ここで重要なことは攻撃が決まっている場合、攻撃の順番は関係ないということです。

以上のことから、まず「投げる」の攻撃力に基づいてソートをし、最も強い「振る」攻撃より強い「投げる」攻撃を強い順に行います。攻撃の順番は関係ないことから、この時点で、最も強い「振る」攻撃を持つ刀の「投げる」攻撃が先に行われているようになってしまっていますが、関係ありません。最後は残った魔物のHPに対して、最も強い「振る」攻撃を繰り返すだけです。

注意したいのは、実際に戦う時には最も強い「振る」攻撃力を持つ刀の「投げる」攻撃であるということです。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
	int num = 0;

	int N, H;
	cin >> N >> H;

	vector<pii> ab(N);
	int max_a = 0, max_ai;

	REP(i, N) {
		cin >> ab[i].first >> ab[i].second;
		if (max_a < ab[i].first) {
			max_a = ab[i].first;
			max_ai = i;
		}
	}

	sort(ab.begin(), ab.end(), [](const pii x, const pii y) { if (x.second == y.second) { return x.first < y.first; } else { return x.second > y.second; }});

	REP(i, N) {
		if (max_a < ab[i].second) {
			num++;
			H -= ab[i].second;
			if (H <= 0) break;
		}
		else break;
	}

	if (H <= 0) cout << num << endl;
	else cout << num + (H + max_a - 1) / max_a << endl;

	return 0;
}

改善点

特になし
この問題のようにあくまでも順番に行う操作であっても、順番を無視できる可能性がある問題はよく出てきますね。