[Codeforces] Round 929 (Div. 3) 후기

https://codeforces.com/contest/1933

Dashboard - Codeforces Round 929 (Div. 3) - Codeforces

https://codeforces.com/blog/entry/126560

Codeforces Round 929 (Div. 3) Editorial - Codeforces

 

---

2024.03.01

저번 Round 927 때처럼 빠르게 4솔만이라도 하면 오늘 민트찍을 수 있지 않을까?!?!? 하며 시작했던 라운드.

하지만 결국... C번에서 이상하게 오래걸리는 바람에 A,B,C,D 4솔에 E번 긁다가 2틀 당하고 마무리..

그래도 다행인건 레이팅이 줄지는 않았다는거? 26점 올라서 현재 레이팅은 1340이다. 

개강하기 전에 민트를 찍고싶었지만.. 그렇다고 Div2에 도전하기에는 너무 쫄리기 때문에....

 

지금 읽고있는 종만북을 먼저 다 읽고, Div2 버츄얼 돌리면서 코포 문제 스타일에 익숙해질 시간이 필요할 것 같다.

개강 전 민트는 결국 실패했지만, 종강 전 민트는 제발 할 수 있었으면 좋겠다..

 

 

---

A. Turtle Puzzle: Rearrange and Negate (00:01)

문제 안읽고 예제만 보고 푼 문제.

오늘 민트를 찍을거라는 기대감과 함께 1분만에 풀었다. 

그냥 단순히 입력값의 절대값을 다 더해주면 되는 문제.

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        int n;cin>>n;
        ll sum = 0;
        rep(i,0,n){
            int x;cin>>x;
            sum+=abs(x);
        }
        cout<<sum<<'\n';
    }
}

 

 

---

B. Turtle Math: Fast Three Task (00:11)

입력값에 대해서 값을 하나 없애거나, 특정값에 1을 더해줌으로서 최소 몇번의 연산안에 입력의 합을 3의 배수로 만들 수 있는지 찾는 문제.

우선 정답은 0,1,2 중 하나라는 것은 금방 찾아낼 수 있었다. 

입력값의 합을 3k, 3k+1, 3k+2 로 나타내보자.

 

1. 합이 3k일 때, 

 연산할 필요가 없으니 0을 출력한다.

2. 합이 3k+2일 때,

 1을 더해주는 연산을 통해 확정적으로 3의 배수로 나타낼 수 있으나 1을 출력한다.

3. 합이 3k+1일 때,

 우선 1을 더하는 연산을 2번 진행하면 확정적으로 3의 배수를 만들 수 있으니 정답은 최대 2이다.

 우리가 찾아야 하는 것은 정답이 1이 될 수 있는지. 즉, 배열값을 하나 없애서 3의 배수를 만들 수 있는 지이다.

 이를 위해서 3k+1을 만들 수 있는 배열 값의 입력이 들어왔는지 저장해둔다.

 만약 입력이 들어왔다면 그 배열값을 지움으로서 3의 배수로 만들 수 있으므로 1을 출력하고, 

  입력이 들어오지 않았다면, 어떤 배열값 한개를 지워도 3의 배수로 나타낼 수 없으므로 2를 출력한다.

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> v(n);
        ll sum=0;
        vector<int> cnt(3);
        rep(i,0,n){
            cin>>v[i];
            cnt[v[i]%3]++;
            sum+=v[i];
            // cout<<v[i]<<' ';
        }
        // cout<<'\n';

        if(sum%3==0){ //0이면 할거없고
            cout<<0<<'\n';
            continue;
        }
        if(sum%3==2){ //2면 1더해주면 되고
            cout<<1<<'\n';
            continue;
        }
        if(sum%3==1 && cnt[1]>0){ //1이면?
            cout<<1<<'\n';
            continue;
        }
        cout<<2<<'\n';
        

    }
}

 

 

---

C. Turtle Fingers: Count the Values of k (00:48)

이 문제에서 헤메지만 않았으면 민트 찍었을 수도 있었을 텐데... ㅠ

우선 t가 10'000, l이 최대 1'000'000이고, a,b가 2보다 크기 때문에 x,y값을 브루트 포스로 찾을 수 있음을 알 수 있다. 

그리고 정수 x,y가 존재하기 위해선 k는 항상 l의 소인수가 되어야 한다. 

l의 소인수를 우선 구해두고, 소인수, x,y값을 하나 하나 대조해보면 된다. 

소인수 구하고.. 최대 x, 최대 y, 다 구현하고... 거듭제곱 빠르게 하려고 함수도 만들고 이것저것 다 했는데,,,

이렇게까지 안해도 풀리나보다..

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
vector<int> func(int n){
    vector<int> v;
    for(int i=1;i*i<=n;i++){
        if(n%i==0) v.push_back(i);
    }
    for(int j=(int)v.size()-1;j>=0;j--){
        if(v[j]*v[j]==n) continue;
        v.push_back(n/v[j]);
    }
    return v;
}
ll involution(int a, int b) {
	if(b==0) return 1;
	else if(b==1) return a;
	ll tmp = involution(a, b / 2);
	if(b%2) return tmp*tmp*a;
	else return tmp*tmp;
}
int sol(int a,int b, int val){
    int mxx=0, mxy=0;
    while(pow(a,mxx)<=val) mxx++;
    while(pow(b,mxy)<=val) mxy++;
    int cnt = 0;
    for(int x=0;x<=mxx;x++){
        for(int y=0;y<=mxy;y++){
            ll cal = involution(a,x) * involution(b,y);
            if(cal==val) return 1;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        int a,b,l; cin>>a>>b>>l;
        vector<int> v = func(l);
        ll cnt = 0;
        for(int i=0;i<v.size();i++){
            int tmp = v[i];
            int ans = sol(a,b,l/v[i]);
            cnt+=ans;
        }
        cout<<cnt<<'\n';
    }
}

 

 

---

D. Turtle Tenacity: Continual Mods (01:13)

배열을 어떻게 잘 정렬해서 a1 mod a2 mod ... an mod != 0을 만들면 되는 문제.

 

처음엔 그냥 '정렬해놓고 돌려보면 되나?' 했는데 4번째 테케 보니까 그건 아닌 것 같더라.

게다가 그래도 div3 D번인데 무지성 정렬로 풀리겠나? 싶기도 했고..

 

일단 생각해보면 nk mod k = 0이므로 이런 식이 안만들어지게끔 코드를 짜면 되겠다는 생각이 들었다. 

이 생각을 하면서 8번 테케를 봤는데, nk mod k의 형태를 피하는 방법이 없네?

게다가 최대 공약수 3으로 나누니 1이 2개가 나오네?

 

여기서 1의 개수를 보고 추론을 해보았다.

gcd로 다 나누고, 1이 2개 이상이면 무조건 NO를 출력해야 된다는 것을 찾았다.

1 2개를 어디에다 위치시켜도 무조건 0을 만들 수 없더라. 

그래서 1이 0개,1개일때도 생각을 해봤는데... 

수학적 지식이 부족한 나에게는 이건 무리였고,,, 그래도 2개 이상이면 안된다는 걸 알았으니까 코드를 짜봤다

그리고 틀리면 어쩔수 없는거지~ 하면서 제출했는데.. 맞았다 ! ? 

 

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll t; cin>>t;
    while(t--){
        int n; cin>>n;
        vector<int> v(n);
        int mn=2e9;
        rep(i,0,n){
            cin>>v[i];
            mn = min(mn,v[i]);
        }
        bool flag = 1;
        rep(i,0,n){
            if(v[i]%mn==0){
                continue;
            }
            else{
                flag = 0;
            }
        }
        if(flag){
            rep(i,0,n){
                v[i]/=mn;
            }
        }
        int cnt = 0;
        rep(i,0,n){
            if(v[i]==1) cnt++;
        }

        if(cnt>=2) cout<<"NO\n";
        else cout<<"YES\n";

    }
}

gcd는 아무리 커봤자 배열의 최소값보다 클 수 없으므로 최소값을 배열의 다른 값으로 나눌 수 있는지로 코드를 짰다.

근데... 이제와서 생각해보니 최소값이 gcd보다 클 수도 있는데... 왜 이렇게 짠건지...

더 어이가 없는건 이게 그 때 당시 왜 맞았는지.... ;;;;

Proof By AC를 해버렸다 ㅎ...

 

 

에디토리얼을 보니까 gcd가 아니라 최소값에 대한 성질 파악이 중요한 문제였다. 

오름차순 정렬했을때

1. 첫번째, 두번째 원소가 다르다면 mod 계산값은 항상 첫번째 원소이다. 즉 무조건 YES

2. 첫번째, 두번째 원소가 같거나 배열값중에 첫번째원소와 나누어 떨어지는 원소가 있다면 NO, 그 외에는 YES이다.

 

사실 결국 운이 좋아서 맞은 문제였다. 풀고나서 조금 찝찝했는데, 그래도 원인을 알았으니 OK.

 

 

---

 

E. Turtle vs. Rabbit Race: Optimal Trainings

5솔 하고싶어서 진짜 열심히 풀었는데... 

누적합 쓰는 거고 r값을 어떻게 잘 빠르게 구하기만 하면 되는거고... 식을 세워보니 오목함수인거까지 찾았는데...

삼분탐색이라는 것 자체를 몰라서 시간초과가 났다.. 

삼분탐색이라는게... 거의 잘 안쓰다보니 공부안하고 걍 패스했는데 여기서 발목을 잡을 줄은....

많이 아쉽긴 했지만,, 뭐 내가 부족했던거니까 ㅎ;

그래도 레이팅 올랐으니 만족!