ABC 188

대회중에는 A,B번까지 풀었다

A,B 두 문제를 10분안에 해결해서 C번은 풀 줄 알았는데 도무지 풀이가 생각나질 않아서 못풀었다

 

A - Three-Point Shot

삼점 슛을 넣고 역전이 가능한지 묻는 문제이다

문제에 나온 그대로 구현하면 풀 수 있다

주어지는 두 팀 중 무조건 점수가 낮은팀을 A, 높은 팀을 B로 보는게 구현의 팁

 

B - Orthogonality

벡터의 곱을 하여 0이 되는지 묻는 문제이다

N이 10만이라 $O\left ( N^2 \right )$보다 빠르게 풀어야 하는데, 그냥 1부터 N까지 더해주면서 그 합이 0인지 아닌지 확인하면 풀린다

 

C - ABC Tournament

비트연산을 이용한 구현인줄 알았는데 전혀 아니었습니다

키 포인트는 어찌됐든 매치의 결과로 파이널리스트는 왼쪽, 오른쪽에서 각각 한명씩 나온다는 점입니다

middle을 기준으로 ans = min(왼쪽의 max, 오른쪽의 max)입니다

 

두번째 구현으로는 queue를 이용해서 직접 시뮬레이션을 돌려 줄 수 있습니다 또 이는 벡터를 이용해서도 가능합니다

 

첫번째 구현

    ll mid = e/2;
    ll lt = 0, rt = 0;
    ll idx1 = 0, idx2 = 0;
    for (int i = 0; i < mid; i++) {
        if (lt < A[i]) idx1=i+1;
        lt = max(lt, A[i]);
    }
    for (int i = mid; i < e; i++) {
        if (rt < A[i]) idx2=i+1;
        rt = max(rt, A[i]);
    }
    if (rt>lt) cout << idx1 << endl;
    else cout << idx2 << endl;

두번째 구현

    queue<int> q;
    map<int, int> mp;
    rep(i, e) {
        int tmp;read(tmp);
        q.push(tmp);
        mp[tmp]=i+1;
    }
    ll ans = 0;
    while (q.size()>1) {
        int x = q.front();q.pop();
        int y = q.front();q.pop();
        ans = min(x, y);
        q.push(max(x, y));
    }
    cout << mp[ans] << endl;

첫번째 구현은 이걸 참고했고 두번째 구현은 이 영상을 보고 따라했습니다

 

D - Snuke Prime

구현과 풀이 모두 이 영상을 참고했습니다

전체 구간을 시작지점과 끝 지점을 기준으로 선을 그어 나눠주고

이렇게 나온 각각의 구간의 길이에 대해 min(프라임가격, 개별 서비스들의 비용의 합)을 곱해주면 정답을 구할 수 있습니다

N이 $2\times 10^5$이라 $O\left ( 4\times 10^5 \right )$안에 해결 가능합니다

다만 이 풀이는 구현을 생각해 내는게 어려운데 페어를 이용해 이를 쉽게 구현 할 수 있습니다

    vt<pii> A;
    rep(i, n) {
        int x,y,z;
        cin >> x >> y >> z;
        A.pb({x, z});
        A.pb({y+1, -z});
    }
    ll h = 0; // 총 비용
    ll last = 0; // 구간의 길이
    ll sum = 0; // 정답
    sort(A.begin(), A.end());
    rep(i, A.size()) {
        sum+=(A[i].X-last)*min(c, h);
        h+=A[i].Y;
        last=A[i].X;
    }

시작 시간과 비용을 묶어주고, 끝나는 시간 + 1 과 -비용을 묶어서 벡터에 넣어줍니다

이후 구간의 길이에 min값을 곱해주고, 총 비용을 갱신하고, 구간의 시작도 갱신해 줍니다