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

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

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

解いた/挑んだ問題

A問題

問題の概要

一日毎に白と黒の服を着る高橋君は白い服を着たN日後は何色の服を着るか
黒の時は"Black"、白の時は"White"と出力せよ

制約

Nは整数
$1 \leq N \leq 30$

どのように考えたか

Nが奇数の時は黒、偶数の時は白の服と置き換えた

結果

1発AC
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;

int main() {
	int n;
	cin >> n;
	if(n%2==1){
		cout << "Black" <<endl;
	}else{
		cout << "White" <<endl;
	}
	return 0;
}

A問題らしい問題だった

ACまでの時間

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

f:id:iiiimmmmo:20201101235731p:plain — ABC181_A

B問題

問題の概要

N回以下の操作を行う

整数A,Bが与えられ、A以上B以下の数を列挙する

列挙したすべての数の合計を出力せよ

制約

入力はすべて整数
$1 \leq N \leq 10^5$
$1 \leq A_i \leq B_i \leq 10^6$

どのように考えたか

等差数列の和により、1からBまでの和を求め、
1からA-1の和を引いたものを変数に足していき
最後に出力

結果

1発AC
提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;

int main() {
	int n,a,b;
	ll ans=0,tmp=0;
	cin >> n;
	rep(i,n){
		cin >> a >> b;
		tmp = b*(b+1LL)/2;
		if(a != 1)tmp -= (a-1LL)*(a)/2LL;
		ans += tmp;
	}
	cout << ans <<endl;
	return 0;
}

等差数列の和の公式を覚えていてよかった

ACまでの時間

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

f:id:iiiimmmmo:20201101235751p:plain — ABC181_B

C問題

問題の概要

2次元平面上にN個の点があり、i番目の点は $(x_i,y_i)$ にあります
N個の点の中で異なる3つの点が同一直線上にあるものは存在するか
存在する場合"Yes"を、しない場合"No"を出力せよ

制約

入力はすべて整数
$3 \leq N \leq 10^2$
$|x_i|,|y_i| \leq 10^3$
$i ≠ j ならば、(x_i,y_i) ≠ (x_j,y_j)$

どのように考えたか

Nが100しかないので、全探索を行い3点の傾きを計算して一致しているか判定

結果

コンテスト中に通すことはできませんでした
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;

int main() {
	int n, x, y;
	double a, b, c;
	int ans = 0;
	cin >> n;
	vector<pi>v(n);
	rep(i, n) {
		cin >> x >> y;
		v[i] = pi(x, y);
	}
	rep(i, n - 2) {
		FOR(j, i + 1, n - 1, 1) {
			FOR(k, j + 1, n, 1) {
				a = (double)(v[j].second - v[i].second) / (double)(v[j].first - v[i].first);
				b = (double)(v[k].second - v[i].second) / (double)(v[k].first - v[i].first);
				// /c = (double)(v[k].second - v[j].second) / (double)(v[k].first - v[j].first);
				if ((a+0.5) == (b+0.5))ans = true;
			}
		}
	}
	//Yes/Noを返す
	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

最後に1WA出したのは誤差の影響らしいので、式変形で誤差が生まれないようにしたいです。

ACまでの時間

なし

f:id:iiiimmmmo:20201101235811p:plain — ABC181_C

D問題

問題の概要

1~9の数字のみからなる数字列Sが与えられる
この数字列を並び替えて8の倍数に出来るかどうか
出来る場合"Yes"を、できない場合"No"を出力せよ

制約

$1 \leq |S| \leq 2 × 10^5$
Sの各文字は1~9のいずれか

どのように考えたか

googleで8の倍数　判定方法　で検索して3桁以上の場合が出てきたので、
3桁はそれに倣って実装
2桁以下は全列挙して判定しました

結果

1発AC
・提出したコード

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define FOR(i,x,n,r) for(long long i = x; i< (long long)(n); i+=r)
#define afor(a,t) for(auto a:t)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
using namespace atcoder;
using ll = long long;
using pi = pair<int, int>;

int main() {
	bool ans = false;
	vector<map<char, int>>vm;
	map<char, int>m;
	string ts;
	FOR(i, 100, 1000, 1) {
		if (i % 2 != 0)continue;
		int tmp = i / 2;
		int t = tmp % 100;
		if (t % 4 != 0)continue;
		m.clear();
		ts = to_string(i);
		afor(a, ts)m[a]++;
		vm.push_back(m);
	}
	string  s;
	cin >> s;
	if (s.size() < 3) {
		vector<string>v;
		v = { "8","16","24","23","04","48","56","46","27","08","88","69" };
		sort(all(s));
		afor(a, v)if (s == a)ans = true;
	}
	else {
		map<int, int>ss;
		afor(a, s)ss[a]++;
		afor(b, vm) {
			afor(c, b) {
				if (c.second <= ss[c.first])ans = true;
				else { ans = false; break; }
			}
			if (ans) {
				break;
			}
		}
	}
	//Yes/Noを返す
	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}