ABC166に参加しました - imomoの勉強記録

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題
結果
- コンテスト結果
- 順位、パフォーマンス変動
反省点

解いた/挑んだ問題

A問題

問題の概要

文字列"ABC"が与えられたら"ARC"を、文字列"ARC"が与えられたら"ABC"を出力せよ

制約

与えられる文字列は"ABC"か"ARC"のいずれか

どのように考えたか

ABCとARCの文字列をstring型の変数に持たせておいてif文で比較し逆を出力する。

結果

一発AC
・提出したのコード

#include"bits/stdc++.h"
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}


int main() {
	string abc = "ABC";
	string arc = "ARC";

	string mae;
	cin >> mae;
	if (mae == abc)cout << arc << endl;
	else cout << abc << endl;
	return 0;
}

A問題らしい問題だと思った

ACまでの時間

ACしたのはコンテスト開始から90秒後です。

f:id:iiiimmmmo:20200503225723p:plain — ABC166_A

B問題

問題の概要

K種類のお菓子があり、N人いる子供のうち、お菓子iを持っているのは子供 $A_{i,1},A_{i,2},・・・,A_{i,d_i}$ の計 $d_i$ 人です。
1つもお菓子を持っていない子供は何人いるでしょうか

制約

入力はすべて整数
$1 \leq N \leq 100$
$1 \leq K \leq 100$
$1 \leq d_i \leq N$
$1 \leq A_{i,1} < ・・・ < A_{i,d_i} \leq N$

どのように考えたか

vectorに子供のお菓子所次数をカウントさせて、最後に拡張for文でお菓子が0の子供を数えて出力

結果

一発AC
提出したコード

#include"bits/stdc++.h"
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}


int main() {
	int N, K;
	int human;
	int sunake;
	int cnt = 0;
	cin >> N >> K;
	vector<int>sunuke(N,0);
	rep(i, K) {
		cin >> human;
		rep(j, human) {
			cin >> sunake;
			sunuke[sunake - 1] += 1;
		}
	}

	for (int i : sunuke) {
		if (i == 0)cnt++;
	}
	cout << cnt << endl;
	return 0;
}

最初問題の入力形式に戸惑って、コードを書くのが遅くなってしまいました。

ACまでの時間

ACしたのはコンテスト開始から13分後です。

f:id:iiiimmmmo:20200503225744p:plain — ABC166_B

C問題

問題の概要

N個の展望台があり、展望台iの標高は $H_i$ です。
また、異なる展望台同士をM本の道で結んであり、道jは展望台 $A_j$ と展望台 $A_j$ を結んでいます。
展望台iから一回でたどり着ける展望台がiの標高より低いものの展望台の台数を出力せよ
ただし、展望台から道が出ていないものも、台数に入れる

制約

$2 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq H_i \leq 10^9$
$1 \leq A_i,B_i \leq N$
$A_i ≠B_i$
同じ展望台の組を結ぶ道が複数あることもある。
入力中の値はすべて整数である。

どのように考えたか

展望台同士をつなぐ道をvectorに持たせて、
展望台iから行ける展望台と比較して真が返ったらカウントして出力

結果

一発AC
・提出したコード

#include"bits/stdc++.h"
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}


int main() {
	int N, M, A,B;
	ll HH;
	int ans = 0;
	cin >> N >> M;
	vector<ll>H(N);
	vector<vector<int>>tenbou(N,vector<int>());
	rep(i, N) {
		cin >> HH;
		H[i] = HH;
	}
	rep(i, M) {
		cin >> A >> B;
		A--; B--;
		tenbou[A].push_back(B);
		tenbou[B].push_back(A);
	}

	rep(i, N) {
		ll n = H[i];
		bool takai = true;
		for (int rin : tenbou[i]) {
			if (H[rin] >= n) takai = false;
		}
		if (takai)ans++;
	}
	cout << ans << endl;
	return 0;
}

探索系問題は少し勉強していたので実装方法が頭に浮かんできてよかったです

ACまでの時間

ACしたのはコンテスト開始から25分後です。

f:id:iiiimmmmo:20200503225859p:plain — ABC166_C

D問題

問題の概要

$A^5 - B^5 = X$ を満たす整数の組(A,B)を一つ示せ

制約

$1 \leq X \leq 10^9$
Xは整数である
条件を満たす整数の組(A,B)は存在する

どのように考えたか

予め数の5乗を計算しておき、vectorに格納してその数字で全探索を行いXと等しければ出力

結果

2回目でACでした。
・提出したコード

#include"bits/stdc++.h"
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;

template <typename T>
bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}

template <typename T>
bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b;  // aをbで更新
		return true;
	}
	return false;
}


int main() {
	ll a = -458;
	int A = 0, B = 0;
	ll ans  = 0;
	vector<ll> num;
	while (ans < pow(10, 13)  * 2) {
		ans = (a * a * a * a * a);
		num.push_back(ans);
		a++;
	}
	//cout << num.size();
	ll X;
	cin >> X;
	for (int i = 0; i < num.size(); i ++) {
		for (int j = 0; j < num.size(); j++) {
			if (num[i] - num[j] == X) {
				A = i - 458;
				B = j - 458;
				break;
			}
		}
	}
	cout << A << " " << B << endl;

	return 0;
}