20/04/12 유사코 2020 2월(USACO 2020 February)

https://www.acmicpc.net/category/detail/2202

USACO 2020 February Contest Bronze

브론즈 문제들 매우 쉬움!

 

실버들은 저번 1월 문제와 달리 난이도가 쭉 상승했었음.. 이분탐색이 개꿀이었는데

 

Swapity Swapity Swap . 18783번

https://www.acmicpc.net/problem/18783

18783번: Swapity Swapity Swap

브론즈에 있는문제의 범위가 커졌다. 같은 풀이를 사용해서 풀었다.

$L_M$

$N (1\le N \le 10^5)$개의 소들을 $M (1\le M \le 100)$번동안 뒤집는다. 

뒤집을 때는 $(L_1, R_1) ... (L_M, R_M)$들을 입력받아(L_i, R_i)를 뒤집는다.   

이렇게 $(L_1, R_1) ... (L_M, R_M)$를 뒤집는 행위를 $K (1\le K \le 10^9)$번 하고난뒤의 결과를 출력하면 된다.

$(L_1, R_1) ... (L_M, R_M)$을 한번 뒤집으면 특정 값들이 사이클을 이루게 된다.

예제의 경우 $[1, 5, 7, 6, 2, 3, 4]$이니 $(1), (2, 5), (3, 7, 4, 6)$이렇게 3개의 사이클이 나온다.

즉 $(L_1, R_1) ... (L_M, R_M)$을 한번 뒤집으면 내 사이클에서 다음 값을 가지게 된다. 내 사이클의 길이만큼 돈다면 나 자신이 나오니 K번 도는 것이 아닌$ K% $(cycle 길이) 를 해준만큼만 돌면된다. 

vector<int> v;
bool che[MAXN];
int arr[MAXN];//정답 보관
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int N,M, K;
    cin >> N >>M>> K;
    
    for (int i = 1; i <= N; i++) {
        v.push_back(i);
    }
    for (int i = 1; i <= M; i++) {//M번 뒤집기
        int c, d;
        cin >> c >> d;
        reverse(v.begin() + c - 1, v.begin() + d);
    }
    for (int i = 1; i <= N; i++) {
        if (che[i] == 0) {//한번 방문한점은 방문한 사이클이기 때문에 패스한다.
            vector<int> tem;//사이클 요소들 넣기 tem의 크기가 사이클의 길이다.
            for (int j = i; che[j] == 0; j = v[j-1]) {
                che[j] = 1;
                tem.push_back(j);
            }
            for (int j = 0; j < tem.size(); j++) {
                int temnum = (K + j) % (int)tem.size();
                arr[tem[j]] = tem[temnum];
            }
        }
    }
    for (int i = 1; i <= N; i++)
        cout << arr[i] << '\n';
}

 

Triangles (Silver) 18784번

https://www.acmicpc.net/problem/18784

18784번: Triangles (Silver)

이 문제도 브론즈에있던 문제가 강화 된것이다. 

$N (3\le N \le 10^5)$개의 점좌표들 $(X_1, Y_1) ... (X_N, Y_N)$ 을 입력 받아 2D map 에 찍은뒤 3개의 점으로 이뤄져 있고 x축과 y축에 평행한 변 2개로 만들어지는 직각삼각형들의 $넓이 \times 2$들의 합을 mod $10^9 + 7$해준 값을 출력하면 된다. 

 

ll ans = 0;
ll arr[MAXN];//각 점을 수직으로 잡을때 만들어지는 높이들
vector<pair<pii,int>> vy, vx;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int y, x;
        cin >> x >> y;
        vy.push_back({ {y,x},i });//y우선 정렬 
        vx.push_back({ {x,y},i });//x우선 정렬
    }
    sort(vy.begin(), vy.end());
    sort(vx.begin(), vx.end());
    for (int i = 0; i < N; i++) {
        ll sum = 0;//높이들의 합
        int iter = i;
        while (iter+1<N && vy[iter].first.first == vy[iter + 1].first.first) {//같은 y인거들 찾음
            sum = (sum + vy[iter + 1].first.second - vy[i].first.second) % MOD;
            iter++;
        }//iter는 마지막 같은 녀석을 가르키고 있음
        for (int j = i; j <= iter; j++) {
            arr[vy[j].second] = sum;
            if (j == iter)break;
            sum = (sum - (iter + i - 2*j -1) * (vy[j + 1].first.second - vy[j].first.second)) % MOD;
        }
        i = iter;
    }
    for (int i = 0; i < N; i++) {
        ll sum = 0;//밑변들의 합
        int iter = i;
        while (iter + 1 < N && vx[iter].first.first == vx[iter + 1].first.first) {//같은 x찾기
            sum = (sum + vx[iter + 1].first.second - vx[i].first.second) % MOD;
            iter++;
        }//iter는 마지막 같은 녀석을 가르키고 있음
        for (int j = i; j <= iter; j++) {
            ans = (ans + arr[vx[j].second] * sum)%MOD;//arr에 저장된 높이와 가로인 sum 곱하기
            if (j == iter)break;
            sum = (sum - (iter + i - 2 * j - 1) * (vx[j + 1].first.second - vx[j].first.second)) % MOD;
        }
        i = iter;
    }
    cout << ans;
}

 

Clock Tree 18785

https://www.acmicpc.net/problem/18785

18785번: Clock Tree

$N(2 \le N \le 2500)$개의 노드를 가진 트리가 주어진다. 각 노드에는 시계가 있는데  $1 ... 12$ 중 정확히 하나를 표시하고있다.  $N-1$개의 간선이 있을텐데 이 간선들을 이용하여 다른 노드로 이동할 수 있다. 다른 노드를 방문하면 시간이 1 증가하게 된다.$ (4\to 5,  11\to 12, 12\to 1)$ 출발 할때는 값이 증가 하지 않는다. 

즉 이동후 도착한 곳의 시간만 1증가 한다. 모든 노드의 시간을 12로 만들고 싶을 때 시작 할 수 있는 노드의 수를 출력 하면 된다. 

N의 범위가 작으므로 각 노드를 돌며 이곳에서 시작했을 때 모든 노드를 12로 만들수 있으면 정답을 1씩 증가시켜주면 될것이다. $O(N^2)$

위 그림과 같이 증가가 일어 날 것이다 . 처음 노드를 방문 할 때 (dfs중 왔을때) 내 값이 한번 증가하고 내 자식 노드가 있다면 내려간다. 자식 노드를 방문하면 자식 노드값을 1증가 시켜주고 12와의 격차만큼 내 노드를 방문했다가 다시 자식노드를 방문해야 12가 되기 때문에 내 노드에 $12 - 자식노드 값$ 만큼 더해 줘야한다. 또한 자식노드가 끝나면 다시 내 노드에 돌아와야 하므로 내 노드에 1을 또 더해준다. 

위 그림의 경우 $20$번 동작할때 시작 노드가 12가 되었지만 1이되어도 상관없다. 값이 1이라는건 $18$과정이 이루어 질때 시작노드의 값이 이미 12였다는 말이므로 과정 $19, 20$을 생략하면 만족 할 수 있기 때문이다. 

nt ans = 0;
int arr[MAXN];
int dfsv[MAXN];
vector<int> adj[MAXN];
 
int dfs(int node, int par) {//내가 자식이 없을때 내꺼의 값을 반환
    dfsv[node]++;//처음 노드 방문할때 
    for (int a : adj[node]) {
        if (a == par)continue;
        dfsv[node] += 12 -dfs(a, node);//12가 되기위해 필요한 만큼 의 갯수를 더함
        dfsv[node] = (dfsv[node] - 1) % 12 + 1;//1~12범위로만 표시
    }
    dfsv[par]++;//내꺼 끝나면 부모노드로 돌아가야함
    return dfsv[node];//내꺼 부모노드한테 반환
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i < N; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dfsv[j] = arr[j];
        }
        dfsv[i]--;
        dfs(i, -1);
        if (dfsv[i] == 1 || dfsv[i] == 12)//1이더라도 마지막에 시작노드로 돌아가는 과정을 빼면 12로 끝낼수 
            ans++;
    }
    cout << ans;
}

 

확실히 유사코 문제가 알고리즘은 간단한데 생각을 해야 풀 수 있고 코드고 깔끔하게 나오고 좋은거 같다.