KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）

A. Century

주어진 년도를 보고 몇 세기인지 출력하는 문제이다.
1년부터 100년까지가 1세기, 101년부터 200년까지가 2세기이므로 100으로 나누어 떨어지지 않는 경우부터 다음 세기로 넘어가는 것을 알 수 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  if(n%100==0) cout<<n/100;
  else cout<<n/100+1;
  return 0;
}

B. 200th ABC-200

주어진 조건을 $k$번 수행했을 때, 나오는 결과값을 출력하는 문제이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  ll n,k;
  cin>>n>>k;
  while(k--) {
    if(n%200==0) n/=200;
    else {
      n*=1000;
      n+=200;
    }
  }
  cout<<n;
  return 0;
}

C. Ringo's Favorite Numbers 2

배열 $A$가 주어졌을 때, $A_i-A_j$가 200의 배수인 모든 경우의 수를 계산하는 문제이다.

$N$의 범위가 2 ≤ $N$ ≤ $2×10^5$이기 때문에 $O(N)$에 해결해야 한다.

어떠한 수 $a$, $b$가 있을 때, $a$와 $b$는 다음과 같이 표현할 수 있다.

• $a = 200*c_1+d_1$
• $b = 200*c_2+d_2$

$a$, $b$의 나머지인 $d_1$와 $d_2$가 같다면 $a-b$는 200의 배수가 될 수 있다. 즉, 배열의 원소들을 200의 나머지로 묶을 필요가 있다.

이제 각 묶음마다 2개씩 조합을 구해야 하므로 $\frac{x\times(x-1)}{2}$의 공식을 사용해서 누적해준다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  vector<ll> a(n),b(200);
  for(int i=0;i<n;i++) {
    cin>>a[i];
    b[a[i]%200]++;
  }
  ll ans=0;
  for(int i=0;i<200;i++) {
    ans+=(b[i]*(b[i]-1))/2;
  }
  cout<<ans;
  return 0;
}