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

사람들이 참여를 별로 안했는지?? 순위가 잘 나왔다

잘하면 다음 앳코더 때 그린에 도착할 수 있겠다

 

E F G번 문제는 읽어봤는데도 뭐 할 수 있는게 없더라. 수련이 필요하다.

 

그건 그렇고 또 콘테스트 초반에 서버가 터졌다

이거 또 unrated처리되나 하고 조마조마했다

 

A. 

A번은 언제나 실수만 안하면 된다

 

B. 반복문, 1차원 배열

B번 역시 실수만 안하면 된다

예제만 몇 번 돌려보면 실수 안 할 문제

 

C. 문자열

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
int cnta[26],cntb[26];
int at,bt;
int main(void) {
	fastio;
    string S,T;cin>>S>>T;
    for (char i:S)
    {
        if(i=='@')at++;
        else cnta[i-'a']++;
    }
    for (char i:T)
    {
        if(i=='@')bt++;
        else cntb[i-'a']++;
    }
    string zz = "atcoder";
    for (char  i:zz)
    {
        if(cnta[i-'a']>cntb[i-'a']){
            int tz = cnta[i-'a']-cntb[i-'a'];   
            bt-=tz;
            cntb[i-'a']+=tz;
        }
        else if(cnta[i-'a']<cntb[i-'a']){
            int tz = cntb[i-'a']-cnta[i-'a'];   
            at-=tz;
            cnta[i-'a']+=tz;
        }
    }
    for (int i = 0; i < 26; i++)
    {
        if(cnta[i]!=cntb[i]){
            cout<<"No";return 0;
        }
    }
    if(bt!=at){
        cout<<"No";return 0;
    }
    else if(at<0||bt<0){
        cout<<"No";return 0;
    }
    cout<<"Yes";
	return 0;
}

이거 좀 까다로운데 그냥 잘 카운팅하고 마지막에 조건 몇 개 안 빼먹으면 된다

 

D. 문자열, 그리디

제목이 비트마스크지만 별거 없는 문제이다

N을 초과하지 않는 가장 큰 수를 주어진 이진수로 만들어내면 된다, 그러기 위해 ?가 있는 위치 중 가장 큰 위치 부터 넣을 수 있는지 검사해 보고, 넣을 수 있다면 넣는다.

주어진 S의 길이는 60이므로, 숫자가 커봤자 2^61이고, 이는 long long으로 표현 가능한 숫자이다.

 

E. 복잡한 bfs, 그리디

못풀었지만 bfs와 그리디라는 생각이 든다. 백준에 나온다면 플래티넘 이상의 난이도가 붙을 것 같다.

생각해본 풀이는 이러하다.

1. 스타트에서 골로 갈수 있는지 확인
2. 골로 가는 데 남는 무브가 총 몇번인지 확인
3. 골로 가는 최단루트에서 가장 가까운 캔디부터 그리디하게 추가
4. 근데 캔디가 여러개일 경우 최단거리가 계속 달라지는데 이 부분을 어캐함

비슷한 문제가 백준에 있을 것 같고 고난이도 bfs문제를 좀 많이 풀어봐야 할 것 같음

 

F. 확률/조합/정수론? 앳코더에 자주 보이는 유형의 문제

일단 모듈로 998244353 저녀석 나오면 머리가 아프다

답이 매우 크거나 분수꼴로 나온다는건데

앳코더에 많이 나오는 유형이니만큼 모아서 한번 풀어볼 필요가 있다고 생각함

 

G. 기하

직선 위에 몇개의 점들이 있는지 찾고, 직선끼리 교점이 발생하고, 그 교점이 x<0에 있고,,, 그런 부분을 따지는 문제인 건 알겠으나

일반적인 루트로 알고리즘을 접한 사람들이라면 기하에 약하다고 생각하고 나도 그렇다

CCW정도밖에 모른다

특히 C++로 직선의 방정식이 어떻게 표현되고 그 위에 점이 있는지 판별하는 방법은 궁금한 부분이었다

에디토리얼을 보고 공부할 필요가 있음