Educational Codeforces Round 133 (Rated for Div. 2) 1673 → 1751

https://codeforces.com/contest/1716

Dashboard - Educational Codeforces Round 133 (Rated for Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. 2-3 Moves

https://codeforces.com/contest/1716/problem/A

Problem - A - Codeforces

문제

 

1차원 좌표에 n 위치가 주어진다. 현재 위치는 0이고 , 현재 좌표를 x라고 했을 때 1분에 x+2, x-2 ,x+3 ,x-3 으로 이동이 가능하다. n 위치로 갈 수 있는 최소 시간을 출력하는 문제

 

풀이

 

6미만은 따로 처리해주고 3으로 나눈 나머지에 맞게 값을 출력해준다..

 

코드

 

    #include <bits/stdc++.h> 
    using namespace std;
    int ans[10];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        ans[1] = 2;
        ans[2] = 1;
        ans[3] = 1;
        ans[4] = 2;
        ans[5] = 2;
     
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            n = abs(n);
            if (n < 6) {
                cout << ans[n] << '\n';
                continue;
            }
            int mod = n % 3;
            if (mod == 0)cout << n / 3;
            else if (mod == 1) cout << n / 3 + 1;
            else if (mod == 2)cout << n / 3 + 1;
            cout << '\n';
        }
     
    }

 

B. Permutation Chain

https://codeforces.com/contest/1716/problem/B

Problem - B - Codeforces

문제

 

n이 주어진다. n길이의 permutation중에 p[i] = i인 갯수를 fixedness 라고 한다. 하나의 permutation에 두개의 위치를 swap해서 이전보다 작은 fixedness를 만들 수 있으면 chain으로 연결할 수 있다. 최대 chain의 수와 chain에 연결된 permutaiton들을 출력하는 문제

 

풀이

 

양옆에 인접한 숫자를 1개씩 바꿔주면 최대 chain의 수인 n이 나오고 그대로 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h> 
    using namespace std;
    int a[101];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
     
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            for (int i = 1; i <= n; i++)a[i] = i;
            cout << n << '\n';
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++)cout << a[j] << ' ';
                cout << '\n';
                swap(a[n - i], a[n - i + 1]);
            }
            
        }
     
    }

C. Robot in a Hallway

https://codeforces.com/contest/1716/problem/C

Problem - C - Codeforces

문제

 

2*m 의 배열이 주어진다. 각 칸에는 최소 a[i][j]의 시간이 차야 들어갈 수 있다. 최초로 1,1에서 시작하고 한번에 인접한 칸 하나에 이동할 수 있으며 한번 방문한 칸은 다시 방문하지 못한다. 모든 칸을 방문했을 때 최소 시간을 출력하는 문제

 

풀이

 

최초 쭉 오른쪽 -> 아래 -> 쭉 왼쪽 을 제외하고 , 아래 -> 오른쪽 -> 위 -> 오른쪽 -> 아래 식으로 방문했다 쳤을때 각 칸마다 모든 칸을 방문했을때의 계산을 preMAX 배열을 이용하면 O(1)에 바로 구할 수있다. 모든 경우의 수를 계산해주면 된다.

 

코드

    #include <bits/stdc++.h> 
    using namespace std;
    long long a[3][200010];
    long long sum1[3][200010],sum2[3][200010];
    bool check[3][200010];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            long long m;
            cin >> m;
            for (int i = 1; i <= 2; i++) {
                for (int j = 1; j <= m; j++) {
                    cin >> a[i][j];
                    check[i][j] = false;
                    sum1[i][j] = sum2[i][j] = 0;
                }
            }
            sum1[1][m] = a[1][m] + 1;
            sum1[2][m] = a[2][m] + 1;
            long long MAX1 = a[1][m], MAX2 = a[2][m];
            long long idx1 = m, idx2 = m;
            for (int i = m-1; i > 0; i--) {
                long long dif = m - i;
                sum1[1][i] = max(sum1[1][i + 1], a[1][i] + 1 + dif);
                sum1[2][i] = max(sum1[2][i + 1], a[2][i] + 1 + dif);
            }
            sum1[1][1] = max(sum1[1][2], a[1][1] + m - 1);
            sum2[1][m] = a[1][m] + 1;
            sum2[2][m] = a[2][m] + 1;
            for (int i = m - 1; i > 0; i--) {
                sum2[1][i] = max(sum2[1][i + 1]+1, a[1][i] + 1);
                sum2[2][i] = max(sum2[2][i + 1] + 1, a[2][i] + 1);
            }
            //for (int i = 1; i <= 2; i++) {
            //    for (int j = 1; j <= m; j++)cout << sum1[i][j] << ' ';
            //    cout << '\n';
            //}
            //cout << '\n';
            long long ans = max(sum1[1][1] + m, sum2[2][1]);
            check[1][1] = true;
            long long time = 0;
            int x = 2, y = 1;
            while (true) {
                check[x][y] = true;
                time = max(time+1, a[x][y] + 1);
                if (x == 1) {
                    if (check[x + 1][y]) {
                        y++;
                    }
                    else {
                        long long dif = m - y;
                        long long now = max(time + dif, sum1[x][y]);
                        now = max(now + 1, a[2][m] + 1);
                        now = max(now + dif, sum2[2][y]);
                        ans = min(ans, now);
                        x++;
                    }
                }
                else {
                    if (check[x - 1][y]) {
                        y++;
                    }
                    else {
                        long long dif = m - y;
                        long long now = max(time + dif, sum1[x][y]);
                        now = max(now + 1, a[1][m] + 1);
                        now = max(now + dif, sum2[1][y]);
                        ans = min(ans, now);
                        x--;
                    }
                }
                if (y > m)break;
            }
            cout << ans << '\n';
     
        }
     
    }

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.