AtCoder 勉強記録[C++] その10

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
[私のアカウント](https://atcoder.jp/users/nanami_brother)
[解いた問題](https://kenkoooo.com/atcoder/#/table/nanami_brother)
# 本日解いた問題
## B - Perfect String
[B - Perfect String](https://atcoder.jp/contests/abc249/tasks/abc249_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string s;
  cin >> s;
  map<char, ll> res;
  bool up = false, low = false;
  for(int i = 0; i < s.size(); i++){
    res[s[i]]++;
    char c = s[i];
    ll jud = c;
    if(jud < 91 && jud >= 65) up = true;
    else if(jud < 123 && jud >= 97) low = true;
  }
  if(!up||!low) {
    cout << "No" << endl;
    exit(0);
  }
  for(auto const&[k,v]: res){
    if(v >= 2) {
      cout << "No" << endl;
      exit(0);
    } 
  }
  cout << "Yes" << endl;
}
```
### 解法
まず、文字列に大文字と小文字どちらも含まれているかを判定し、含まれていたらすべての文字が相違であるかを判定する。
## B - Enlarged Checker Board
[B - Enlarged Checker Board](https://atcoder.jp/contests/abc250/tasks/abc250_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  vector<string> tile(n,string(n,'a'));
  vector<string> res(n*a, string(n*b,'a'));
  for(int i = 0; i < n; i++){
    if(i%2==0){
      for(int j = 0; j < n; j++){
        if(j%2==0) tile[i][j] = '.';
        else tile[i][j] = '#';
      }
    }
    else {
      for(int j = 0; j < n; j++){
        if(j%2==0) tile[i][j] = '#';
        else tile[i][j] = '.';
      }
    }
  }
  for(int i = 0; i < a*n; i++){
    for(int j = 0; j < b*n; j++){
      res[i][j] = tile[i/a][j/b];
    }
  }
  rep(i, a*n) cout << res[i] << endl;
}
```
### 解法
まず、`N×N`個のタイルについて考える。上から奇数番目の最初のタイルは白となり偶数番目のタイルは黒となる。また、左から数えて最初のタイルが白の場合奇数番目が白、偶数番目が黒となり、最初のタイルが黒の場合は逆になる。このことから`N×N`のタイルの色を入れておく配列を用意する。`(A×N)×(B×N)`個のマス目の色は所属するタイルの色から確定することができる。
## B - At Most 3 (Judge ver.)
[B - At Most 3 (Judge ver.)](https://atcoder.jp/contests/abc251/tasks/abc251_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n, w;
  cin >> n >> w;
  vec a(n);
  rep(i, n) cin >> a[i];
  vector<bool> cnt(w+1);
  for(int i = 0; i < n; i++){
    if(a[i] <= w)cnt[a[i]] = true;
  }
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      ll ad = a[i] + a[j];
      if(ad <= w) cnt[ad] = true;
    }
  }
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j < n; j++) {
      for(int k = j + 1; k < n; k++){
        ll ad = a[i] + a[j] + a[k];
        if(ad <= w) cnt[ad] = true;
      }
    }
  }
  ll res = 0;
  for(int i = 0; i < w+1; i++) {
    if(cnt[i]) res++;
  }
  cout << res << endl;
}
```
### 解法
まず、要素数`W+1`個のbool型配列を用意しておく。`N <= 300`であるため3重ループを使用しても問題なく計算ができる。3個以下の異なるおもりを選ぶパターンをすべて計算して、bool型配列を`True`にしていく。最後に`True`の数を出力する。
##C - The Kth Time Query
[C - The Kth Time Query](https://atcoder.jp/contests/abc235/tasks/abc235_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n, q, x, k, a;
  cin >> n >> q;
  map<ll ,vector<ll>> que;
  rep(i, n) {
    cin >> a;
    que[a].push_back(i+1);
  }
  rep(i, q){
    cin >> x >> k;
    if(que[x].size() < k) {
      cout << "-1" << endl;
      continue;
     }
    cout << que[x][k-1] << endl;
  }
}
```
### 解法＋メモ
`Map`を利用して解くことで計算量を減らすことができる。`Map`の`value`に配列を使用し、`A`の要素を`key`に、要素が前から何番目かを`value`に入れていく。`x`と`k-1`が`Map`に存在するとき出力し、存在しないときは-1を出力する。`Map`の要素に配列を使う発想がなかったため必ず覚えておきたい。