atcoder 基礎

atcoder の基礎をまとめていきます

```.cpp
#include <iostream>
using namespace std;
main(){
  string s;
  int c;
  cin >> s;
  

  cout << c << endl;
}
```

cin >> a >> b >> c >> d >> e >> f;
は
cin >> a;
cin >> b;
cin >> c;
cin >> d;
cin >> e;
cin >> f;
と同義

B=BreakNumber 　解説

https://atcoder.jp/contests/abc068/tasks/abc068_b
```.cpp
#include <iostream>
using namespace std;
main(){
  int n;
  int max= 0,res = 0;
  cin >>n;
  for(int i = 1;i<n + 1;i++ ){
    int count,tmp;
    count = 0;
    tmp = i;
    while(true){   
        if(tmp % 2 == 0){
            tmp = tmp / 2;
            count++;
        }
        else break;
    }
    if(max < count){
        max = count;
        res = i;
    }
  }
  if(res == 0)res = 1;
  cout << res;
}
```
全探索
1からnまでを試していき最も大きな値更新したときにresに入れ記録


B - A to Z String 
```.cpp
#include <iostream>
#include <algorithm>
using namespace std;
main(){
    string s;
  	cin >> s;
    int min = 0,max = 0;
    bool flag = false;
    for(int i = 0;s[i] != '\0';i++){
        if(s[i] == 'A' && !flag){
            flag = true;
            min = i;
        }
        if(s[i] == 'Z'){
            max = i;
        }

    }
    //cout << max - min +1 <<endl;
    cout << max - min + 1 <<endl;
    //cout << max<<endl;
    
}
```
文字列の全探索条件で番目を記録
B - Cakes and Donuts

https://atcoder.jp/contests/abc105/tasks/abc105_b

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
bool flag = false;
int n;
cin >> n;
  for(int i = 0;i< 26; i++){
    for(int j = 0; j<15; j++){
      if(i * 4 + j * 7 == n){
        flag = true;
      }
    }
  }
  flag? cout <<"Yes" : cout << "No";

}
全探索　範囲を絞ることも可能


B - Palindromic Numbers

https://atcoder.jp/contests/abc090/tasks/abc090_b
```.cpp
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int up(int x) {return x/1000;}//上２桁
 
int swap1 (int x){
    
    int tmp1 = x/10,tmp2 = x%10;
    return tmp2 * 10 + tmp1;
}
 
int down(int x) {
    return swap1(x%100);
    }//下２桁
 
 
main(){
    int A,B;
    int count = 0;
    cin >> A >> B;
 
    for(int i = A;i<=B;i++){
        if(up(i) == down(i))count ++;
    }
    cout << count <<endl;
}
```
上二桁と下二桁に分け下二桁に関して入れ替え関数に引数あたえ入れ替える。


# ソートアルゴリズム
B - Snake Toy
https://atcoder.jp/contests/abc067/tasks/abc067_b
```.cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int N,K,sum = 0;
    int len[101];
    cin >> N >> K;
    for (int i = 0;i < N;i++)cin >> len[i];

    sort(len,len + N,greater<int>());
    for (int i = 0; i< K;i++)sum += len[i];
    cout << sum ;
}
```
std::sort()を利用するのが楽、アドレスを渡すことで直接小さい順に並び変えてくれる。
第三引数にgreater<int>()を入れることで降べき順になる
文字列も同様に操作できる


B - 文字列大好きいろはちゃんイージー

https://atcoder.jp/contests/abc042/tasks/abc042_b

```.cpp
#include <iostream>
#include <algorithm>
using namespace std;


int main(){
    string str[101];
    int n,l;
    cin>>n>>l;
    for(int i=0;i<n;i++){
        cin >> str[i];
    }
    sort(str,str + n);
    for(int i=0;i<=n;i++){
        cout<<str[i];
    }
}
```

# バケット法
B - Not Found

https://atcoder.jp/contests/abc071/tasks/abc071_b


```.cpp
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
#include <queue>
#include <regex>
 
using namespace std;
 
int main() {
    string S = "atcoderregularcontest";
    //cin >> S;
 
    vector<bool> A(26,false);//動的配列A[26]の宣言
 
    for( int i=0; i < S.size(); i++){
        A[S[i]-'a'] = true;
    }
 
    for( int i=0; i < 26; i++){
        if( A[i] == false ){
            cout << (char)(i+'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}
```
解説　
A[26]という配列を用意し文字のasciiコードに対応した数値をtrueにする（カウントでも可）
文字は'a' で97と認識


B - Counting Roads

https://atcoder.jp/contests/abc061/tasks/abc061_b

```.cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int N,M;
    int load[101],A[100] = {0};
    cin >> N >> M;
    for(int i = 1;i<M * 2 + 1;i++)cin >> load[i];
    for(int i = 1;i<M * 2 + 1;i++)A[load[i]]++;
    for(int i = 1;i < N + 1;i++) {
        cout << A[i] << endl;
    }
}
```
解説　バケットA[100]を使用し、都市iを記録、その後for文で都市の数を出力

C - Not so Diverse

https://atcoder.jp/contests/abc081/tasks/arc086_a
未完成
```.cpp
#include <iostream>
#include <algorithm>
using namespace std;

main(){
    int N,K,L = 0,sum,count = 1;
    cin >> N >>K;
    int A[N] = {0},B[N] = {0},ball[N] = {0};
    for(int i = 1;i<N+1;i++) cin >> ball[i];
    for(int i = 1;i<N+1;i++) A[ball[i]]++;
    for(int i = 1;i < N + 1;i++) {
        if(A[i])L++;//種類カウント
    }

    sort(A + 1,A + N + 1);
    //for(int i = 1;i<N+1;i++) cout << A[i] << endl;

    for(int i = 1;count < (L - K) + 1 ;i++){
        if(A[i] != 0){
            sum += A[i];
            count++;
        }
        
    }
    cout << sum <<endl;
}
```
# 時間制約　
1秒間for文を実行できる回数は 10^8 = 100,000,000 回程度


C - Takahashi's Information

https://atcoder.jp/contests/abc088/tasks/abc088_c
```.cpp
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main(){
  bool J = false;
  int C[3][3];
  rep(i,3)rep(j,3){cin >> C[i][j];}
  int a0,a1,a2,b0,b1,b2;
  rep(i,101)rep(j,101)rep(k,101){
    a0 = i;
    a1 = j;
    a2 = k;
    b0 = C[0][0] - a0;
    b1 = C[0][1] - a0;
    b2 = C[0][2] - a0;
    if(C[1][0] == a1 + b0 && C[1][1] == a1 + b1 && C[1][2] == a1 + b2 &&
      C[2][0] == a2 + b0 && C[2][1] == a2 + b1 && C[2][2] == a2 + b2){
      J = true;
    }
  }
  if(J){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}
```

C - Half and Half

https://atcoder.jp/contests/arc096/tasks/arc096_a


```.cpp
#include <iostream>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
main(){
    int A,B,C,X,Y,mini = 10000000001;
    cin >>A>>B>>C>>X>>Y;
    for(int i = 0; i < max(X,Y) + 1;i++){//iをCの枚数(1/2)とする
        int tmp = 0;
        int tx = X-i,ty = Y-i;

        if((X-i) < 0)tx = 0;
        if((Y-i) < 0)ty = 0;

        tmp = C*i*2 + A*tx + B*ty;  
        if(mini > tmp){
            mini = tmp;
        }
    }
    cout << mini << endl;
}
```
解説　繰り返しが多いので動かす変数をCのみにし他を関係式から導き出した。

A-Addition

https://atcoder.jp/contests/agc010/tasks/agc010_a

```.cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int N;
    cin >> N;
    int A[N],count,sum = 0,kisuu;
    bool check = true;
    for(int i = 0;i<N;i++){
        cin >> A[N];
        sum += A[N];
        if(A[N] % 2 == 1)kisuu++; 
    }

    if(sum % 2 == 1)check = false;
    if(kisuu % 2 == 1)check = false;
    if(!check) cout << "NO";
    else cout << "YES";

}
```

探索ではなく、偶数奇数でどういいうときにできないか　考える
今回は合計が奇数の場合と奇数の数が奇数の場合である。