교세라 프로그래밍 콘테스트 2021 (AtCoder Beginner Contest 200) 비망록

결과
리어 타이 불참
A: 빨리 할 수 ​​있었다
B: 빨리 할 수 ​​있었다
C:해설 보고 스스로 기술
D: 미
E: 미
F: 미

A - Century
입력된 숫자가 몇 세기 응답하는 문제.
100년은 어느 세기인가? 라고 하는 곳만 경우에 따라서 나눗셈의 몫을 출력할 뿐.
즉각적인 답변.

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

int main() {
  int N;
  cin>>N;
  int ans;
  if(N%100==0){
  cout << N/100 <<endl;
  }
  else{
    cout << N/100+1<<endl;
  }

  }

B - 200th ABC-200
정수 N에 대해, 어느 조작을 K회 한다.
①N이 200의 배수일 때는 200으로 나눈다
② 상기 이외에는 아래에 200을 추가한다.

①의 조작은 간단.
②의 조작도, 실제로는 1000을 곱해 200을 더할 뿐이므로, 간단하게 산수적으로 모두 기재 가능.
카타가 커지므로 우선 unsigned long long으로 확실히 부딪친다.

②에 5-10분 정도로 눈치채고, 곧 생겼다.

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

int main() {
  unsigned long long N,K;
  cin>>N>>K;

  for(int i=0;i<K;i++){
    if(N%200==0){
    N=N/200; 
    }
    else{
    N=N*1000+200;
    }
  }
  cout<<N<<endl;
  }

C - Ringo's Favorite Numbers 2



최대로 N=2E5이므로, 전체 탐색이라면 2E5 C 2=1E10 정도이므로 TLE가 된다.
되겠지, 라고 생각하고 코드를 썼지만 역시 되었다.
스스로는 눈치채지 못했기 때문에 해설을 본다.

「수열 중에서 임의의 Ai,Aj 2수를 선택해, Ai-Aj가 200의 배수가 되는 개수」를
"수열 중에서 200으로 나눈 때의 너무 같아지는 것을 추출하고,
너무나 같아진 수의 조합의 수」라고 읽는다.

예를 들어,
원수열:[1]123 [2]223 [3]123 [4]523 [5]200 [6]2000
에 대해, 각 수를 200으로 나누어 너무 많이 내면,
여수 열:[1]123[2]23[3]123[4]123[5]0[6]0
된다. 같은 나머지 수, 예를 들어 [1] 123과 [4] 523은 차이가 200의 배수입니다.
코코가 눈치채는 포인트. 즉,
"같은 나머지 수의 조합 = 차이가 200의 배수가 되는 조합"
라는 것.
나머지 123은 [1], [3], [4]의 3개이므로 3C2에서 3가지의 조합이 있다.
너무 0은 [5], [6]의 2개이므로, 2C2에서 1가지의 조합.
더해 총 4가지가 대답이 된다.
따라서 일반적으로 쓰면,
・원수열 모두를 200으로 나누어 너무나를 내고, 1~199의 배켓으로 개수를 카운트한다.
· 2 개 이상의 각 비트에서 nC2를 계산하여 조합 수를 계산합니다.
・조합의 수를 전부 더한다
그렇게 하면 된다고 된다.

「같은 나머지의 수=차이가 200의 배수가 된다」를 알면, 어쩐지 버킷 세트로 할 수 있다는 것을 깨달을 것 같다.
아시면 할 수 있지만 시리즈이므로, 경험치가 중요하다는 것으로 종료.

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

int main() {
    long N;
    long A[2500000];
    map<long, long>B;
    long ans =0;
    cin>>N;

    for(long i=0;i<N;i++){
        cin>>A[i];
        B[A[i]%200]=B[A[i]%200]+1;//各余りの数をｶｳﾝﾄする
    }

    for(int i=0;i<200;i++){//200余りは0~199
        if(B[i]>1){
          ans=ans+(B[i]*(B[i]-1))/2; //2個を選ぶのでnC2
        }
    }
    cout<<ans<<endl;
}