코드포스 폭망 기념

코드포스 폭망기념 upsolving

Codeforces Round #800 Editorial 개요.

코드포스를 시작하고 그래도 계속 그린 퍼포먼스는 나오길래 답만 보고 넘겼었다.
그런데 이번 코포에서 정말 단 한문제도 못풀었다…
그래서 분노의 업솔빙을 해보려고 한다. ㅠㅠ
백준 플레가 코포 뉴비에서 헤매고 있다니 정말 분하고 부끄럽다.
업솔빙을 계기로 강해져보자

A. Creep

나를 눈물나게 한 문제이다.
접두사가 될 수있는 최대 점수는 전체 = abs(a-b)라고 생각을 했고, 앞에서부터 채워나가면서 이 abs(a-b)만 안넘으면 된다고 생각했다.
그래서 a, b를 모두 소진 할 때까지 Max = abs(a-b)를 넘기지 않으면서 넣는 과정을 계속했는데…ㅠㅠ 계속 틀렸다.
a와 b가 충분히 작기 때문에 O(a+b)로 해결할 수 있다고 믿었기 때문이다.
정답을 봤는데 비슷하다…다만 내가 신경쓰지 못한부분은 a==b이고 cnt가 계속 0이니까 라고 생각했는데 내가 cnt를 ++하고 비교했다는 것을 깨닫지 못한것이다…
아래 코드에서 Max를 max(1, Max)로 바꾸니 통과했다.

        int a, b;
        cin >> a >> b;
        int Max = abs(a-b);
        int cnt = 0;
        bool state;
        if(a>b) state = true;
        else state = false;
        
        int acnt = a, bcnt = b;
        for(int i=0;i<a+b;i++){
            if(state&&acnt){
                cout << '0';
                cnt++; acnt--;
                if(cnt==Max||acnt==0) {
                    cnt = 0;
                    state = false;
                }
            }else if(bcnt){
                cout << '1';
                cnt++; bcnt--;
                if(cnt==Max||bcnt==0) {
                    cnt = 0;
                    state = true;
                }
            }
        }

B. Paranoid String

A가 안풀려서 멘탈이 터진 상태로 B로 왔는데.
또 멘탈이 터졌다.
문제 이해부터 쉽지 않았는데 그냥 모든 01, 10, 또는 1, 0을 세라는 거구나라고 이해했다.
하지만 어떻게 문자열을 줄이느냐에 따라 paranoid string이 생길 수도 있고 안생길 수도 있었다.
나는 이 문제는 경우에 따라 나눠서 dp로 접근할까했는데 예제 4번에서 막혔다. 예제 4번 1001은 1,0,0,1, 10, 01, 01, 01 이렇게 8개 있는데 마지막 101의 01을 못세었다.
답을 봤는데… 역대급으로 간단했다.
그냥 전체 크기 + 10 or 01인걸 셀 때 index값만 해주면 되었다..덜덜덜…why?
예를 들어 s[m-1] != s[m] 일 때 s[m] = 0이라고 하면 110, 010의 경우가 있다. 둘다 10 -> 0 , 10 -> 0으로 만들 수 있다.
s[m] = 1이라고 하면 001, 101이 있고 이는 01 -> 1 , 01 -> 1로 둘다 만들 수 있다. 그니깐 저렇게 풀어도 되는것이다..ㅠㅠ

        cin >> n >> S, ans = n;
		for (int i = 1; i < n; ++ i)
			if (S[i] != S[i - 1])
				ans += i;
		cout << ans << '\n';

답이 long long으로 int형이 넘어간다는 것도 체크해야한다.

C. Directional Increase

A, B를 WA맞고 아주 살짝 건드린 문제.
문제를 이해함과 동시에 아 그냥 A, B만 팔까 싶었다.
어려워서 그랬다기 보다는 A,B도 못푸는데 무슨 C냐 하는 마음이였던 것같다.
총합은 무조건 0이고, 일단 문제를 보고 투포인터를 떠올렸고 앞에 포인터가 음수거나 뒤에 포인터가 양수면 실패하도록 설계했다. 하지만 예제 4번째꺼가 발목을 잡았다.ㅠㅠ
이 문젠 부분합을 이용하여 부분합 마지막이 0, 부분합 중간 부분에 음수가 있거나, 중간에 0이 껴있으면 실패하는 경우를 찾는 것이다.
부분합 + casework 문제였다.(할만했을지도…)

        if(ps[n]) { //부분 합 마지막이 0이 아님
            cout << "No\n";
            continue;
        }
        bool possible = true;
        for(int i=1;i<=n;i++) if(ps[i]<0) possible = false; // 부분합 중간에 음수가 있음
        bool zero = false;
        for(int i = 1;i<=n;i++){    //부분 합 중간에 0이 껴있음
            if(ps[i]==0) zero = true;
            else if(zero) possible = false;
        }

D. Fake Plastic Trees

여기서부터는 완벽하게 올업솔빙이다.
건들지도 못했다. 이번 코포는 나를 너무 자책하게 만들었다.
하지만 괜찮다. 못하는걸 어떡하겠어 더 실력을 갈고 닦아야지.
문제 이해를 대충해보니 greedy하게 풀 수 있을 것 같았다.
왜냐하면 부모는 무조건 자식에게 영향 받으므로 자식이 없는 노드 부터 생각을 해가면 부모의 경우의 수가 줄어 들것으로 예상했기 때문이다.
dfs로 자식에서 부터 올라면서 더하는 것을 구현한다.
근데 이거 그리디하게만 하면 된다는 것을 증명하기는 좀 까다로운 것 같다…

E. Keshi in Search of AmShZ

n은 정점, m은 간선으로 graph 모델링은 쉬운것같고, 방향이 있는 간선이라고 줬다.
이제 문제는 두가지 메시지를 보내서 서로 만나는 거리을 최소화하는 것이다.
최단거리니깐 다익스트라를 사용해봐야겠다는 직관을 얻을 수 있다.
keshi는 1에 AmshZ는 n에 있고 n에서 1까지 다익스트라 하면 된다.

F. Decinc Dividing

몰라… 걍 생략!