PS Diary #5

 

 

 

 

 

 

 

 

CodeForces Round 364 $($Div. 1$)$. Connecting Universities

dfs, dp

 구현은 아주 간단하나 아이디어가 좀 필요했던 문제이다. $N\leq 2\times 10^5$ 이라서 적어도 $O(N\log{}{N})$이하의 풀이가 필요하다.  두 점 사이에 거리를 구하는데만 해도 dfs로 $O(N)$이나 걸리는데 최대 $\frac{N}{2}$ 쌍에 대해서 거리를 구하려고 하면 $O(N^2)$이기에 다른 방법이 필요했다. 그래서 더블카운팅 형식으로 세주려고 했다. 모든 간선들에 대해서 그 간선이 쓰일 수 있는 최대 횟수를 더해주면 그게 정답이 된다. 그 어떤 간선 $E = \left\{V,U\right\}$ 쓰일 수 있는 최대 횟수는 $V$방향 서브트리에 존재하는 대학의 개수와 $U$방향 서브트리에 존재하는 대학의 개수 중 최솟값이다. 이를 효율적으로 계산하기 위해 어떤 정점을 root node로 하는 tree를 구성하면 된다. 여기서 $dp[S] := (S$의 서브트리에 존재하는 대학 개수$)$로 정의하면 $dp[S] = \left[\sum_{V\in child(S)}^{}dp[V]\right] + isUniversity(S)$ 가 되고 구하는 정답은 $\sum_{V\in V(G)}^{}\min{\left\{dp[V], 2k -dp[V]\right\}}$가 된다. 이는 $O(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 = 2e5;
 
ll n,k,dp[nmax + 10];
bool isUniversity[nmax + 10],visited[nmax + 10];
vector<int> tmpGraph[nmax + 10], graph[nmax + 10];
 
ll dfs(int S){
    visited[S] = true;
    if(isUniversity[S]) dp[S] = 1;
 
    for(int i=0;i<tmpGraph[S].size();i++){
        int U = tmpGraph[S][i];
        if(visited[U]) continue;
        visited[U] = true;
        graph[S].push_back(U);
        dp[S] += dfs(U);
    }
    return dp[S];
}
 
void solve(){
    ll ans = 0;
    for(int u=1;u<=n;u++) ans += min(dp[u],2*k-dp[u]);
    cout << ans;
}
 
int main(){
    fastio;
    cin >> n >> k;
    for(int i=0;i<2*k;i++){
        int u; cin >> u;
        isUniversity[u] = true;
    }
    for(int i=0;i<n-1;i++){
        int u, v; cin >> u >> v;
        tmpGraph[u].push_back(v);
        tmpGraph[v].push_back(u);
    }
    dfs(1);
    solve();
}

 

 

CodeForces Round 80. Minimax Problem

binary search, bit masks 

한 30분 정도 고민했던 거 같다. $m \leq 8$이라서 bit masks를 쓸 수 있겠다는 것은 알았는데 어떻게 써야할지를 오래 고민했다. 어떤 배열 $a_k$에 대해 가능한 $b_k$에 최소 원소로 가능한 최대값이 무엇인지를 log시간에 계산할 수 있으면 모든 배열에 대해 계산하면서 최대일 때가 언제인지를 확인하는 풀이가 가능하다. 배열 $a_k$에 대해 $b_k$의 최소 원소로 어떤 정수 $c$가 가능하다는 것은 $a_k$의 원소 중 $a_k[i] < c$를 만족하는 모든 $i$들에 대해 $a_l[i] >= c$이도록 하는 배열 $a_l$이 존재한다는 것이다. 따라서 각 인덱스$($0부터 7$)$의 포함 여부를 bit mask로 저장하면 효율적으로 처리할 수있다. 또한 각 배열에 대해 최대값을 찾는 것은 이분탐색을 이용할 수 있다. 결과적으로 시간복잡도는 $O(2^m \times N\log{}{N})$ 이 된다.

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

int n,m;
int arr[nmax + 10][8];
int minValues[1 << 8];

int BinarySearch(int v){
    int l = 0, r = 1e9, rtv;
    while(l <= r){
        int mid = (l+r)/2;
        int mask  = 0;
        for(int i = 0; i < m; i++){
            if(arr[v][i] < mid) mask = mask | (1 << i);
        }
        if(mask == 0) {
            rtv = mid;
            l = mid + 1;
        } else {
            if(minValues[mask] < mid) r = mid - 1;
            else {
                rtv = mid;
                l = mid + 1;
            }
        }
    }
    
    return rtv;
}

void solve(){
    for(int mask = 1; mask < (1 << m); mask++){
        int mx = 0;
        for(int i = 0; i < n; i++){
            int mn = 2e9;
            for(int j=0;j<m;j++){
                if(!(mask & (1 << j))) continue;
                mn = min(mn, arr[i][j]);
            }
            mx = max(mx, mn);
        }
        minValues[mask] = mx;
    }
    
    int mx = -1; int mxIdx;
    for(int i = 0; i < n; i++){
        int minmax = BinarySearch(i);
        if(minmax <= mx) continue;
        mx = minmax;
        mxIdx = i;
    }
    cout << mxIdx + 1 << " ";
    
    int mask = 0;
    for(int i = 0; i < m; i++)
        if(arr[mxIdx][i] < mx)
            mask = mask | (1 << i);
    for(int i = 0; i < n; i++){
        bool flag = true;
        for(int j = 0; j < m; j++){
            if(!(mask & (1 << j))) continue;
            if(arr[i][j] < mx) {
                flag = false; break;
            }
        }
        if(flag){
            cout << i + 1;
            return;
        }
    }
    cout << mxIdx + 1;
}

int main(){
    fastio;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> arr[i][j];
    
    solve();
}

 

 

BOJ 3015. 오아시스 재결합

stack

 그냥 stack만 이용하는 문제였다. 키가 같은 사람들이 있을 때 처리하는게 조금 까다로웠다. stack에 현재 키와 자신보다 키가 큰 사람이 나기 전까지 자신과 키가 동일했던 사람이 몇 명인지를 저장해놓고 논리에 따라 처리해주면 되는 문제였다. 시간복잡도는 $O(N)$이다.

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

int N, height[NMAX + 10];

void solve(){
    ll ans = 0;
    stack<pll> st;
    for(int i=0;i<N;i++){
        ll sameHeightNum = 0;
        while(!st.empty() && st.top().first < height[i]){
            ans += st.top().second + 1;
            st.pop();
        }
        if(!st.empty()){
            if(st.top().first == height[i]){
                ans += st.top().second + 1;
                sameHeightNum = st.top().second + 1;
                st.pop();
                if(!st.empty()) ans ++;
            } else {
                ans ++;
            }
        }
        st.push({height[i], sameHeightNum});
    }
    
    cout << ans;
}

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

 

 

AtCoder. Fennec vs Snuke

dfs, game theory

전략이 빨리 보여서 게임이론 관련된 문제 중에서 어렵지 않은 편에 속하는 것 같다. 다른 사람이 최대한 많이 먹지 못하게 하려면 먼저 미리 상대의 경로를 차단해야한다.

 트리 상에서 상대의 시작점과 자신의 시작점을 잇는 최단경로 상에서 최대한 갈 수 있는 만큼 전개를 해놓으면 나머지 자식 칸들은 이후에 모두 자신이 칠할 수 있으므로 영역 전개가 중요하다. 이를 이용하면 $O(N)$만에 구현할 수 있다. 아이디어는 빨리 생각했지만 구현하는데 시간이 좀 걸렸다 ._. ,,

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

int N, BlackNum = 0, WhiteNum = 0, pathCnt = 1;
vector<int> graph[NMAX + 10];
bool isInPath[NMAX + 10];

bool FindPath(int cur, int bef){
  if(cur == N) return true;
  int rtv = false;
  for(int i=0;i<graph[cur].size();i++){
    int v = graph[cur][i];
    if(v == bef) continue;
    rtv = rtv | FindPath(v, cur);
  }
  if(rtv) {
    isInPath[cur] = true; 
    pathCnt ++;
  }
  return rtv;
}

int childNum(int cur, int bef){
  int rtv = 1;
  for(int i=0;i<graph[cur].size();i++){
    int nx = graph[cur][i];
    if(nx == bef) continue;
    rtv += childNum(nx, cur);
  }
  return rtv;
}

void solve(){
  int FennecCnt = 0, cur = 1, bef = -1, nxt;
  while(FennecCnt < (pathCnt + 1)/2){
    FennecCnt ++; BlackNum ++;
    for(int i=0;i<graph[cur].size();i++){
      int v = graph[cur][i];
      if(isInPath[v] && v != bef) nxt = v;
      if(isInPath[v]) continue;
      BlackNum += childNum(v, cur);
    }
    bef = cur; cur = nxt;
  }
  int SnukeCnt = 0;
  cur = N, bef = -1;
  while(SnukeCnt < (pathCnt)/2){
    SnukeCnt ++; WhiteNum ++;
    for(int i=0;i<graph[cur].size();i++){
      int v = graph[cur][i];
      if(isInPath[v] && v != bef) nxt = v;
      if(isInPath[v]) continue;
      WhiteNum += childNum(v, cur);
    }
    bef = cur; cur = nxt;
  }
  if(WhiteNum >= BlackNum) cout << "Snuke";
  else cout << "Fennec";
}

int main(){
  fastio;
  cin >> N;
  for(int i=0;i<N-1;i++){
    int v, u; cin >> v >> u;
    graph[v].push_back(u);
    graph[u].push_back(v);
  }
  isInPath[N] = true;
  FindPath(1, -1);
  solve();
}