AtCoder Beginner Contest 293 후기 (ABC 293 4솔)

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

저번처럼 ABCD를 풀고, E F번 문제를 보면서 정수론 문제 같다고 감을 잡았지만 풀지는 못했다.

이번 E F 문제는 특히 알면 풀고 모르면 못 푸는 경향이 강한 것 같다

도와줘요수학귀신

 

2503등을 하고 129점이 올랐다!!

다음 앳코더는 브론즈 승급전이라고 생각하고 더 열심히 해야겠다

 

 

A번 : 문자열, 1차원 배열, swap

문제 제목처럼 string의 홀수번과 짝수번을 swap해서 출력하기만 하면 된다

인덱스 범위를 넘기지 않도록 조심하자

 

B번 : 1차원 배열, 구현

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

int ary[200001];

int main(){
    fastio;
    int N;cin>>N;
    for (int i = 1; i <= N; i++)
    {
        int t;cin>>t;
        if(ary[i])continue;
        else ary[t]++;
    }
    

    vector<int> v;
    for (int i = 1; i <= N; i++)
    {
        if(!ary[i])v.push_back(i);
    }
    sort(v.begin(),v.end());


    cout<<v.size()<<"\n";
    for (int i:v)
    {
        cout<<i<<" ";
    }
    

    return 0;
}

예제 안돌리고 제출했다가 v.size를 출력 안해서 틀렸다

설명이 필요없다 시키는대로 하면 풀린다

 

C번 : 백트래킹 또는 bfs dfs

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
int H,W;
int ary[11][11];
int ans;
set<int> vis;
void bt(int x,int y){
    if(x==H&&y==W){
        ans++;
        return;
    }

    if(x+1<=H){
        if(!vis.count(ary[x+1][y])){
            vis.insert(ary[x+1][y]);
            bt(x+1,y);
            vis.erase(ary[x+1][y]);
        }
    }
    if(y+1<=W){
        if(!vis.count(ary[x][y+1])){
            vis.insert(ary[x][y+1]);
            bt(x,y+1);
            vis.erase(ary[x][y+1]);
        }
    }
}
int main(){
    fastio;
    cin>>H>>W;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin>>ary[i][j];
        }
    }
    vis.insert(ary[1][1]);
    bt(1,1);
    cout<<ans;
    return 0;
}

ary[1][1]의 정보를 vis에 넣어놓지 않았다가 틀렸다. 예제를 꼭 돌리자 나는 실수가 많다

백트래킹 외에도 bfs나 dfs로 풀 수 있을 것이라 생각한다. 나는 백트래킹이 제일 익숙해 백트래킹으로 짰다.

 

D번 : Union find

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

int N,M;
int acnt,bcnt;//사이클,사이클아님

int parent[200001];

int uf(int n){
    if(parent[n]==n)return n;
    return parent[n] = uf(parent[n]);
}

int main(){
    fastio;
    cin>>N>>M;
    for (int i = 1; i <= N; i++)
    {
        parent[i]=i;
    }
    for (int i = 1; i <= M; i++)
    {
        int a,c;
        char b,d;
        cin>>a>>b>>c>>d;
        if(uf(a)==uf(c)){//사이클
            acnt++;
        }
        else{
            parent[uf(c)] = uf(a);
        }
    }
    set<int> ss;
    for (int i = 1; i <= N; i++)
    {
        uf(i);
        ss.insert(parent[i]);
    }
    cout<<acnt<<" "<<ss.size()-acnt;
    return 0;
}

문제 설명에 2가지 색깔(red, blue)이 존재하는데, 이건 함정이다 그냥 쌩까고 유니온파인드만 돌리면 사이클을 찾을 수 있다

마지막에 for문을 한번 돌리면서 사이클 된 녀석의 개수와 사이클 안 된 녀석 개수를 체크하면서 그걸 출력하면 된다

D번문제로 저번에도 유니온파인드가 나왔는데, 맨날 유니온파인드만 나왔으면 좋겠다 D번 문제로 나올 수 있는 문제 중에선 유니온파인드가 젤 쉬운 것 같다

 

E번 : 정수론, 분할정복

제목이 Geometric Progression (등비 수열) 이다. 

분할정복을 이용한 거듭제곱만으로는 풀리지 않는다.

(1000000000^1000000000000)%998244353 을 분할정복을 이용한 거듭제곱으로 계산할 수는 있으나,

1부터 b까지 더하는 것만 해도 10^12 = 10000초가 걸리므로, 급수의 합을 구하는 것 역시 어떤 분할 정복 테크닉을 사용해야 한다.

 

그렇지만 나는 이 문제를 풀면서, 메모이제이션을 이용해 시간 복잡도를 줄여보려고만 하고 다른 해결책을 시도하거나, 찾지 못했다.

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

map<ll,ll> bans;

ll solve(ll a,ll b, ll c){
    if(b==0)return 1;
    if(bans.count(b))return bans[b];
    ll cnt = 1;
    ll ans = 1;
    a%=c;
    while (b)
	{
        if(bans.count(b-cnt)){
            ans*=a;
            ans%=c;
            ans*=bans[b-cnt];
            return ans%c;
        }
        if(b%2==1){
			ans*=a;
			ans%=c;
		}
		b=b>>1;
        cnt+=cnt;
		a*=a;a%=c;
        bans.emplace(cnt,a);
	}

    return ans%c;
}

int main(){
    fastio;
    ll A,X,M;cin>>A>>X>>M;
    ll aans = 0;

    bans.emplace(0,1);
    bans.emplace(1,A);

    for (ll i = X-1; i >= 0; i--)
    {
        ll tmp = solve(A,i,M);
        aans+=tmp;
        aans%=M;
    }
    cout<<aans;

    return 0;
}
// TLE code TLE code TLE code TLE code TLE code TLE code TLE code

친구 말로 이 문제는 정수론을 몰라도 적당히 급수의 점화식? 을 만들고 분할정복으로 응용할 수 있다면 풀 수 있다고 한다

비슷한 발상의 문제가 백준 분할정복 단계에 존재한다

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

피보나치 수의 성질을 이용해 행렬을 만들고 행렬의 분할정복으로 피보나치 수를 빠르게 계산하는 문제임

피보나치 수 역시 그 점화식이 수열과 비슷한 성질을 띄기 때문인가? 비슷하게 풀리나 보다

도와줘요수학귀신

 

F번

읽고 정수론이라는 생각은 들었다. 특히 소수의 성질을 이용하게 될 거라고 생각했음

왜냐면 16진수에 0과 1만 존재한다면, 8진수에도 0과 1만 존재하고, 2진수에도 0과 1만 존재한다는 사실을 나는 알고 있고

 

그러니까, 숫자 A를 b진수로 나타내었을 때 0과 1만 존재한다면 b진수의 약수에 대해서도 모두 성립할 것이라고 생각했다

그렇지만 시간이 부족해 E번문제에 시간을 투자하고 풀지는 않았다

 

 

---

업솔빙을 열심히 하자 특히 이번 E,F번 문제는 백준 레벨을 올리는 데 많은 도움이 될 것 같다.

왜?? 정수론은 알면 풀고 모르면 못푸는 경향이 강하고, E,F번에서의 배움을 응용할 곳이 많을 것 같다

근데 이런 문제가 대기업 코딩테스트에 나올지는 의문이다