Codeforces #763

A. Robot Cleaner

Problem - A - Codeforces

Problem - A - Codeforces

\(n \times m\) 사이즈의 보드판이 주어진다.

로봇의 좌표는 \((r_b, c_b)\), 목표칸의 좌표는 \((r_d, c_d)\)이다.

 

로봇은 1초마다 \((dr, dc)\)만큼 움직인다.

즉, \((r, c) \rightarrow (r+dr, c+dc)\)

 

초기 \(dr=1, dc=1\)이다.

수직벽에 닿으면 \(dc \rightarrow -dc\), 수평벽에 닿으면 \(dr \rightarrow -dr\)로 값이 변한다.

 

로봇은 다음 칸으로 이동하기 전에 현재 행과 열을 청소한다.

목표칸을 청소하기까지 몇 초가 걸리는지 구하는 문제이다.

 

가로 방향과 세로 방향을 분리해서 생각하면 편하다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n, m, rb, cb, rd, cd;
        cin >> n >> m >> rb >> cb >> rd >> cd;
        int ans = INT_MAX;
        if (rb <= rd) ans = min(ans, rd - rb);
        else ans = min(ans, 2*n - rd - rb);
        if (cb <= cd) ans = min(ans, cd - cb);
        else ans = min(ans, 2*m - cd - cb);  
        cout << ans << '\n';
    }
    return 0;
}

 

 

B. Game on Ranges

Problem - B - Codeforces

Problem - B - Codeforces

초기 set에는 \([1, n]\)만 들어있다.

이후 set에 남아있는 원소가 없을 때까지 다음 행위를 반복한다.

1. set에서 어떤 원소 \([l, r]\)을 선택하여 제거한다.

2. \([l, d-1]\), \([d+1, r]\)을 (존재하면) 넣는다. \((l \le d \le r)\)

 

set에 포함되었던 구간들이 모두 주어질 때, 해당 구간에서 어떤 \(d\)를 선택했는지 찾는 문제이다.

 

구간 \([l, r]\)을 \([l, -r]\)로 변형하여 vector \(v\)에 넣고 정렬한다.

\(v_i\)와 \(v_{i+1}\)의 비교를 통해 \(v_i\)에서 어떤 \(d\)를 선택했는지 알 수 있다.

1) \(l_{v_i} = l_{v_{i+1}} \Rightarrow d_{v_i} = r_{v_{i+1}} + 1\)

2) \(r_{v_i} = r_{v_{i+1}} \Rightarrow d_{v_i} = l_{v_{i+1}} - 1\)

3) \(l_{v_{i+1}} = r_{v_{i+1}} \Rightarrow d_{v_{i+1}} = l_{v_{i+1}}\)

4) 위 경우에 해당하지 않는 \(i\)는 건너뛴다.

 

그림으로 그려보면 쉽게 이해할 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<pii> v(n);
        for (int i = 0; i < n; i++) {
            int l, r;
            cin >> l >> r;
            v[i] = {l, -r};
        }
        sort(v.begin(), v.end());
        
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (i && v[i-1].first == v[i].first) {
                ans.push_back(-v[i].second + 1);
            }
            if (i && v[i-1].second == v[i].second) {
                ans.push_back(v[i].first - 1);
            }
            if (v[i].first == -v[i].second) {
                ans.push_back(v[i].first);
            }
        }
        for (int i = 0; i < n; i++) {
            cout << v[i].first << ' ' << -v[i].second << ' ' << ans[i] << '\n';
        }
    }
    return 0;
}

 

 

C. Balanced Stone Heaps

Problem - C - Codeforces

Problem - C - Codeforces

\(n\)개의 더미가 주어지고, \(i\)번째 더미에는 \(h_i\)개의 돌이 들어있다.

 

3번째 더미부터 \(n\)번째 더미 순서로

1. \(d (0 \le 3 \cdot d \le h_i)\)를 선택한다.

2. \(i\)번째 더미에서 \(i-1\)번째 더미로 \(d\)개의 돌을 옮긴다.

3. \(i\)번째 더미에서 \(i-2\)번째 더미로 \(2 \cdot d\)개의 돌을 옮긴다.

 

모든 과정이 끝난 후, 더미에 들어있는 돌의 최솟값의 최댓값을 구하는 문제이다.

 

파라메트릭 서치로 답을 찾을 수 있다.

판단 함수를 만들 때 주의할 점은 어떤 일이 실제로 일어나는 순서와 답을 구하는 순서가 다르다는 것이다.

돌을 옮기는 것은 3번째 더미부터지만, 돌을 얼마나 옮길지는 \(n\)번째 더미부터 결정한다.

 

\(i\)번째 더미가 다른 돌 더미들로부터 받을 수 있는 돌의 최대 개수를 \(a_i\)라고 하자.

초기에는 모든 \(i)에 대하여 \(a_i = 0\)이다.

 

\(n\)번째 더미부터 시작하여 다음 행동을 반복한다.

1. \(h_i + a_i - x < 0\)이면 \(x\)가 불가능한 값임을 알 수 있다.

2. \(d_i = \max(\lfloor \frac{h_i}{3} \rfloor , \lfloor \frac{h_i + a_i - x}{3} \rfloor)\)

3. \(a_{i-1} = a_{i-1} + d_i, \text{    } a_{i-2} = a_{i-2} + 2 \cdot d_i \)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int n;
vector<ll> h;
 
bool ok(int x) {
    vector<ll> a(n);
    for (int i = n-1; i >= 2; i--) {
        if (h[i] + a[i] - x < 0) return false;
        ll d = min(h[i]/3, (h[i] + a[i] - x)/3);
        a[i-1] += d;
        a[i-2] += 2*d;
    }
    return (h[0] + a[0] >= x) && (h[1] + a[1] >= x);
}
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        cin >> n;
        h.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }
        int lo = 0, hi = 1e9+1;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (ok(mid)) lo = mid;
            else hi = mid;
        }
        cout << hi - 1 << '\n';
    }
    return 0;
}