AtCoder Beginner Contest 205


https://atcoder.jp/contests/abc205

当日参加
A:AC　書くだけ
B:AC　書くだけ
C:AC　場合分けした力業
D:解答見て勉強　二分探索を使う

https://atcoder.jp/contests/abc205/tasks/abc205_a
100ml当たりAkcal。
Bmlなら何kcal?
なんのひねりもなし。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    double A,B;
    cin>>A>>B;
    double cal =(A*B)/100;
    cout<<cal<<endl;
}
```
https://atcoder.jp/contests/abc205/tasks/abc205_b
ある数列A(N)が、1~Nまでの数の並べ替えで等価にできるか。
一個でも違う数があったらNGなので、mapで同じ数が２個以上あったらNG判定にした。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    int N;
    int A[1100];
    map<int,int>AA;
    bool flg=0;
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>A[i];
        AA[A[i]]++;
        if(AA[A[i]]>1){
            flg=1;
        }
    }
    if(flg==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}
```

https://atcoder.jp/contests/abc205/tasks/abc205_c
A^CとB^Cの大小関係を調べるだけの問題。
だけど、A,Bは-1E9~1E9,Cは1E9とｸｿでかいので、普通に計算するとNG。
A､Bの大小関係から比較するが、A,Bの正負とCの偶奇でマイナスになったりプラスになったりするなーと直感的にすぐわかる。
もっとまとめられそうだなーと思いつつ、一つ一つのケースで場合わけをした。
ｺｰﾄﾞ長くなってミスしそうなので、どっちがいいか微妙だけど、とりあえずAC。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    long long A,B,C;
    cin>>A>>B>>C;
    string ans;
    long long AA=abs(A);//A絶対値取得
    long long BB=abs(B);//B絶対値取得
    long long amari=C%2;//C偶奇判定
    if(A==B){
        ans="=";
    }
    else{
        if(amari==0){//Cが偶数の時
            if(AA<BB){
                ans="<";
            }
            else if(AA==BB){
                ans="=";
            }
            else{
                ans=">";
            }        
        }
        else{//Cが奇数の時
            if(A<0){
                if(B<0){//AとBが負の時
                    if(AA<BB){
                        ans=">";
                    }
                    else{
                        ans="<";
                    }      
                }
                else{//Aが負、Bが正の時
                    ans="<";//Bが正になるので
                }
                
            }
            else{
                if(B<0){//Aが正、Bが負の時
                    ans=">";
                }
                else{//Aが正、Bが正の時
                    if(AA<BB){
                        ans="<";
                    }
                    else{
                        ans=">";
                    }    
                }
            }
        }
    }
    cout<<ans<<endl;
}
```

https://atcoder.jp/contests/abc205/tasks/abc205_d
配列Aに含まれない数のうち、K番目の数を返せ、という問題。
最初は配列Aに含まれない数列Bを作って、Kのｲﾝﾃﾞｯｸｽで返すｺｰﾄﾞを作ったが、
Aは最大1E18なので、Bの要素数も最大で1E18程度までいってしまうため、メモリ不足。

↓が最初に書いたｺｰﾄﾞ。
A[i]-A[i-1]を計算し、その数要素間の差を出す。
その数分だけカウントして、配列Bにpush_backしていく。
AC3つで残りすべてRE。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    long long N,Q;
    long long Amax=0;
    long long count=0;
    long long A[110000];
    vector<long long>B;
    long long K[110000];
    cin>>N>>Q;
    A[0]=0;
    for(int i=1;i<=N;i++){
        long long dif=0;
        cin>>A[i];
            if(Amax<A[i]){
                Amax=A[i];
            }        
        dif=A[i]-A[i-1];
        if(dif>1){
            for(int j=1;j<dif;j++){
                B.push_back(A[i-1]+j);
                count++;
            }
        }        
    }
    for(int i=1;i<=Q;i++){
        cin>>K[i];    
    }
    for(int i=1;i<=Q;i++){\
        if(K[i]>count){
            cout<<Amax+K[i]-count<<endl;
        }
        else{
            cout<<B[K[i]-1]<<endl;
        }
    } 
}
```

答えの配列を作ると詰んだので、回答を見る。
・A[]以下かつ配列Aに含まれない数をB[]とする配列を定義する
　A{3,5,6,7}なら、B{2,3,3,3}となる。
　3より小さくAに含まれない数は1,2の二つなので2、
　5より小さくAに含まれない数は1,2,4の三つなので3 という感じ
・クエリKに対して、それがどの要素間にあるのかを調べる
　ここで二分探索関数lower_bound(ｲﾃﾚｰﾀ1, ｲﾃﾚｰﾀ2, key)を使う。
　これはイテレータ1,イテレータ2の中で、key以上になる最小の要素のイテレータを返す。
　key=3なら、lower_bound(B.begin(),B.end(),key)で一番頭の3のイテレータを返す。
　これをうまく使って実装。
・Kをkeyとして、key>Bの最大値(=B[N])なら、Aの最大値(=A[N])からK-B[N]分進んだ数字がans
・key<=B[N]の時、keyがB配列の数値と等しい時は、B配列とkeyが一致するｲﾝﾃﾞｯｸｽをaとして、A[a-1]から差分K-B[a-1]だけ進んだ数字がans


```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    long long N,Q;
    long long A[110000];
    
    vector<long long>B;
    long long K[110000];
    long long kk;
    cin>>N>>Q;
    A[0]=0;
    B.push_back(0);
    for(int i=1;i<=N;i++){
        cin>>A[i];
        B.push_back(B[i-1]+A[i]-A[i-1]-1);
    }    

    for(int i=1;i<=Q;i++){
        long long ans=0;
        cin>>kk;
            if(kk<=B[N]){
                auto a=lower_bound(B.begin(),B.end(),kk)-B.begin();
                ans=A[a-1]+kk-B[a-1];
                cout<<ans<<endl;
            }
            else{
                ans=A[N]+kk-B[N];
                cout<<ans<<endl;
            }
    }
}
```