Codeforces Round 702 (Div.3)

A. Dense Array

$a_i$와 $a_{i+1}$이 $2a_i ≤ a_{i+1}$ (or $2a_{i+1} ≤ a_i$)의 식을 만족하지 않으면 두 수 사이에 조건을 만족하는 숫자를 집어넣는 문제

$a_i$에서 시작하여 2씩 곱해가면서 $a_{i+1}$보다 같거나 작을 때까지 반복하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
#define ll long long
using namespace std;

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=0;
  for(int i=0;i<n-1;i++) {
    int m=min(a[i],a[i+1]), M=max(a[i],a[i+1]);
    while(m*2<M) {
      ans++;
      m*=2;	
    }	
  }
  cout<<ans<<endl;
  return;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

B. Balanced Remainders

$a$배열에서 3으로 나눈 나머지인 0, 1, 2의 숫자가 같을 때까지 $a$배열의 원소를 +1 연산의 최소 수를 구하는 문제

$c_i$가 모두 같게 하기 위해서는 $c_i=\frac{n}{3}$을 만족해야 한다. 그래서 $c_i>\frac{n}{3}$인 $i$를 가장 먼저 찾는다.

$a$배열에서 $i$번째 원소를 +1 증가하는 것은 $c_i$의 개수는 -1, $c_{i+1}$의 개수는 +1인 것을 의미한다.

그래서 위의 과정을 반복하여 횟수를 세어준다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
#define ll long long
using namespace std;

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  
  int res=0;
  vector<int> cnt(3);
  for(int i=0;i<n;i++) {
    for(int j=0;j<=2;j++) {
      if(a[i]%3==j) cnt[j]++;
    }
  }

  while(*min_element(cnt.begin(),cnt.end())!=n/3) {
    for(int i=0;i<3;i++) {
      if(cnt[i]>n/3) {
        res++
        cnt[i]--;
        cnt[(i+1)%3]++;
      }
    }
  }

  cout<<res<<endl;
  return;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

C. Sum of Cubes

어떠한 수 $x$에 대해 $a^3+b^3=x$를 만족하는 $a$,$b$가 존재하는 지 찾는 문제

$a$,$b$가 양수이기 때문에 $a^3$, $b^3$또한 양수이다. 그러므로 $a^3 ≤ a^3+b^3 ≤ x$ 를 만족하기 때문에 $a$는 1부터 $\sqrt[3]{x}$까지만 탐색하면 된다.

따라서 $a$의 범위는 $1 ≤ a ≤ 10^4$이다.

각 $a$에 따라 $b$는 $b=\sqrt[3]{x-a^3}$을 만족하는데 $b$가 정수인지 확인하면 된다.

#include <iostream>
#include <unordered_set>
#define endl '\n';
#define ll long long
using namespace std;

const ll N = 1000000000000L;
unordered_set<ll> cubes;

void precalc() {
  for(ll i=1;i*i*i<=N;i++) {
    cubes.insert(i*i*i);
  }
}

void solve() {
  ll x;
  cin>>x;
  for(ll i=1;i*i*i<=x;i++) {
    if(cubes.count(x-i*i*i)) {
      cout<<"YES"<<endl;
      return;
    }
  }
  cout<<"NO"<<endl;
  return;
}

int main() {
  precalc();
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

D. Permutation Transformation

재귀적으로 트리를 만들어야 한다. 먼저, $(l,r,d)$ 인자를 정의한다.

• $[l,r]$구간에서의 깊이 $d$

이제 다음의 과정을 따라가면서 해결한다.

1. 구간 $[l,r]$에서의 최대 값 $a_m$의 위치 $m$를 찾는다. $(a_m=max^{r}_{i=l}a_i)$
2. 정점 $a_m$의 깊이는 $d$이다.
3. 만약, $l<m$이라면, 다음 상태 $(l,m-1,d+1)$로 들어간다.
4. 만약, $m<r$이라면, 다음 상태 $(m+1,r,d+1)$로 들어간다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

void build(int l, int r, vector<int> const &a, vector<int> &d, int curD=0) {
  if(r<l) return;

  if(l==r) {
    d[l]=curD;
    return;
  }

  int m=l;
  for(int i=l+1;i<r;i++) [
    if(a[m]<a[l]) m=i;
  }
  d[m]=curD;

  build(l,m-1,a,d,curD+1);
  build(m+1,r,a,d,curD+1);
}

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int &x : a) cin>>x;

  vector<int> d(n);
  build(0,n-1,a,d);

  for(int x : d) cout<<x<<' ';
  cout<<endl;

  return;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

E. Accidental Victory

$i$번째 플레이어가 $a_i$개의 토큰을 가지고 있을 때 문제의 조건에 따라서 $i$번째 플레이어가 이길 수 있는지 확인하는 문제이다.

$a$가 [1,2,3,4]일때, 토큰 3개를 가지고 있는 플레이어가 이길 수 있다면, 3개보다 많은 토큰을 가진 플레이어들은 모두 이길 수 있다.

반면에, 토큰 3개를 가진 플레이어가 이길 수 없다면, 3개보다 적은 토큰을 가진 플레이어들은 모두 이길 수 없다.

따라서, 이분탐색으로 어떤 플레이어가 이길 수 있는지 없는지 확인하는 과정이 필요하다.

확인하는 과정은 어떤 토큰 $x$가 $x$보다 작은 토큰을 모두 가져가서 오른쪽 플레이어들을 이길 수 있는지 체크하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

void solve() {
  int n;
  cin>>n;
  vector<pair<ll,int> > a(n); // (token, index)
  for(int i=0;i<n;i++) {
    cin>>a[i].first;
    a[i].second=i;
  }

  sort(a.begin(),a.end());
  vector<int> c(n,1); // check

  int l=0, r=n-1;
  while(l<=r) {
    int mid=(l+r)/2;
    ll psum=0; // mid이전 플레이어들의 토큰을 모두 먹는다
    for(int i=0;i<=mid;i++) psum+=a[i].first;
    bool fail=false;
    for(int i=mid+1;i<n;i++) {
      if(psum<a[i].first) { // 이길 수 없다면
        fail=true;
        break;
      }
      else psum+=a[i].first; // 다음 플레이어를 이기면 토큰 흡수
    }
    if(!fail) r=mid-1;
    else {
      for(int i=0;i<=mid;i++) c[i]=0; // mid이전 플레이어들은 모두 불가능
      l=mid+1;
    }
  }

  vector<int> res;
  for(int i=0;i<n;i++) {
    if(c[i]) res.push_back(a[i].second+1);
  }

  sort(res.begin(),res.end());

  cout<<res.size()<<endl;
  for(int i=0;i<res.size();i++) cout<<res[i]<<' ';
  cout<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}