AtCoder Beginner Contest 294 후기 (ABC 294 5솔)

처음으로 5솔을 했고 6솔도 노려볼만 했다고 생각한다

2218등을 했다 다음엔 1xxx등을 노려 보자,,,,,

101점 올라서 브론즈 됐음

 

에디토리얼이 제공되어 있다

 

A - Filter : 짝수 판별

배열을 쓸 필요도 없이 입력값이 짝수이면 출력하면 된다

 

B - ASCII Art : 2차원 배열, char

입력이 0이면 해당하는 char 배열의 위치에 '.'을 저장하고,

그렇지 않다면 입력값 + 'A' - 1을 저장한 뒤 출력하면 된다

 

C - Merge Sequences : 정렬, 우선순위 큐??

배열 A와 B를 concatenate해 새로운 배열 C에 저장한 뒤, 그것을 정렬한 뒤,

A와 B의 원소를 차례대로 검사하면서 그것이 C의 몇번째 원소인지 출력하면 된다

 

정해가 뭔지 모르겠다. 나는 그냥 내가 아는 자료구조 중 입출력/정렬이 가장 빠른 priority queue를 써서 풀었다

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int main(void) {
    fastio;
    int N,M;cin>>N>>M;
    vector<int> A(N),B(M);
    vector<int> a,b;
    priority_queue<int,vector<int>,greater<int>> pq;
    for (int i = 0; i < N; i++)
    {
        cin>>A[i];
        pq.push(A[i]);
    }
    for (int i = 0; i < M; i++)
    {
        cin>>B[i];
        pq.push(B[i]);
    }

    int ia=0,ib=0;
    int now = 0;

    while (!pq.empty())
    {
        ++now;
        int cur = pq.top();
        pq.pop();
        if(A[ia]==cur){
            ia++;
            a.push_back(now);
        }
        else{
            ib++;
            b.push_back(now);
        }
    }
    
    for (int i:a)
    {
        cout<<i<<" ";
    }
    cout<<"\n";
    for (int i:b)
    {
        cout<<i<<" ";
    }
    return 0;
}

pq를 쓸 경우, pq는 heap구조니까, N개원소 입력에 NlogN, N개원소 출력에 NlogN 시간이 필요할 것이다

최악의 경우 입력이 2*10^5니깐,,,,,

NlogN을 하면 대충 10^(7.5) 만큼 걸릴 것이니 이 문제를 풀 수 있다,,,,,

 

D - Bank : 영어독해, 우선순위 큐, 구현

문제를 이해하는 데 한참 걸렸다. 그러니까 나한텐 이게 영어독해 문제임

구현 자체는 C번보다 더 쉬웠다

call된 대상은 queue에 집어넣고, come한 대상은 set에 저장해서,

3번 동작을 할 때마다 이녀석이 queue에 있는 가장 ID가 앞인 녀석이면서, come했는지 안했는지 확인한 뒤 출력하면 됨

 

E - 2xN Grid : 누적 합, map, 큐

일단 문제가 정말 안 읽힌다 이것도 독해하는데 한참 걸렸다

정해가 뭔지 모르겠어서 생각나는 것 중 가장 빠른 방법으로 구현했다.

설명하기가 좀 어려운데

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
int main(void) {
    fastio;
    ll L,N1,N2;cin>>L>>N1>>N2;
    ll ans = 0;
    map<ll,queue<pair<ll,ll>>> mm;
    ll n1=0;
    for (int i = 0; i < N1; i++)
    {
        ll v,l;cin>>v>>l;
        ll n1t = n1;
        n1+=l;
        mm[v].emplace(n1t,n1);
    }
    ll n2=0;
    for (int i = 0; i < N2; i++)
    {
        ll v,l;cin>>v>>l;
        ll n2t = n2;
        n2+=l;
        while (!mm[v].empty())
        {
            ll st = mm[v].front().first;
            ll ed = mm[v].front().second;
            if(n2t>=ed)mm[v].pop();
            else if(n2<=st)break;
            else if(ed<n2){
                ans+=min(n2,ed)-max(st,n2t);
                mm[v].pop();
            }
            else{
                ans+=min(n2,ed)-max(st,n2t);
                break;
            }   
        }       
    }
    cout<<ans;
    return 0;
}

첫번째 행의 입력을 받으면서 map을 만들었다.
key로 2차원 그리드의 내용물 값을 갖고,
value로 그 내용물이 몇번째 인덱스부터 몇번째 인덱스까지 위치해 있는지 저장한다. 이때, 누적합을 활용하기 위해 시작하는 인덱스 -1 와, 끝나는 인덱스 값을 저장하게 했다

두번째 행의 입력을 받으면서 map에 저장된 부분과 겹치는 부분이 있는지를 확인했다.

두번째 행의 검사 범위가 map보다 앞쪽에 있다면 검사를 중지했고,

두번째 행의 검사 범위가 map보다 뒤쪽에 있다면 map에 저장된 queue를 pop하면서 불필요한 부분을 없앴고,

두번째 행의 검사 범위와 map에 겹치는 범위가 있다면 그만큼 ans에 더했음.

 

 

F - Sugar Water 2 : 소수, 사칙연산, 투포인터??

시간만 더 있으면 풀 수 있었을 것 같은데 아깝당

//RE code RE code RE code RE code RE code RE code RE code RE code RE code
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
//최대 25억가지 설탕물 조합
int main(void) {
    fastio;
    int N,M,K;cin>>N>>M>>K;
    vector<pair<double,double>> A,B;
    for (int i = 0; i < N; i++)
    {
        double a,b;cin>>a>>b;
        double c = a/(a+b);
        A.emplace_back(c,a+b);
    }
    for (int i = 0; i < M; i++)
    {
        double a,b;cin>>a>>b;
        double c = a/(a+b);
        B.emplace_back(c,a+b);
    }

    sort(A.begin(),A.end(),greater<pair<double,double>>());
    sort(B.begin(),B.end(),greater<pair<double,double>>());

    int now = 1;
    int ai=0,bi=0;
    double ans = (A[ai].first*A[ai].second+B[bi].first*B[bi].second)/(A[ai].second+B[bi].second);
    while (1)
    {
        if(K==now){
            ans*=100;
            cout<<fixed<<setprecision(12)<<ans;
            return 0;
        }
        if(ai<N&&bi<N){
            double ans1 = (A[ai+1].first*A[ai+1].second+B[bi].first*B[bi].second)/(A[ai+1].second+B[bi].second);
            double ans2 = (A[ai].first*A[ai].second+B[bi+1].first*B[bi+1].second)/(A[ai].second+B[bi+1].second);
            //둘중에 더큰걸로 함
            if(ans1>ans2){
                ans = ans1;
                ai++;
            }
            else{
                ans = ans2;
                bi++;
            }
        }
        else if(ai<N){
            ans = (A[ai++].first*A[ai++].second+B[bi].first*B[bi].second)/(A[ai++].second+B[bi].second);
        }
        else{
            ans = (A[ai].first*A[ai].second+B[bi++].first*B[bi++].second)/(A[ai].second+B[bi++].second);
        }
        ++now;
    }
    return 0;
}
//RE code RE code RE code RE code RE code RE code RE code RE code RE code

내가 생각해낸 방법은 이러하다

A와 B배열을 저장해 놓고 설탕물 농도가 높은 순/용액량이 많은 순으로 정렬한다

그다음 A배열의 포인터와 B배열의 포인터를 움직이면서 K번째로 농도가 높은 설탕물 조합을 찾는다

 

근데 위의 코드로 제출하면 Nan오류로 인해 런타임 에러가 발생하기도 하고 일부 케이스에 대해 WA도 발생한다

문제 자체는 어렵지 않은 것 같은데 뭔가 더 있는 것 같다. 시간제한을 괜히 4초 주지도 않을 테고,

입력값을 보면 DIV/0 으로 인한 오류는 아닌 거 같은데

아무튼 그렇다

다시 풀어 보자