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

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

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

解いた/挑んだ問題

A問題

問題の概要

バスケの試合が行われており、現在の得点がX対Yです。
劣勢のチームが3点を入れることができたら逆転できますか？
ただし、両チームの得点は異なります

制約

$0 \leq X \leq 100$
$0 \leq Y \leq 100$
$X ≠ Y$
$X,Y$ は整数である

どのように考えたか

max(X,Y) < min(X,Y) + 3をした

結果

一発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,v,n) for(long long i = v; i < (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	int a,b,ans=0;
	cin >>a >> b;
	if(max(a,b) < min(a,b) + 3)ans = 1;
	//Yes/Noを返す
	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

同点だとダメなところに引っかからなくてよかった

ACまでの時間

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

f:id:iiiimmmmo:20210111001205p:plain — ABC188__A

B問題

問題の概要

2つのN次元ベクトル $A = (A_1,A_2,A_3,...A_N), B = (B_1,B_2,B_3,...,B_N)$ が与えられます
AとBの内積が0かどうかを判定してください

制約

$1 \leq N \leq 100000$
$-100 \leq A_i \leq 100$
$-100 \leq B_i \leq 100$
入力はすべて整数

どのように考えたか

AとBの同じ添え字どうしをかけて足した

結果

一発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,v,n) for(long long i = v; i < (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	int n,ans=0;
	cin >> n;
	vector<int>a(n),b(n);
	rep(i,n)cin >> a[i];
	rep(i,n)cin >> b[i];
	rep(i,n)ans += a[i]*b[i];
	//Yes/Noを返す
	if (!ans) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

ベクトルと聞いて少し怖かったが問題文に計算の仕方が載っていたので助かった

ACまでの時間

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

f:id:iiiimmmmo:20210111001802p:plain — ABC188_B

C問題

問題の概要

選手1から $選手2^N$ までの $2^N$ 人の選手がトーナメント形式で対戦します
選手 $i$ のレートは $A_i$ で、二人で対決するとレートが高いほうが必ず勝ちます。
まだ負けていない番号の小さい選手から対戦すると、準優勝は誰になりますか

制約

$1 \leq N \leq 16$
$1 \leq A_i \leq 10^9$
$A_i$ は相違なる
入力はすべて整数

どのように考えたか

while文で隣り合う選手と対決して勝った選手を配列に格納
配列のサイズが2になったら小さい方の選手を出力

結果

2回目で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,v,n) for(long long i = v; i < (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	int n;
	cin >> n;
	vector<int>a((1 << n)),b;
	rep(i,(1 << n))cin >> a[i];
	map<int,int>mp;
	rep(i,(1 << n)){
		mp[a[i]] = i+1;
	}
	while(2 < a.size()){
		for(int i = 0;i <a.size();i+=2)b.push_back(max(a[i],a[i+1]));
		swap(a,b);
		b.clear();
	}
	sort(all(a));
	cout << mp[a[0]] << endl;
	return 0;
}

添え字バグで1回WAしてしまい、そこから時間を使ってしまったのでこういうミスはなくしたい

ACまでの時間

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

f:id:iiiimmmmo:20210111002436p:plain — ABC188_C

D問題

問題の概要

あるサービス会社はサービスがいくつかあり、一括プランを一日 $C$ 円で、一つのサービスを一日 $c_i$ 円で提供しています。
そのうちN個のサービスを $a_i$ 日から $b_i$ 日まで使います
一括プランでは、すべてのサービスを1日利用することができます。
サービスを利用する最小料金を求めて下さい。

制約

$1 \leq N \leq 2 × 10^5$
$1 \leq C \leq 10^9$
$1 \leq a_i \leq b_i \leq 10^9$
$1 \leq c_i \leq 10^9$
入力はすべて整数

どのように考えたか

imosをmapで行う
ある日から次のある日の変化量を足したのが答え

結果

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

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

#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define REP(i,v,n) for(long long i = v; i < (long long)(n); i++)
#define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--)
#define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--)
#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<ll, ll>;
ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}

int main() {
	ll n,C,a,b,c,res=0,uk=0,uv=0;
	cin >> n >> C;
	map<ll,ll>mp;
	vector<pi>vec;
	rep(i,n){
		cin >> a >> b >> c;
		b++;
		mp[a] += c;
		mp[b] -= c;
	}
	ll tmp=0;
	for(auto[k,v]:mp){
		tmp += v;
		vec.emplace_back(k,tmp);
	}
	rep(i,vec.size()-1){
		auto[a,b] = vec[i];
		auto[c,d] = vec[i+1];
		ll day = c-a;
		res += min(day*b,day*C);
	}
	cout << res << endl;
	return 0;
}

あとで教えてもらったのですが、計算の途中でオーバーフローしてしまっていて正しい答えが出なかったです・・・

ACまでの時間

コンテスト開始から120分後。

結果

コンテスト結果

ABCの3完でした。
Dはとれたと思うので、勿体なかった

f:id:iiiimmmmo:20210111003421p:plain — ABC188

パフォーマンス、レーティング変動

今回のパフォーマンスは593、前回より100も下がってしまいました。
レーティングはそれに伴い-7の663となりました。

f:id:iiiimmmmo:20210111003504p:plain — コンテスト成績表

f:id:iiiimmmmo:20210111003533p:plain — ABC188を終えた時点でのレーティング

反省点

今回はC問題の簡単なミス
D問題のオーバーフロー考慮ミスがありあまりいい結果を残せませんでした。
Dの解法を思いついたのも結構後だったので、素早く思いつけるようになりたいです