AtCoder Beginner Contest 300 후기 (ABC 300 3솔)

요약 : 어려움. 감떨어졌다

** ABC 298과 299는 디도스공격으로 인해 서버가 제대로 동작하지 않았고, unrated 처리되었고, 제대로 응시하지 않았음.

 

A  - 그냥 풀면 된다.

선언만 해놓고 cin으로 입력을 안받아서 1 WA

 

B  - 까다로움. 2차원 배열을 만든 뒤, 브루트 포스로 한칸씩 밀어보면서 검사한다

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

int main(void) {
    fastio;
    int H,W;cin>>H>>W;
    set<pair<int,int>> A,B,C;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            char t;cin>>t;
            if(t=='#')A.insert({i,j});
        }
    }
    
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            char t;cin>>t;
            if(t=='#')B.insert({i,j});
        }
    }

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            C.clear();
            for (auto k:A)
            {
                int a,b;
                a=(k.first+i)%H;
                b=(k.second+j)%W;
                C.insert({a,b});
            }
            if(C==B){
                cout<<"Yes";return 0;
            }
        }
    }
    cout<<"No";
    return 0;
}

B번치고 좀 많이 귀찮다. 실수없이 빠르게 구현하긴 좀 어렵지 않나

 

C  - B번도 까다로운데 얜 더 까다로움. 2차원배열 / 브루트포스 / 구현

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

int main(void) {
    fastio;
    int H,W;cin>>H>>W;
    int C[H+1][W+1]={0,};
    int vis[H+1][W+1]={0,};
    int ans[min(H,W)+1]={0,};
    for (int i = 0; i < H; i++)
    {
        string s;cin>>s;
        for (int j = 0; j < W; j++)
        {
            if(s[j]=='#')C[i+1][j+1]=1;
        }
    }

    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if(C[i][j]&&vis[i][j]==0){
                vis[i][j]=1;
                int ii=i,jj=j;
                while (ii+1<=H&&jj+1<=W&&C[ii+1][jj+1])
                {
                    ii++;jj++;
                    vis[ii][jj]=vis[ii-1][jj-1]+1;
                }
                ans[vis[ii][jj]/2]++;
            }
        }
    }

    for (int i = 1; i <= min(H,W); i++)
    {
        cout<<ans[i]<<" ";
    }
    return 0;
}

카카오 코테인가 소마인가 거기서 비슷한 문제를 봤는데.. 거기서는 가로세로 방향으로 놓인 십자가를 크기를 찾아내는 문제였고, 십자가끼리 엮여있기도 했음. 그러나 이번엔 대각선으로 놓인 십자가의 크기를 찾아내는 문제임.

처음엔 bfs나 dfs를 생각했으나, 문제의 조건 : 십자가끼리는 절대 인접하지 않음 에 의해, 문제가 간단해지고 브루트포스로 풀린다.

근데 이런 문제는 실수하기가 너무 쉽다. B번이랑 C번 문제 푸는 데 걸린 시간 좀 봐라. 카카오 코테같은데서 이문제 푸는 데 40분씩 걸리면 다른 문제 풀 시간이 어딨어

 

D - 에라토스테네스의 채를 만든다. 반복문을 돌리면서 불가능한 조건에서 break한다

필요할 때 제깍제깍 break해 줘야 시간 내에 풀린다. 대회 시간 내에 풀지 못했다.

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

vector<ll> sosu(ll maxnum){
	vector<ll> ans;
	bool eratos[maxnum+1]={0,};
	eratos[0]=1;eratos[1]=1;
	for (ll i = 2; i <= maxnum; i++)
	{
		if(eratos[i])continue;
		ans.push_back(i);
		for (ll j = i; j <= maxnum; j+=i)eratos[j]=1;
	}
    return ans;
}

int main(void) {
    fastio;
    ll N;cin>>N;
    vector<ll> ans = sosu(sqrt(N));
    ll cnt = 0;
    for (ll i = 0; i < ans.size(); i++)
    {
		ll ai = ans[i];
		if(ai*ai*ai*ai*ai>N)break;
        for (ll j = i+1; j < ans.size(); j++)
        {
			ll aj = ans[j];
			if(ai*ai*aj*aj*aj>N)break;
            for (ll k = j+1; k < ans.size(); k++)
            {
				ll ak = ans[k];
				if(ai*ai*aj*ak*ak>N)break;
				else cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}

이문제도 까다로웠다. 에라토스테네스의 체를 만드는 건 당연히 할 줄 알아야 하며,

이게 삼중 반복문으로 풀리는 문제인가?? 시간복잡도 내에 돌아갈 수 있는가? 에라체의 범위는 어떻게 잡아야 하는가?? 이런 감각을 요구하는 문제가 아닌가 싶다...

 

E번은 예제를 이해하기도 어려워 포기했다

 

Atcoder problems의 난이도 평가는 이러하다. D번까지는 무난하게 풀 수 있는 난이도였는데. 아쉬운 부분