京セラプログラミングコンテスト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ででっかくブッ込んどく。

②に５－１０分くらいで気づいて、すぐできた。

# 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;
}