새벽에 끝내는 scpc 2024

 

입시가 끝났다... 본인은 이제 응애 학부 1학년생이다.

학부생이라면 반드시 해봐야 하는 것 중 하나가 있다면 바도 ps대회이다. 진짜로.

ucpc와 scpc를 모두 나갈려고 했으나 귀찮은 관계로 생략, scpc만 신청했다. (대회 마지막날에 신청한 건 비밀)

 

토요일 기자단발대식 + 월요일 마감 통계학 과제 + 일요일 미팅이 있어서 시간이 좀 부족할 수도 있겠다 싶었는데 오히려 시간은 널널했다. koi처럼 시간으로 변별하는 느낌은 아닌 듯.

뭐 그냥 예선도 아니고 예선 1차라서 오후에 두 분메 새벽에 두 분제 풀고 5번문제는 쿨하게 때려치고 잤다.

 

round1_01.c

#include <stdio.h>
#include <stdlib.h>

#define max(a, b)   (((a)>(b))?(a):(b))

int Fnc(char f){ return (f == 'A')?1:-1; }

void solve(int t){
    int N;
    char str[500002];
    int cur, dy = -1;
    int cnt = 0;
    scanf("%d", &N); scanf("%s", str);
    for(cur = 1; cur < N;cur++){
        dy = max(dy, Fnc(str[cur-1])) + Fnc(str[cur]);
        if(dy > 0){ cnt += dy; dy=0; } // add 'B' on it
    }
    printf("Case #%d\n", t);
    printf("%d\n", cnt);
    return;
}

int main(void){
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(int i=0;i<T;i++){ solve(i+1); }
    return 0;
}

round1_02.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void solve(int t){
    int N;
    vector<int> V;
    long long res = 0;
    scanf("%d", &N);
    V.resize(N);
    for(int i=0;i<N;i++){ scanf("%d", V.begin()+i); }
    sort(V.begin(), V.end());
    for(int i=0;i<N/4;i++){
        res += (V[N-1-i] - V[i]) * 2; }
    printf("Case #%d\n", t);
    printf("%lld\n", res);
    return;
}

int main(void){
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(int i=0;i<T;i++){ solve(i+1); }
    return 0;
}

round1_03.cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long makeRes(int v){
    if(v < 2){ return 0; }
    return (long long)v * (v-1) / 2;
}

void solve(int t){
    int N;
    int a, b;
    int ext[2] = { 0, 0 };
    int extIdx = 0;
    
    int len[2] = { 0, 0 };
    int lenIdx = 0;
    int cur, vis, tmp;
    int met = 0;

    long long res;

    vector< vector< int > > edge;
    scanf("%d", &N);
    edge.resize(N+1);
    for(int i=0;i<N+1;i++){
        scanf("%d %d", &a, &b);
        edge[a].push_back(b); edge[b].push_back(a);
        if(edge[a].size() >= 3){ ext[extIdx++] = a; }
        if(edge[b].size() >= 3){ ext[extIdx++] = b; }
    }
    for(int i=0;i<3;i++){
        vis = ext[0];
        cur = edge[ext[0]][i];
        if(cur == ext[1]){ continue; }
        for(met=1;cur != ext[1];){
            tmp = cur;
            cur = (edge[cur][0] != vis)?edge[cur][0]:edge[cur][1];
            vis = tmp;
            met++;
        }
        len[lenIdx++] = met;
    }
    res = makeRes(len[0]) + makeRes(len[1]);
    printf("Case #%d\n", t);
    printf("%lld\n", res);
    return;
}

int main(void){
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(int i=0;i<T;i++){ solve(i+1); }
    return 0;
}

round1_04.cpp

#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>

#define max(a, b)   (((a)>(b))?(a):(b))
#define min(a, b)   (((a)<(b))?(a):(b))

using namespace std;

typedef long long lint;

int solve(){
    int N, L;
    vector< int > A;
    vector< int > B;
    int res = -1;
    int anc, hok;
    int tmp;
    scanf("%d %d", &N, &L);
    A.resize(N); B.resize(N);
    for(int i=0;i<N;i++){ scanf("%d", A.begin()+i); }
    for(int i=0;i<N;i++){ scanf("%d", B.begin()+i); }
    sort(A.begin(), A.end()); sort(B.begin(), B.end());
    for(int i=0;i<N;i++){ res = max(res, abs(A[i] - B[i])); }
    //
    if(res > L){ return -1; }
    //
    for(anc=hok=0;hok<N;hok++){
        tmp = (int)(lower_bound(B.begin(), B.begin()+hok, A[hok]-L) - B.begin());
        res = max(res, abs(A[hok]-B[max(anc, tmp)]));
        if(abs(A[hok]-B[hok+1])>L){ anc=hok+1; }
    }
    for(anc=hok=N-1;hok>=0;hok--){
        tmp = (int)(upper_bound(B.begin()+hok, B.end(), A[hok]+L) - B.begin())-1;
        res = max(res, abs(A[hok]-B[min(anc, tmp)]));
        if(abs(A[hok]-B[hok-1])>L){ anc=hok-1; }
    }
    return res;
}

int main(void){
    int T, res;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(int i=0;i<T;i++){ 
        res = solve();
        printf("Case #%d\n", i+1);
        printf("%d\n", res); }
    return 0;
}