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

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
[私のアカウント](https://atcoder.jp/users/nanami_brother)
[解いた問題](https://kenkoooo.com/atcoder/#/table/nanami_brother)
# 本日解いた問題
## B - Better Students Are Needed!
[B - Better Students Are Needed!](https://atcoder.jp/contests/abc260/tasks/abc260_b)
解答
```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() {
  ll n, x, y, z;
  cin >> n >> x >> y >> z;
  vec a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  vector<bool> jud(n, false);
  for(int i = 0; i < x; i++){
    ll ma = -1;
    ll tmp = 0;
    for(int j = 0; j < n; j++){
      if(jud[j]) continue;
      if(ma < a[j]){
        ma = a[j];
        tmp = j;
      }
    }
    jud[tmp] = true;
  }
  for(int i = 0; i < y; i++){
    ll ma = -1;
    ll tmp = 0;
    for(int j = 0; j < n; j++){
      if(jud[j]) continue;
      if(ma < b[j]){
        ma = b[j];
        tmp = j;
      }
    }
    jud[tmp] = true;
  }
  for(int i = 0; i < z; i++){
    ll ma = -1;
    ll tmp = 0;
    for(int j = 0; j < n; j++){
      if(jud[j]) continue;
      if(ma < a[j]+b[j]){
        ma = a[j]+b[j];
        tmp = j;
      }
    }
    jud[tmp] = true;
  }
  rep(i, n) {
    if(jud[i]) {
      cout << i+1 << endl;
    }
  }
}
```
### 解法
受験者の合否を判定する`bool`型配列を用意しておく。数学から合格者を判定していき、合格者を`true`にしていくことで結果が求まる。
## B - Tournament Result
[B - Tournament Result](https://atcoder.jp/contests/abc261/tasks/abc261_b)
解答
```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() {
  ll n;
  cin >> n;
  vector<vector<char>> a(n, vector<char>(n));
  rep(i, n){
    rep(j, n) cin >> a[i][j];
  }
  bool jud = true;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(i==j) continue;
      if(a[i][j]=='W'&&a[j][i]!='L') jud = false;
      else if(a[i][j]=='L'&&a[j][i]!='W') jud = false;
      else if(a[i][j]=='D'&&a[j][i]!='D') jud = false;
    }
  }
  if(jud) cout << "correct" << endl;
  else cout << "incorrect" << endl;
}
```
### 解法
`A[i][j]`が`W`のとき`A[j][i]`が`L`以外、`A[i][j]`が`L`のとき`A[j][i]`が`W`以外、`A[i][j]`が`D`のとき`A[j][i]`が`D`以外となる場合、矛盾する。
## C - Martial artist
[C - Martial artist](https://atcoder.jp/contests/abc226/tasks/abc226_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++)

vector<bool> seen;
void dfs(const vector<vector<int>> &G, int v) {
    seen[v] = true;
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; 
        dfs(G, next_v);
    }
}

int main() {
  ll n;
  cin >> n;
  vector<vector<int>> G(n);
  vec t(n);
  for(int i = 0; i < n; i++){
    cin >> t[i];
    ll k;
    cin >> k;
    for(int j = 0; j < k; j++){
      ll a;
      cin >> a;
      a--;
      G[i].push_back(a);
    }
  }
  seen.assign(n, false);
  dfs(G, n-1);
  ll res = 0;
  rep(i, n){
    if(seen[i]){
      res += t[i];
    }
  }
  cout << res << endl;
}
```
### 解法
Nを習得するために必要な技を考えるとき、Nから辿ることができるすべての技を習得する必要があるため、グラフとして考える。`DFS`を利用して、Nから辿れるすべての要素の時間の総和が答えとなる。
## C - ABC conjecture
[C - ABC conjecture](https://atcoder.jp/contests/abc227/tasks/abc227_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() {
  ll n;
  cin >> n;
  ll res = 0;
  for(ll i = 1; i*i*i <= n; i++){
    for(ll j = i; i*j*j <= n; j++){
      res += n/(i*j) - j + 1;
    }
  }
  cout << res << endl;
}
```
### 解法
Aがとりうる値が`1<=A^3<=N`であり、Bがとりうる値が`A<=B*A^2<=N`であるため、この範囲で探索することで結果が求まる。