PS Diary #7

CodeForces Raif Round 1. Carrots for Rabbits

priority queue, math, greedy

 priority queue를 사용하는 문제 치고는 좀 까다로운 문제였다. 처음 이 문제를 접근할 때에는 당근을 잘랐을 때 자른 당근의 길이채로 배열에 저장하려고 했었는데 그냥 2개로만 나눠지는 게 아니라 $n$ 개로 나눠질 수도 있기 때문에 나중 상황을 고려하지 못하게 된다. 그래서 그냥 당근은 그 길이대로 저장해되 그 당근을 현재까지 몇 개로 나눴는지를 저장하기로 하였다. 그래서 총 나눈 개수가 K개가 될 때 종료해주면 된다. 그럼 어떤 당근을 잘라야할지를 정해야한다. 그 기준을 '현재 상태에서 1번 더 나누었을 떄 시간이 얼마나 더 줄어드는가'로 하였다. 나눠지는 횟수가 많을 수록 줄어드는 시간이 점점 더 줄어드므로 매순간 줄어들 수 있는 시간이 가장 큰 당근을 선택하는 관찰이 잘 성립한다.  시간복잡도는 $O(N\log{}{N})$이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
const int NMAX = 1e5;

ll potential(int s, int n){
    ll lower = s / n;
    ll reminder = s % n;
    ll T = lower * lower * (n - reminder) + (lower + 1) * (lower + 1) * reminder;
    return T;
}

struct carrot{
    ll size, divNum;
    bool operator<(const carrot &c) const{
        ll delta1 = potential(size,divNum) - potential(size,divNum+1);
        ll delta2 = potential(c.size,c.divNum) - potential(c.size, c.divNum+1);
        return delta1 < delta2;
    }
};

ll N, K;
ll a[NMAX + 10];

void solve(){
    priority_queue<carrot> pq;
    for(int i=0;i<N;i++){
        pq.push({a[i],1});
    }
    
    int cnt = N;
    while(cnt != K){
        carrot x = pq.top(); pq.pop();
        x.divNum ++;
        pq.push(x);
        cnt ++;
    }
    
    ll ans = 0;
    while(!pq.empty()){
        carrot c = pq.top(); pq.pop();
        ll lower = c.size / c.divNum;
        ll reminder = c.size % c.divNum;
        ll T = lower * lower * (c.divNum - reminder) + (lower+1) * (lower+1) * reminder;
        ans += T;
    }
    cout << ans << '\n';
}

int main(){
    fastio;
    cin >> N >> K;
    for(int i=0;i<N;i++) cin >> a[i];
    solve();
}

 

 

USACO US Open Contest 2020.  Favorite Colors

 union-find

usaco gold 기출들을 풀어보다가 재미있어 보여서 시도해봤다. 문제를 보자마자 union-find를 써야겠다는 생각을 했다. 같은 색을 갖는 정점들끼리 같은 집합으로 묶어야한다. 만약 정점 $v$ 가 색깔 $c$를 가진 $u$를 admire하는데 색깔 $x$ 를 가진 어떤 정점이 색깔 $c$ 를 가진 어떤 정점을 admire하는 정점 쌍이 존재한다면 $v$ 의 색깔은 $x$로 결정된다. 여기서는 색깔 $x$ 그룹이 색깔 $c$ 그룹을 admire한다고 생각할 수 있다. 만약 이터레이션을 하다가 색깔 $y$ 그룹에 속한 어떤 정점이 그룹 $c$ 에 속한 어떤 정점을 admire한다는 것이 밝혀진다면 그룹 $x$, $y$는 한 그룹이였다는 것이므로 union 해주면 된다. 이 말은 어떤 그룹이 admire 당하는 그룹은 유일하다는 말을 내포한다. 그래서 $ad[i] := ($ 그룹 $i$ 를 admire하는 그룹$)$ 과 같이 정의해주고 중복이 발생할 때마다 union 해주면 최종적인 최대 색깔 집합들을 얻을 수가 있다. 처음은 당연히 그룹이 $N$ 개로 모두 분리된 상태이다. 시간복잡도는 $O(M\log{}{N})$ 이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
const int NMAX = 2e5;

int N,M;
vector<int> graph[NMAX + 10];
int ad[NMAX + 10], parent[NMAX + 10], rk[NMAX + 10];

int getParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int x, int y){
    x = getParent(x); y = getParent(y);
    if(x == y) return;
    if(rk[x] > rk[y]){
        parent[y] = x;
        if(ad[x] == 0) ad[x] = ad[y];
        else if(ad[x] != 0 && ad[y] != 0){
            unionParent(ad[x],ad[y]);
            ad[x] = getParent(ad[x]);
        }
    } else {
        parent[x] = y;
        if(ad[y] == 0) ad[y] = ad[x];
        else if(ad[x] != 0 && ad[y] != 0){
            unionParent(ad[x],ad[y]);
            ad[y] = getParent(ad[y]);
        }
        if(rk[x] == rk[y]) rk[y] ++;
    }
}

void solve(){
    for(int i=1;i<=N;i++) parent[i] = i;
    for(int i=1;i<=N;i++){
        int p =getParent(i);
        for(int j=0;j<graph[i].size();j++){
            if(ad[p] == 0) ad[p] = getParent(graph[i][j]);
            else {
                unionParent(ad[p], getParent(graph[i][j]));
                ad[p] = getParent(ad[p]);
            }
        }
    }
    
    vector<int> color(N+1,0);
    int cnt = 1;
    for(int i=1;i<=N;i++){
        int p = getParent(i);
        if(color[p] != 0) cout << color[p] << "\n";
        else {
            cout << cnt << "\n";
            color[p] = cnt;
            cnt ++;
        }
    }
}

int main(){
    fastio;
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
    }
    solve();
}

 

 

IOI 2009. Mecho

binary search, bfs

 일단 첫 번째로 해야하는 관찰은 '$k$ 분 동안 기다리고 탈출하는 것이 가능하다면 $k-1$분 동안 기다리고 탈출하는 것도 가능하다.' 이다.  그럼 기다리는 시간에 대한 이분탐색을 생각해볼 수 있고 $k$ 분 기다렸을 때 탈출이 가능한지를 $O(N^2)$ 정도로만 판단할 수 있어도 충분한다.  먼저 주어진 맵에서 각각의 격자점들까지 벌들이 몇 분만에 도달할 수 있는지를 bfs를 통해 구해놓을 수 있다.  이를 미리 알고 있으면 가능한지를 판단할 때 곰의 초기 위치에서 출발해서 bfs를 편하게 할 수 있다. 곰의 초기 위치로부터 거리가 $n\times S + r$ 꼴일 때는 시간이 $k + n$ 분 지난 것이므로 벌이 이 시간보다 더 빨리 도착할 수 있다면 갈 수 없는 칸이고 아니라면 갈 수 있는 칸이다. 이를 토대로 bfs했을 때 집까지 도착할 수 있다면 $k$ 분에서 가능한 것이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> coord;
const int NMAX = 8e2, INF = 1e9;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

int N,S;
int forest[NMAX + 10][NMAX + 10];
int dist[NMAX + 10][NMAX + 10];
coord bear, home;
vector<coord> bees;

void bfs(coord c){
    queue<coord> q;
    q.push(c);
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(forest[nx][ny] || dist[nx][ny] <= dist[x][y] + 1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx,ny});
        }
    }
    return;
}

bool isPossible(int t){
    int Sx = bear.first, Sy = bear.second;
    if(dist[Sx][Sy] <= t) return false;
    vector<vector<int>> dist2(N, vector<int>(N, INF));
    queue<coord> q; q.push(bear);
    dist2[Sx][Sy] = 0;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(forest[nx][ny] == -1 || dist2[nx][ny] <= dist2[x][y] + 1) continue;
            if(dist[nx][ny] <= t + ((dist2[x][y]+1)/S)) continue;
            dist2[nx][ny] = dist2[x][y] + 1;
            q.push({nx,ny});
        }
    }
    
    return (dist2[home.first][home.second] != INF);
}

void solve(){
    for(coord c : bees) bfs(c);
    if(!isPossible(0)) cout << -1;
    else {
        int l = 0, r = N*N, ans = 0;
        while(l <= r){
            int mid = (l+r)/2;
            if(isPossible(mid)){
                ans = max(ans, mid);
                l = mid + 1;
            } else r = mid - 1;
        }
        cout << ans;
    }
}

int main(){
    fastio;
    cin >> N >> S;
    for(int i=0;i<N;i++){
        string s; cin >> s;
        for(int j=0;j<N;j++){
            dist[i][j] = INF;
            if(s[j] == 'T') forest[i][j] = -1;
            else if(s[j] == 'M') bear = {i,j};
            else if(s[j] == 'D') {
                home = {i,j};
                forest[i][j] = 1;
            } else if(s[j] == 'H') {
                bees.push_back({i,j});
                forest[i][j] = -1;
                dist[i][j] = 0;
            } 
        }
    }
    solve();
}

 

 

BOI 2013. Tracks in the Snow

0-1 bfs

 딱 0-1 bfs 연습하기 좋은 문제이다. 아이디어랑 증명이 필요하긴 하지만 크게 어렵지 않았다.  같은 문자 사이에서는 가중치 0, 다른 문자 사이에서는 가중치 1인 간선이 있다고 생각할 수 있다. 시작점부터 시작해서 0-1 bfs를 통해서 거리를 구해주었을 때 최대 거리가 문제에서 구하는 정답이다. $((0,0)$ 은 거리 1로 초기화$)$ 증명은 간단하게 해볼 수 있다. 최대 거리가 $k$까지 나왔다고 할 때 $k$개의 동물들의 실례가 존재한다는 것과, 동물의 최소 개수 $m$이 $k$보단 작을 수 없다는 것을 증명하면 된다.

 

lemma) 모든 $k$ 이하 자연수 $d$에 대해서 $(0,0)$ 으로부터 거리가 $d$ 초과인 영역을 지나지 않으면서 거리 $d$ 이하인 모든 영역을 지날 수 있다.

p.f) 그렇지 않다고 가정하자. 즉 (0,0)을 포함하지 않으면서 영역에 속한 모든 점들의 거리가 모두 $d$ 이하이고 $(0,0)$ 으로부터 도달할 수 없는 영역이 존재한다는 것이다. 이 중 최대 넓이를 갖는 영역을 생각해보면 이 영역과 인접한 칸들은 모두 거리가 $d$ 초과이거나 갈 수 없는 칸이어야한다.  바깥 영역$($경계$)$이 내부 영역보다 거리가 크므로 0-1 bfs를 할 때 거리는 내부에서 외부 방향으로 업데이트 되었어야한다. 이 영역은 $(0,0)$을 포함하지 않는데 bfs 시에 외부에서 유입이 없으므로 모순이다.

 

 proposition 1) $m \leq k$ 

 실례는 거리가 $d$로 구해진 영역은 $k-d+1$ 번째 온 동물이 남긴 발자국에 의한 것이라고 생각하면 된다. 더 자세히 말하면 $k-d+1$ 번째 동물의 발자국 자취는 거리가 $d$보다 작거나 같은 모든 영역이라고 하면 실례가 된다.  lemma에 의해 이렇게 실례를 잡아도 조건을 잘 만족 시킴을 알 수 있다.

 

proposition 2) $m \geq k$

  한 동물이 거리가 서로 다른 두 영역을 모두 칠했을 때 적어도 하나는 다른 동물에 의해 가려진다는 것을 보일 것이다. 다고 가정하자. 어떤 동물이 거리 $d_1$, $d_2$인 영역을 칠했고 최종 상태에서 다른 동물에 의하여 가려지지 않았다고 가정하자.  여기서 동물의 종류는 하나이므로 당연히 $d_1, d_2$의 기우성은 같다. 일반성을 잃지 않고 $d_1 < d_2$ 라고 하면 기우성이 같으므로 $d_1 < d < d_2$ 이고 $d_1,d_2$ 와 기우성이 다른 $d$ 가 반드시 존재한다. 최종상태에서 $d_1, d_2$ 영역 모두 가려지지 않았어야하므로 다른 동물이 $d$ 영역을 채울 때 거리 $d_1,d_2$인 영역을 모두 지나면 안된다. $d_1 < d$라는 사실을 상기해보면 거리 1에서부터 $d$로 갈 때 $d_1$인 영역을 적어도 한 번은 지나야하므로 모순이다. 즉 다른 동물이 나중에 이 칸들을 메꿔줘야하므로 한 동물만으로는 안된다.

 

따라서 $m = k$임이 증명되는데 굳이 이렇게 증명을 안해도 직관적으로 당연하다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
const int NMAX = 4e3;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
typedef pair<int,int> pii;

int H,W, dist[NMAX + 10][NMAX + 10];
char meadow[NMAX + 10][NMAX + 10];

void solve(){
    deque<pii> q;
    q.push_back({0,0}); dist[0][0] = 0;
    while(!q.empty()){
        int x = q.back().first, y = q.back().second;
        q.pop_back();
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
            if(meadow[nx][ny] == '.') continue;
            int w = (meadow[x][y] == meadow[nx][ny]) ? 0 : 1;
            if(dist[nx][ny] <= dist[x][y] + w) continue;
            dist[nx][ny] = dist[x][y] + w;
            if(w == 0) q.push_back({nx,ny});
            else q.push_front({nx,ny});
        }
    }
    
    int ans = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(meadow[i][j] == '.') continue;
            ans = max(ans, dist[i][j] + 1);
        }
    }
    cout << ans;
}

int main(){
    fastio;
    cin >> H >> W;
    for(int i=0;i<H;i++){
        string s; cin >> s;
        for(int j=0;j<W;j++){
            meadow[i][j] = s[j];
            dist[i][j] = 1e9;
        }
    }
    solve();
}

 

 

KOI 2003. 경찰차

dp

cow checklist 문제를 풀고 난이도 기여를 봤더니 사람들이 경찰차 문제랑 비슷하다길래 궁금해서 이 문제를 풀어보게 되었다. 당연히 dp 문제겠다고 생각하고 dp table을 $dp[i][j]:= ($ 경찰차 1이 $i$번 사건까지 처리, 경찰차 2가 $j$번 사건까지 처리했을 때 최소 비용$)$ 와 같이 정의하자. 전체 최소 비용은 $i$ 또는 $j$가 $W$인 것중의 최솟값이 된다. 먼저 $i > j+1$과 같은 경우에서는 이전 상황에서의 최소 비용이 $dp[i-1][j]$ 였어야하므로 쉽게 처리할 수 있다. 마찬가지로 $j > i +1$과 같은 경우에서는 $dp[i][j-1]$이 이전 상황의 최소 비용이다. $i = j + 1$ 의 경우는 이전 상황이 여러 가지가 있는데 $dp[i][j] = \min_{k<i}(dp[k][j] + dist(i,k))$ 와 같이 나타난다. 여기서 $dist(i,k)$는 사건 $i$ 와 사건 $k$ 까지의 유클리드 거리이다. 이건 $O(W)$라서 시간복잡도가 $O(W^3)$이라고 생각할 수도 있지만 $i = j+1$ 또는 $j =i+1$ 인 경우는 $W$ 개 정도이므로 해봤자 $O(W^2)$ 이다. 나머지는 역추적으로 구해주면 된다. 시간복잡도는 $O(W^2)$이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> accid;
const int NMAX = 1e3;

int N, W;
ll dp[NMAX + 10][NMAX + 10];
pair<int,int> bef[NMAX + 10][NMAX + 10];
accid accidents[NMAX + 10];

ll dist(int idx1, int idx2){
    int x = abs(accidents[idx1].f - accidents[idx2].f);
    int y = abs(accidents[idx1].s - accidents[idx2].s);
    return x + y;
}

void solve(){
    for(int i=1;i<=W;i++) {
        dp[i][0] = dp[i-1][0] + dist(i,i-1);
        bef[i][0] = {i-1,0};
    }
    for(int i=1;i<=W;i++) {
        dp[0][i] = dp[0][i-1] + dist(i,(i-1+W)%(W+1) + 1);
        bef[0][i] = {0,i-1};
    }
    for(int i=1;i<=W;i++){
        for(int j=1;j<=W;j++){
            if(i == j) continue;
            if(i == j+1){
                ll mn = 1e18; pair<int,int> b;
                for(int k=0;k<j;k++){
                    b = (mn > dp[k][j] + dist(k,i)) ? make_pair(k,j) : b;
                    mn = min(mn, dp[k][j] + dist(k,i));
                }
                dp[i][j] = mn; bef[i][j] = b;
            } else if(j == i+1){
                ll mn = 1e18; pair<int,int> b;
                for(int k=0;k<i;k++){
                    b = (mn > dp[i][k] + dist((k+W)%(W+1) + 1,j)) ? make_pair(i,k) : b;
                    mn = min(mn, dp[i][k] + dist((k+W)%(W+1) + 1,j));
                }
                dp[i][j] = mn; bef[i][j] = b;
            } else {
                dp[i][j] = (i > j)?(dp[i-1][j] + dist(i,i-1)):(dp[i][j-1] + dist(j,(j-1+W)%(W+1) + 1));
                bef[i][j] = (i > j)?make_pair(i-1,j):make_pair(i,j-1);
            }
        }
    }
    
    ll ans = 1e18; pair<int,int> p;
    for(int i=0;i<W;i++){
        p = (ans > dp[i][W]) ? make_pair(i,W) : p;
        ans = min(ans, dp[i][W]);
        p = (ans > dp[W][i]) ? make_pair(W,i) : p;
        ans = min(ans, dp[W][i]);
    }
    cout << ans << "\n";
    
    vector<int> who(W + 1); int cnt = W;
    while(p.f != 0 || p.s != 0){
        pair<int,int> b = bef[p.f][p.s];
        if(p.f != b.f) who[cnt] = 1;
        else who[cnt] = 2;
        cnt --;
        p = b;
    }
    for(int i=1;i<=W;i++) {
        cout << who[i] << '\n';
    }
}

int main(){
    fastio;
    cin >> N >> W;
    accidents[0] = {1,1}; accidents[W+1] = {N,N};
    for(int i=1;i<=W;i++){
        cin >> accidents[i].f >> accidents[i].s;
    }
    solve();
}