AtCoder Beginner Contest 189 후기

2021. 1. 24. 15:29

내가 한 엣코더 라운드 중에 가장 잘한 라운드다!

3솔했고, B에서 많이 뇌절했다.

B는 문제가 좀 별로인것 같다.

그리고 C번은 왤논이었는데 내가 그걸 모르고(...) 엄청 어렵게 풀었다.

풀이로 들어가자!

A. Slot

Problem Statement

You are playing the slots.

The result of a spin is represented by three uppercase English letters $C_{1}$ , $C_{2}$ and $C_{3}$ . It is considered a win when all of them are the same letter.

Determine whether it is a win.

Constraints

$C_{i}$ is an uppercase English letter.

Input

Input is given from Standard Input in the following format:

$C_{1} C_{2} C_{3}$

Output

If the result is a win, print Won; otherwise, print Lost.

풀이

주어진 세개의 문자가 같은지를 판별하자.

#include<bits/stdc++.h>
int main(){
	char a,b,c;
	scanf("%c %c %c",&a,&b,&c);
	if(a==b&&a==c&&b==c) puts("Won");
	else puts("Lost");
	return 0;
}

[01:21 Accepted]

B. Alchoholic

Problem Statement

Takahashi had $N$ glasses of liquor.

The amount and alcohol percentage of the $i$ -th liquor were $V_{i}$ milliliters and $P_{i}$ percent by volume, respectively.

Takahashi gets drunk when his alcohol intake exceeds $X$ milliliters.

Which of the $N$ liquors was he drinking when he gets drunk? If he was not drunk even after drinking all the liquors, print -1 instead.

Constraints

All values in input are integers.
$1 \leq N \leq 10^{3}$
$0 \leq X \leq 10^{6}$
$1 \leq V_{i} \leq 10^{3}$
$0 \leq P_{i} \leq 100$

Input

Input is given from Standard Input in the following format:

$N$ $X$

$V_{1}$ $P_{1}$

$⋮$

$V_{N}$ $P_{N}$

Output

If Takahashi got drunk when drinking the $i$ -th liquor, print $i$ . If he was not drunk even after drinking all the liquors, print -1 instead.

풀이

각 주어지는 음료별로 알코올의 양을 구해서 더하면 된다.

그대로 코드를 짜고 제출하면 틀린다.

왜그럴까? 바로 실수 오차 때문이다.

실수 오차를 없엘려면 실수를 없에 버리면 된다.

따라서 알코올의 양을 100으로 나누지 않고, 즉 알코올의 양*100을 구하고 그 값을 마실수 있는 최대 알코올의 양*100과 비교해주면 된다.

실수오차 참 짜증난다:(

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x;cin >> n >> x;
    int v[1000], p[1000];
    for (int i = 0; i < n; ++i) cin >> v[i] >> p[i];
    long long t[1000];
    for (int i = 0; i < n; ++i) t[i] = v[i] * p[i];
    long long ans = 0;
    for (int i = 0; i < n; ++i){
        ans += t[i];
        if (ans > x * 100){
            cout << i+1 << endl;
            break;
        }
    }
    if (ans <= x * 100) cout << -1;
}

[13:00 Wrong answer]

[15:07 Wrong answer]

[18:23 Wrong answer]

[25:29 Wrong answer]

[27:52 Wrong answer]

[30:25 Accepted]

C. Mandarine Orange

Problem Statement

There are $N$ dishes arranged in a row in front of Takahashi. The $i$ -th dish from the left has $A_{i}$ oranges on it.

Takahashi will choose a triple of integers ( $(l, r, x)$ satisfying all of the following conditions:

$1 \leq l \leq r \leq N$
$1 \leq x$
for every integer $i$ between $l$ and $r$ (inclusive), $x \leq A_{i}$ .

He will then pick up and eat $x$ oranges from each of the $l$ -th through $r$ -th dishes from the left.

At most how many oranges can he eat by choosing the triple $(l, r, x)$ to maximize this number?

Constraints

All values in input are integers.
$1 \leq N \leq 10^{4}$
$1 \leq A_{i} \leq 10^{5}$

Input

Input is given from Standard Input in the following format:

$N$

$A_{1}$ $\dots$ $A_{N}$

Output

Print the maximum number of oranges Takahashi can eat.

풀이

이 문제는 왜인지 모르겠지만 왤논이라고 한다,,

나는 대회 중에 진짜 이상한 방법으로 풀어서 11분만에 템플릿 미포함 1442B를 짜는 미친짓을 했다.

여러분은 이런 풀이를 하지 않았으면 한다.. ㅠㅠㅠ

내 풀이를 설명하면 머리만 아프니까 에디토리얼에 있는 간단한 풀이를 설명하도록 하겠다.

One can first fix $l$ , then update $x$ while increasing $r$ one by one to find them in a total of $O (N^{2})$ time.

아 너무 쉽다

<에디토리얼 코드>

#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	int ans=0;
	for(int l=0;l<n;l++){
		int x=a[l];
		for(int r=l;r<n;r++){
			x=min(x,a[r]);
			ans=max(ans,x*(r-l+1));
		}
	}
	cout << ans;
}

<내 코드>

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> f(vector<ll> &v){
	ll i,j,k,l,n=v.size();
	vector<ll> res(n);stack<ll> st;
	for(i=0;i<n;i++){
		while(!st.empty()&v[i]<=v[st.top()]) st.pop();
		if(st.empty()) res[i]=-1;
		else res[i] = st.top();
		st.push(i);
	}
	return res;
}
vector<ll> g(vector<ll> &v){
	ll i,j,k,l,n=v.size();vector<ll> res(n);stack<ll> st;
	for(i=n-1;i>=0;i--){
		while(!st.empty()&v[i]<=v[st.top()]) st.pop();
		if(st.empty()) res[i]=n;
		else res[i] = st.top();
		st.push(i);
	}
	return res;
}
void solve(){
	ll i,j,k,n,m,a,b,u;cin>>n;vector<ll> v(n);
	for(i=0;i<n;i++) cin>>v[i];
    vector<ll> l = f(v);vector<ll> r = g(v); ll ans=0;
    for(i=0;i<n;i++) ans = max(ans, v[i]*(r[i]-l[i]-1));
    cout<<ans;
}
int main(){
    ll t;t=1;
    while(t--) solve();
}

~~제 코드가 얼마나 더러운지 알겠나요~~

[41:55 Accepted]

D 굉장히 어려워 보여서 안풀었다 ㅋㅋㅋㅋ

업솔빙도 안할예정

저작자표시

'대회 후기 > Atcoder' 카테고리의 다른 글

Atcoder Beginner Contest 186 (1)	2020.12.26
Atcoder Beginner contest 185 후기 (0)	2020.12.19
ABC 184 후기 (0)	2020.11.23

CodeupCoder's Blog