[대회] SUAPC 2022 Winter 참여기

https://icpc-sinchon.io/suapc

SUAPC는 신촌지역 5개 대학(서강, 숙명, 연세, 이화, 홍익)의 학부생 및 대학원 1년 차를 대상으로 하는 프로그래밍 대회입니다. 대회 문제는 서울 리저널의 문제 출제 경향을 따르며 제한시간 동안 얼마나 많은 문제를 정확하게 풀 수 있는지를 평가하여 순위를 결정합니다.

서강대학교, 숙명여자대학교, 연세대학교, 이화여자대학교, 홍익대학교의 재학/휴학생인 경우 누구나 참여 가능합니다. (단, 졸업 1년 차와 대학원생은 참여 가능하되, 대회 중 스코어보드에는 보이지 않습니다.)

 

이 블로그는 2022 winter Suapc에 참여한 후기 및 문제 풀이 관련 타임라인을 정리한 내용입니다.

 

0. 결과

팀 : Down the Code (5 Solve)

1. TMI

목표는 3 solve였기 때문에 매우 예상하지 못했던 성과였다. 작년 여름과 비교해도 만족할 만한 성과였다.

SUAPC 2021 Summer 때의 처참한 성과...(1 solve) vs SUAPC 2022 Winter (5 solve)

원래는 교내 동아리 내부에서 나가는 것이 정석이지만 피치 못할 사정으로 새로운 팀을 찾아야 했다. 다행히 팀원을 찾아서, "cdnnnl(효신님), fungod12(동은님)"과 함께 백준 그룹을 만들어서 남은 2주 정도 빡세게 공부하기로 했다.

첫 주는 정말 빡세게 공부해서, 매일 연습 만들고 공부했었다.

둘째 주에는 지치기도 했고, 내가 약속과 팀 대항전 그리고 이사 준비로 바빠서 많은 준비를 하진 못했다. 연습 7이 마지막 연습이었다. 

연습의 흔적... 연습으로도 만들고 문제집으로도 만들어서 한번에 보이진 않지만 매일 몇시간씩 투자했다.

2. 문제풀이(Timeline)

처음에 잡았던 것은 C, 전부 읽고 있었는데 scoreboard에 first solve가 뜨기에 바로 잡았다.

(12:08:23) 마음이 급해서 그냥 제출했다가 틀렸다... (제발 이런 실수 좀 그만...)

(12:16:25) 디코에 보내봤더니 초기화 안 했다는 점 짚어주셔서 변수 초기화해서 새로 제출해서 1 solve.

• C. 카카오뷰 큐레이팅 효용성 분석

//카카오뷰 큐레이팅 효용성 분석
//remember to initialize every variables...
#include<iostream>
using namespace std;

int main(){
    int N, arr[1000001];
    long long all=0, notmy=0;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> arr[i];
    for(int i = 0; i < N; i++){
        int chk;
        all += arr[i];
        cin >> chk;
        if(chk != 1) notmy+=arr[i];
    }
    cout<< all << "\n"<<notmy << "\n";
}

그 이후, 잡을 문제를 찾다가 scoreboard 보니 A, G, L 순으로 많이 푸신 듯하였다. cdnnnl이 G, fungod12이 L, 나는 K를 잡기로 하였다.

(12:43:19) G를 제출하셨고, 틀렸다. 단순 계산으로는 풀리지 않을 문제인 것 같았고, fungod12이 롤링 해시나 문자열 압축을 말씀하셨지만, 일단 넘어가기로 했다.

• G code

#include <iostream>
using namespace std;

int N;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    string s;
    cin >> s;

    int answer = 0;
    int tree, grass, fence, people;
    tree = grass = fence = people = 0;

    for(int i =3 ; i<=N ; i+=3){
        for (int j = 0; j < N - (i-1); j++) {
            tree = grass = fence = people = 0;
            for (int k = j; k <= j + i - 1; k++) {
                if (s[k] == 'T') tree++;
                else if (s[k] == 'G') grass++;
                else if (s[k] == 'F') fence++;
                else people++;
            }
            if (tree % 3 == 0 && grass % 3 == 0 && fence % 3 == 0 && people % 3 == 0)
                answer++;
            //cout << "answer: " << answer << "\n";
        }
    }
    cout << answer << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const lint p = 27;

int psz, ssz;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0);
    string s, P;
    cin >> s >> P;
    ssz = s.size(), psz = P.size();

    lint ph = 0, h = 0, pp = 1;
    for (int i = 0; P[i]; i++) {
        ph = ph + 1LL * P[psz - 1 - i] * pp;
        h = h + 1LL * s[psz - 1 - i] * pp;
        if (i < psz - 1) pp *= p;
    }
    if (ph == h) return cout << 1, 0;
    for (int i = 1; i <= ssz - psz; i++) {
        h = p * (h - 1LL * s[i - 1] * pp) + s[i + psz - 1];
        if (ph == h) return cout << 1, 0;
    }

    return cout << 0, 0;
}

 

(12:49:50)(12:53:31) K번을 제출하였으나, 틀렸다. 출력 오류라 생각해서 재시도하였으나 다시 틀렸다. 좌측 괄호는 괄호가 닫힌 경우는 유지되어야 하고, 우측 괄호는 가장 오른쪽 괄호를 제외하면 없애도 된다고 생각하였다.

 

(13:14:40) fungod12이 A번과 아래 문제가 동일하다는 가설을 제시하셨고, 내가 union_find 알고리즘을 제시하였다. 같은 집합 내부에 있는 사람들 중 한 명을 튜터로 선택하면 되기 때문에 집합 내 인원수들의 곱을 구하면 된다고 생각하였다. 일단 첫 회에는 실패하였다.

- 참고한 문제 번호

[알고리즘][15][백준_2533] - 사회망 서비스

 

(13:46:09) 이후 cdnnnl께 K번 설명 중 내가 짠 알고리즘 상에 오류를 발견해서 재시도하였고, 성공했다. 자세한 내용은 아래 코드 아래 그림 참조.

• K. 올바른 괄호

//올바른 괄호
//Needed to think about how to solve all the cases by sorting cases 1 by 1
#include<iostream>
#include<string>
using namespace std;

string s;
int l=0, r=0, l_minus = 0;
bool chk;

int main(void){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    cin >> s;
    if(s.at(0) == ')') {
        cout << "1" <<"\n";
        return 0;
    }
    for(int i = 0; i < s.length(); i++){
        if(l<r && i != s.length()-1){ // )가 더 큰 경우가 생기면 그것 포함 그 전의 ) 중 하나 삭제해야함 
            cout << r << "\n";
            return 0;
        }
        else if(l == r){
            l_minus = l;
        }
        if(s.at(i) == '(') l++;
        else r++;
        // cout << i << " : " << l << ", "<< r << "-" << l_minus << "\n";
    }
    //front (( 인 경우 l, (직후에 )가 나오는 경우 ㅣ-1
    //end ))인 경우 r, 직전에 ( ) 인경우 r-1
    
    if(r>l && s.at(s.length()-2) == ')'){
        cout<<r<<"\n";
    }
    else if(r>l) cout<<r-1<<"\n";
    else if(l_minus == 0 && s.at(1) !=  '('){
        cout << l-1 << "\n";
    }
    else cout << l-l_minus<<"\n";
    return 0;
}

fungod12은 L번을 잡아서, 초반에는 dp로 풀 수 있을지 고민하였으나, N이 너무 커서 가능하지 않아 규칙을 찾고 계셨다.

(14:47:13) 수학적인 규칙을 찾다가 0이 마지막 자리에 오는 펠린드롬수가 없다는 점에서 착안하여 규칙을 찾으셨고 바로 성공하셨다.

• L. 팰린드롬 게임

//팰린드롬 게임
//10^n numbers cannot be made only from pelindrom numbers
#include <iostream>
#include <algorithm>
using namespace std;

int T;

using ll=long long;

int main() {
    cin>>T;
    while(T--){
        ll N;
        cin>>N;
        if(N%10==0) cout<<1<<'\n';
        else cout<<0<<'\n';
    }
    return 0;
}

J번을 잡았다. 숫자 1들을 가진 수들(11,111,1111...)의 약수인지 아닌지 판별하는 문제였다. 1의 개수가 소수가 아닌 경우에는 1111= 11*101처럼 만들 수 있어 소수인 경우만 확인하면 되는 문제였다. 11, 111, 11111, 1111111, 11111111111... 1의 개수가 소수인 이런 숫자들을 만들어야 하는데 for문으로 만드는 게 최선일지 고민하다가 결국 for 문으로 만들었다. 관건은 long long의 범위를 넘어가지 않도록 답을 구하는 것이었다.

 

(15:35:55) long long의 범위를 넘어가는 연산을 하면 음수가 나온다는 점에서 착안하여 그 경우를 해결했고, J를 성공했다.

• J. 일이 너무 많아...

//일이 너무 많아...
//포함 배제의 원리(in Set Thorem)
//1111 = 11의 multiplication이라는 점 이용
//only Prime Number 개수만큼 1만 계산
//Long long의 범위를 넘어가는 수의 계산
#include<iostream>
#include<cmath>
using namespace std;
long long N, ans = 0, tmp;
int pn[30], indx = 0;

bool isPN(long long x){
    for(long long i=2;i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

long long calc1(int n){
    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans*=10;
        ans++;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 2; i < log10(N)+1; i++){
        if(isPN(i)){
            pn[indx++] = i;
            ans += N/calc1(i);
        }
    }
    for(int i = 0; i < indx; i++){
        for(int j = i+1; j < indx; j++){
            tmp = calc1(pn[i]) * calc1(pn[j]);
            if(tmp  > N || tmp < 0)  break;
            else {
                ans -= N / tmp;
                //cout << pn[i] << ", " << pn[j] << " - " << "\n";
            }
            for(int k = j + 1; k< indx && pn[k] < 17; k++){
                tmp = calc1(pn[i]) * calc1(pn[j]) * calc1(pn[k]);
                if(tmp > N || tmp < 0) break;
                else {
                    ans += N / tmp;
                    //cout << pn[i] << ", " << pn[j] << ", " << pn[k] <<  "+\n";
                }
                for(int p = k+1; p < indx && pn[p] < 17; p++){
                    tmp = calc1(pn[i]) * calc1(pn[j]) * calc1(pn[k]) * calc1(pn[p]);
                    if(tmp > N || tmp < 0) break;
                    else {
                        ans -= N / tmp;
                        //cout << pn[i] << ", " << pn[j] << ", " << pn[k] << ", "<< pn[p] <<  "-\n";
                    }
                }
            }  
        }
    }
    cout << ans << "\n";
    return 0;
}

fungod12은 A번 튜터와 튜티 관계의 수, 나는 F번 mod와 쿼리 문제를 잡았다.

(16:15:00) F번 실패. 답에 문제는 없었으나, mod 연산의 속도 문제를 해결할 방법이 떠오르지 않아서 실패했다.

• F. mod와 쿼리

#include<iostream>
using namespace std;
long long arr[100005],ans = 0;
int N, Q, tmp, x, i;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    cin >> Q;
    while(Q-->0){
        cin>> tmp;
        ans = 0;
        switch(tmp){
        case 1:
            cin >> x;
            for(int i = 0; i < N; i++){
                ans += arr[i] % x;
            }
            cout << ans << "\n";
            break;
        case 2:
            cin >> x;
            for(int i = 0; i < N; i++){
                ans += x % arr[i];
            }
            cout<< ans << "\n";
            break;
        case 3:
            cin >> i >> x;
            arr[i-1] = x;
            break;
        }
    }
}

(16:59:01) A. 튜터-튜티 관계의 수 성공. cdnnnl이 테스트 케이스 올려주신 것 덕분에 해결할 수 있었다.

• A. 튜터-튜티 관계의 수
• 테스트케이스
  100 5
  3 8
  8 3
  1 2
  2 1
  3 2

//튜터 튜티 관계의 수
//union find 라는 것은 딱 보고 느껴졌는데 구현과정에서 계속 에러가 난 문제.
//같은 입력값이 반복되는 경우도 생각해야 한다는 것을 다시 실감함.
#include <iostream>
using namespace std;
using ll=long long;
ll p[200010];
ll height[200010];
ll cnt[200010];
long long int ans=1;
ll N,M;
ll Find(ll x){
    if(p[x]==-1) return x;
    return p[x]=Find(p[x]);
}
bool Union(int u,int v){
    u=Find(u);v=Find(v);
    if(u==v) return false;
    if(height[u]<height[v])swap(u,v);
    p[v]=u;
    cnt[u]+=cnt[v];
    cnt[v]=1;

    if(height[u]==height[v]) height[u]++;
    return true;
}
int main() {
    cin>>N>>M;
    for(ll i=1;i<=N;i++) {p[i]=-1;cnt[i]=1;}
    while(M--){
        int a,b;
        cin>>a>>b;
        Union(a,b);
    }
    for(ll i=1;i<=N;i++){
      ans=ans%1000000007*cnt[i]%1000000007;
    } 
    cout<<ans%1000000007;
    return 0;
}

그렇게 5 solve로 SUAPC WINTER 2022가 마무리되었다.

정말 많이 틀리고 고생했지만 많이 맞았다.

3. 후기

 

I. 이 멋진 수열에 쿼리를!

 - 이 문제 해설을 들어보니 최근에 공부했던 Linear Algebra 관련 문제였던 것 같아서 아쉬웠다... 행렬을 이용하면 풀 수 있었을 것 같은데 애초에 적용할 생각조차 하지 못했던 것은 나의 실책이었다고 생각한다... 공부를 했으면 적용할 때까지 문제를 좀 풀어봐야 할 것 같다는 생각이 마구 들었다.

 

이번에 제대로 SUAPC를 준비하면서 알고리즘 강화 기간을 잡고 알고리즘에만 집중할 수 있어서 좋았던 것 같다. 팀원 분들도 잘 모였고.. 앞으로도 할 일 있으면 같이 해보기로 했다. 그냥 헤어지긴 아쉬운 팀플이라니... 그런 게 존재할 수 있었던 거였다ㅋㅋㅋ

 

4. 문제 및 풀이 확인

https://www.acmicpc.net/board/view/85025

글 읽기 - SUAPC 2022 Winter 종료