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

난이도는 평이했는데 C랑 D에서 간단한 처리를 빼먹었더니 말렸다

B는 개 귀찮은 구현이라 시간이 걸렸다

 

 

A : 틀리면바봉

 

B : 잘 보고 그냥 구현

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

int main(void) {
    fastio;
    int N;cin>>N;
    vector<string> v(N);
    for (int i = 0; i < N; i++)
    {
        cin>>v[i];
    }
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if(i==0&&j==0){
                cout<<v[i+1][j];
            }
            else if(i==0){
                cout<<v[i][j-1];
            }
            else if(j==0&&i==N-1){
                cout<<v[i][j+1];
            }
            else if(j==0){
                cout<<v[i+1][j];
            }
            else if(i==N-1&&j==N-1){
                cout<<v[i-1][j];
            }
            else if(i==N-1){
                cout<<v[i][j+1];
            }
            else if(i==0&&j==N-1){
                cout<<v[i][j-1];
            }
            else if(j==N-1){
                cout<<v[i-1][j];
            }
            else{
                cout<<v[i][j];
            }
        }
        cout<<"\n";
    }
    
    return 0;
}

i==0 i==N-1 j==0 j==N-1 인 경우를 생각하면서 예외처리를 해주고 안쪽 것들은 그대로 출력

이런문제 싫다

 

C : 정렬 또는 pq를 이용해 지속시간이 짧은 알약부터 하나씩 제거

pq, queue, stack같은 STL를 쓸때 항상 조심해야 할 부분은, 그것들이 empty일때의 동작을 항상 고려해야 한다는 것이다 나의 경우 저 !qq.empty()처리를 해주지 않았더니 TLE가 나서 고치는 데 시간이 많이 걸렸다

 

D : 쉬운 bfs

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

int main(void) {
    fastio;
    int N1,N2,M;cin>>N1>>N2>>M;
    vector<vector<int>> vv(N1+N2+1);
    for (int i = 0; i < M; i++)
    {
        int a,b;cin>>a>>b;
        vv[a].push_back(b);
        vv[b].push_back(a);
    }

    queue<int> qq;
    int vis[N1+N2+1];memset(vis,0,sizeof(vis));
    qq.push(1);
    vis[1]=1;
    int a1 = 1;
    while (!qq.empty())
    {
        int cur = qq.front();
        qq.pop();
        for (int i:vv[cur])
        {
            if(vis[i])continue;
            qq.push(i);
            vis[i]=vis[cur]+1;
            a1 = max(a1,vis[i]);
        }
    }

    qq.push(N1+N2);
    vis[N1+N2]=1;
    int a2 = 1;
    while (!qq.empty())
    {
        int cur = qq.front();
        qq.pop();
        for (int i:vv[cur])
        {
            if(vis[i])continue;
            qq.push(i);
            vis[i]=vis[cur]+1;
            a2 = max(a2,vis[i]);
        }
    }
    cout<<a1+a2-1;
    return 0;
}

1부터 bfs하면서 최장거리 구하고

N부터 bfs하면서 최장거리 구해서 그거 두개 더한거 -1을 출력하면 되는데

N이 2인경우(1 과 2 를 연결하면 결과가 1이 나와야 함)를 고려하지 않아서 틀렸다

 

 

E : 트리, dp?