코드포스 - 3솔의 벽

3솔의 벽이 너무 높다..

Codeforces Round #801, #802 div2 개요.

벌써 코포를 시작한지 한달 정도가 넘어간다.
div2만 들어서면 2솔밖에 못한다..
3솔의 벽이 너무 높다. 아이디어도 못떠올리는 경우가 대다수이다.
“dp 같긴한데…, greedy같긴한데..”생각만하고 못풀 때도 많다.
문제점 잡기가 어렵다. 3솔의 벽을 깨보기 위해 이번에는 C, D만 업솔빙 해보려고 한다.

801 C. Zero Path

문제를 조금 읽고 보면 dp같긴했다. 평소 2차원 dp의 좀 복잡한 형태는 항상 못풀었었고 자신감이 없었따…
dp가 맞긴맞았는데 잘못 짚었다. 4칸을 기준으로 보면 상황은 다음 그림과 같다.

보면 2, 0, -2밖에 되지 않는다. 따라서 경로를 적절히 조절하여 2씩 줄이거나 늘릴 수 있다는 뜻이다.
즉 끝점에서의 min, max값이 min <= 0 <= max 이고 2, 0, -2 단위면 적절히 조절하여 0을 만들 수 있다는 뜻이다.

mindp[0][0] = maxdp[0][0] = grid[0][0];
for(int i=1;i<n;i++){
mindp[i][0] = maxdp[i][0] = mindp[i-1][0]+grid[i][0];
}
for(int j=1;j<m;j++){
    mindp[0][j] = maxdp[0][j] = mindp[0][j-1] +grid[0][j];
}
for(int i=1;i<n;i++){
    for(int j=1;j<m;j++){
        mindp[i][j] = min(mindp[i-1][j], mindp[i][j-1]) + grid[i][j];
        maxdp[i][j] = max(maxdp[i-1][j], maxdp[i][j-1]) + grid[i][j];
       }
}   

if((maxdp[n-1][m-1]%2)||mindp[n-1][m-1]>0||maxdp[n-1][m-1]<0) cout << "NO\n"; 
else cout << "YES\n";

801 D. Tree queries

C가 자신이 없었기에 contest당시에는 D를 더 오래봤다.
근데 끝나고 디코반응같은걸 보니 D가 은근히 복병이었던것 같다.
그래프를 만들고 트리의 지름 문제 처럼 접근하려고 했다. DFS해서 가장 멀리 있는 것을 찾고, 그 다음 남은 서브트리를 찾고,..그런식으로..
예제 3번조차 잘 안됐다. 아이디어가 틀렸던 것 같다.
업솔빙도 오래걸렸다. 위의 문장을 쓰고 2시간이 지났다 ㅋㅋㅋㅋ
내가 영어를 못하는건지 문제가 눈에 하나도 안들어왔는데 이제야 좀 알겠다.
차수가 1이면 1개로 그냥 판단된다. 차수가 2여도 한방에 그냥 판단된다.
그니까 차수가 3개이상일 때만 판단하려면 2번이상 봐야한다. 근데 이걸 볼때도 루트기준으로 (서브트리에서 온 거) + (일자인거 갯수-1)을 해줘야한다.
그냥 무작정 차수가 3개이상이면 degree-1 하고 더하면 문제가 된다.
왜냐하면 서브트리를 판단할 때 썼던 간선이 다른걸 판단 할 때 또 쓰여서 중복으로 세질 수 있기 때문이다.
그래서 각 루트를 기준으로 세서 최소값을 출력한다.

int dfs(int i, int p) {
    int sm = 0, z = 0;  //sm은 서브트리에서 온 k개수, z는 서브트리 중 일자인거 개수이다
    
    for (int j : tree[i]) if (j != p) { //부모노드 빼고 검사하고
        int x = dfs(j, i);
        sm += x;
        if (x == 0) //일자면
            z++;
    }
    
    return sm + max(0, z - 1);  //부모노드 제외하고 2개이상이어야 카운트 된다.
}

특징은 간선이 3개 이상인 곳에서 검사하면 모든 정점 검사할 필요없이 끝이긴하다.(왜그런진 모름..)

802 C. Helping the nature

이런 문제 옛날에 어디선가 풀었던 것같은데 라는 생각만 계속하다가 결국 아무것도 못했다.
난 이런 문제가 젤 어렵다 손으로 하면 되긴하는데 컴퓨터로 어케하지 싶은 문제들..
그래서 맨날 C번을 못푸나 보다 ㅠㅠ
중요한건 인접한 것의 크기비교였다. 만약에 a[i] < a[i+1]이면 오른쪽 시작(suffix)으로 빼야한다. 왜냐면 왼쪽시작(prefix)으로 빼면 이미 작은데 더 빼서 손해기 때문이다.
빼는 양의 정도는 a[i+1]-a[i]일 것이다. 크기를 똑같이 만들어 같이 움직여야한다. 그러면서 평평하게 만들어지고, 그렇다면 그 평평할 때 의 높이 curh를 저장해놓고 마지막에 더해주면 된다.
이래도 되는 이유는 인접한거는 세트로 움직이기 때문이다 그러니까 차이가 변하질 않는다.
a배열의 값이 10억이므로 답은 int형을 훌쩍 넘어갈 수 있다. 따라서 long long으로 해줘야한다.

    long long res = 0;
    long long curh = a[0];
    for(int i = 0; i < n-1; i++) {
        res += abs(a[i] - a[i+1]);
        if(a[i] > a[i+1]) {
            curh += a[i+1] - a[i];  //깎일 수도있고 늘어날수도 있으니 이건 절댓값 안붙여
        }
    }
    cout << res+abs(curh)<<'\n';

802 D. River Locks

C에 올인해서 문제도 안읽어 봤다.
읽어보니 일단 왼쪽에서 넣는게 이득이라는 것을 확인됐다.
조금 이해가 안되는건 높은곳에서 낮은쪽으로 가는게 아니라 그냥 왼쪽이 꽉차면 오른쪽으로 간다.

그림을 위와 같이 그려놔서 내가 해석을 제대로 한건가? 헷갈렸다. ㅋㅋㅋ

cin >> n;
vol = vector<ll> (n+1);
mintime = vector<ll> (n+1);
ll sum = 0;
for(int i=1;i<=n;i++){
    cin >> vol[i];
}
mintime[0] =0;   
for(int i=1;i<=n;i++){
    sum += vol[i];
     // i개 썼을 떄 i개 다 채울라면 몇초 걸림? 
     // 앞에께 크면 앞에꺼 만큼 걸리고, 뒤에께 크면 앞에서 좀 흘러나온거 받음
     // 나눗셈연산 생각해서 올림처리 해줌
    mintime[i] = max(mintime[i-1], (sum+i-1)/i);   
}
cin >> q;
while (q--){
    ll query;
    cin >> query;
    ll rst = (sum+query-1)/query;
    if(rst<=n&&mintime[rst]<=query) cout << rst << '\n';
    else cout << -1 << '\n';
}