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

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

解いた/挑んだ問題
反省点

解いた/挑んだ問題

A問題

問題の概要

アイス製品は乳固形分と乳脂肪分により4つに大別されます。
乳固形分は無脂乳固形分と乳脂肪分の2つからなり、
スヌケアイスには、無脂乳固形分がA%、乳脂肪分がB%含まれています。

アイス製品はそれぞれ
・乳固形分が15%以上で、乳脂肪分が8%以上のものを「アイスクリーム」
・上に当てはまらず、乳固形分が10%以上で、乳脂肪分が3%以上のものを「アイスミルク」
・上に当てはまらず、乳固形分が3％以上のものを「ラクトアイス」
・どれにも当てはまらないものは「氷菓」とする

スヌケアイスはどの種類になりますか

制約

$0 \leq A \leq 100$
$0 \leq B \leq 100$
$A + B \leq 100$
$A,B$ は整数

どのように考えたか

入力では乳固形分が与えられないので、乳固形分を計算して変数に入れて
4通りの場合分けをした

結果

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,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,c;
	cin >> a >> b;
	c = a + b;
	if(15 <= c && 8 <= b)ans = 1;
	else if(10 <= c && 3 <= b)ans = 2;
	else if(3 <= c)ans = 3;
	else ans = 4;
	cout << ans << endl;
	return 0;
}

A問題にしては問題文が難しかった

ACまでの時間

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

f:id:iiiimmmmo:20210307001953p:plain — ABC194_A

B問題

問題の概要

ある会社には従業員が $N$ 人おり、従業員 $i$ は仕事Aを $A_i$ 分、仕事Bを $B_i$ 分でこなすことができます。
同じ従業員が仕事を行うと、Aの時間とBの時間の合算で仕事が終わります。
違う従業員が仕事を行うと、Aの時間とBの時間の短いほうの時間で仕事が終わります。
2つの仕事が終わるのに最短で何分かかりますか

制約

$2 \leq N \leq 1000$
$1 \leq A_i \leq 10^5$
$1 \leq B_i \leq 10^5$
入力は全て整数

どのように考えたか

全ての従業員が２つの仕事をこなした時の最小値を取り、
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,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 = 1001001001;
	cin >> n;
	vector<int>A(n),B(n);
	rep(i,n)cin >> A[i] >> B[i];
	rep(i,n){
		chmin(ans,A[i] + B[i]);
	}
	int tmp;
	rep(i,n){
		rep(j,n){
			if(i == j)continue;
			chmin(ans,max(A[i] , B[j]));
		}
	}
	cout << ans << endl;
	return 0;
}

全探索をすればいいなと思えたので比較的簡単だった

ACまでの時間

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

f:id:iiiimmmmo:20210307002017p:plain — ABC194_B

C問題

問題の概要

長さ $N$ の数列 $A$ が与えられます。
$\sum_{i = 2}^{N}\sum_{j=1}^{i-1}(A_i - A_j)^2$ を求めてください

制約

$2 \leq N \leq 3 × 10^5$
$|A_i| \leq 200$
入力は全て整数

どのように考えたか

愚直にやるとTLEするので、計算量の削減を考えます
$(X - Y)^2$ を展開すると、 $X^2 -(2 × X × Y) + Y^2$ になります。
数列A = [3,4,5]とした場合、
$(3-4)^2 + (3-5)^2 + (4-5)^2$ となり、前半の二つを展開するとそれぞれ
$(3^2 - (2 × 3 × 4) + 4^2) , (3^2 - (2 × 3 × 5) + 5^2)$ となり、
これは、 $2 × 3^2 - (2 × 3 × (4 + 5)) + 4^2 + 5^2$ として、 $X^2$ の部分と $-(2 × X × Y)$ の部分をまとめて計算することができます。
なので、 $X$ より右にある数値をすべて足した配列を事前に計算しておくと、 $-(2 × X × Y)$ を高速に計算できそうです。
また、 $Y^2$ の部分も、 $X$ より右にある数値を二乗してすべて足した配列を事前に計算しておくと高速に計算できます。
$X^2$ に掛ける数値も $X$ より右にある数値の数なので、簡単に求めることができ、
$0 \leq i < j \leq N$ の範囲における $(A_i - A_j)^2$ の合計値をO(1)で計算することができます。

結果

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 n=0;
	ll ans = 0,kake=0;
	cin >> n;
	vector<ll>arr(n),one(n-1,0),two(n-1,0);
	rep(i,n)cin >> arr[i];
	one[n-2] = arr[n-1];
	two[n-2] = arr[n-1] * arr[n-1];
	for(int i = n-2;1 <=i;i--){
		one[i-1] = one[i] + arr[i];
		two[i-1] = two[i] + arr[i] * arr[i];
	}
	rep(i,n-1){
		kake = n - (i+1);
		ll x = arr[i],y = one[i],z = two[i];
		ans += (kake * x*x) -(2*x*y) + z;
	}
	cout << ans << endl;
	// printf("%lld\n",ans);
	return 0;
}

展開して計算量の削減を見つけられたのはよかったが、配列外参照とint型のオーバーフローで２ペナを出してしまったのが痛かった

ACまでの時間

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

f:id:iiiimmmmo:20210307002032p:plain — ABC194_C

コンテスト結果

ABCの3完でした。
C問題で時間を使いすぎて、ほかの問題を最後までつめきれなかった

f:id:iiiimmmmo:20210307002046p:plain — ABC194

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

今回のパフォーマンスは638、前回より70近くあがりました。
レーティングはそれに伴い-5の683となりました。

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

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

反省点

今回は、すぐに式展開をして計算量の削減を図れたのはよかったが、配列外参照でエラーが起き
その原因をなかなか特定できなかったのがとても痛いところです。
E問題もチャレンジしてみて、最後の最後で詰め切れずWAだったので、今回は自分の甘さが出てしまったのかなと思います。
最近なかなか成果が振るわないので、どこかで大逆転できるようにこれからも精進していきたいです。