Codeforces Round 697 (Div.3)

Updated:

A. Odd Divisor

정수 $n$이 주어질 때 홀수인 수 $x$로 나누어 떨어지는지 확인하는 문제이다.

먼저, $n$이 홀수일 때 홀수인 수 $x$로 반드시 나누어 떨어진다.

다음, $n$이 짝수일 때 $n$을 만드는 방법은 세 가지가 있다.

  1. 짝수 * 짝수 = 짝수
  2. 짝수 * 홀수 = 짝수
  3. 홀수 * 짝수 = 짝수

$n$을 짝수로 이루어진 수를 제외하면 모두 홀수 $x$를 가지고 있다는 이야기이다. 그리고 소수인 짝수는 2가 유일하기 때문에 $n$을 2로 계속 나누다 마지막에 1이 남았을 때 $n$이 2의 제곱수의 형태를 갖는다는 것을 알 수 있다.

  • 만약, $n$ & $(n-1)$이 0이 아니라면 n은 홀수인 $x$를 가지고 있다.
  • $n$ & $(n-1)$이 0이라면 2로 이루어진 제곱수의 형태를 가지고 있어서 $x$가 없다.

예를들면, $n$이 6이라면 이진수로 110과 101을 AND연산했을 때 100 = 4가 출력되면서 홀수가 존재하는 것을 알 수 있다.

반면에, $n$이 4라면 이진수로 100과 011을 AND연산했을 때 0이 출력되면서 홀수가 존재하지 않음을 알 수 있다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  ll n;
  cin >> n;
  if (n & (n - 1)) {
    cout << "YES\n";
  } else {
    cout << "NO\n";
  }
}

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

B. New Year’s Number

정수 $n$이 주어질 때 2020과 2021의 합으로 이루어졌는지 확인하는 문제이다.

$x$를 2020의 개수, $y$를 2021의 개수라 가정하면 $n=2020\times x + 2021\times y$가 성립되어야 한다.

위의 식을 다시 정리하면 $n=2020(x+y)+y$이며, $n-y$는 $2020$으로 나누어 떨어져야 한다. 즉, 다음의 식이 성립되어야 한다.

$x=\frac{n-y}{2020}-y$

만약, $x$가 0보다 크거나 같다면 $n$은 2020과 2021로 표현될 수 있다.

#include <bits/stdc++.h>
#include <utility>
using namespace std;

using pii = pair<int, int>;

void solve() {
  int n;
  cin>>n;
  int cnt2021 = n%2020;
  int cnt2020 = (n-cnt2021)/2020 - cnt2021;
  if(cnt2020>=0 && 2020*cnt2020 + 2021 * cnt2021 == n) {
    cout<<"YES\n";
  }
  else {
    cout<<"NO\n";
  }
}

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

C. Ball in Berland

주어지는 준비된 페어 ($a,b$)에 대해 가능한 순서쌍을 구하는 문제이다.

먼저, boys와 girls를 그래프의 정점이라 생각하면 우리는 ($a,b$)에 대해 이분그래프라 생각할 수 있다. 그리고 ($a,b$)는 $a$와 $b$에 edge(간선)가 생긴 것이라 하자.

그러면 우리는 이 그래프에서 두 간선를 찾는데 서로 교차하지 않는 간선들을 찾아야 한다.

이제 $deg(x)$를 정점 $x$가 포함된 간선의 개수라 하자.

어떠한 간선을 연결하는 두 정점을 $a,b$가 있을 때 $a,b$를 연결하는 간선과 교차하지 않은 간선의 개수는 $k-deg(a)-deg(b)+1$이다. (집합의 개념)

  • +1을 하는 이유는 $deg(a)$와 $deg(b)$에 ($a,$$b$)를 연결하는 간선이 두 번 중복되기 때문이다.

따라서 모든 간선에 대해 전부 더해주고 두 번더해지므로 마지막에 2를 나누면 된다.

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

void solve() {
    int A, B, k;
    cin >> A >> B >> k;

    vector<int> a(A+1), b(B+1);
    vector<pair<int, int> > edges(k);

    for(int i=0;i<k;i++) cin>>edges[i].first;
    for(int i=0;i<k;i++) cin>>edges[i].second;

    for (int i=0;i<k;i++) {
        int x=edges[i].first;
        int y=edges[i].second;
        a[x]++;
        b[y]++;
    }

    ll ans = 0;
    for (int i=0;i<k;i++) {
        int x=edges[i].first;
        int y=edges[i].second;
        ans += k - a[x] - b[y] + 1;
    }
    cout << ans / 2 << "\n";
}

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

D. Cleaning the Phone

필요한 메모리를 확보하면서 가장 적은 convience points를 잃어야 하는 문제이다.

convience points는 2가지이며 $b_i=1$ 또는 $b_i=2$이다. 우리는 1과 2에 해당하는 app을 따로 저장해야 한다.

  • $b_i=1$인 app의 메모리는 vector<int> a에, $b_i=2$인 app의 메모리는 vector<int> b에 저장하도록 한다.
  • 다음 a,b 모두 내림차순으로 정렬한다.

a에서 먼저 필요한 app을 합친 후 나머지를 b에서 가져오면서 필요한 메모리 m을 확보할 수 있는지 확인한다.

  • 먼저, $b$의 메모리 총합을 시작으로 $a_i$를 하나씩 추가하면서 필요한 메모리 한해서 필요없는 $b_i$를 빼준다. ```cpp #include #include #include #include // accumulate함수 헤더 #define ll long long #define INF 987654321 using namespace std;

void solve() { int n, m; cin»n»m; vector a,b; vector v(n); for(int i=0;i<n;i++) cin>>v[i]; for(int i=0;i<n;i++) { // bi=1, bi=2인 앱을 따로 저장 int x; cin>>x; if(x==1) a.push_back(v[i]); else b.push_back(v[i]); }

// a, b 내림차순 정렬 sort(a.rbegin(),a.rend()); sort(b.rbegin(),b.rend());

ll curSumA=0; int r=b.size(); ll curSumB=accumulate(b.begin(),b.end(),0ll); // b의 메모리 총합 int ans=INF; for(int l=0;l<=a.size();l++) { // a를 하나 늘려주면 while(r>0 && (curSumA+curSumB-b[r-1] >= m)) { // m을 지키는 한에서 b에서 하나 뺄 수있다. r–; curSumB-=b[r]; }

if(curSumB+curSumA >= m) {
  ans=min(ans,2*r+l);
}
if(l!=a.size()) {
  curSumA+=a[l];
}   }

cout«(ans==INF ? -1 : ans)«endl; }

int main() { freopen(“input.txt”,”r”,stdin); int t; cin » t; while (t–) { solve(); } return 0; } ```

Comments