Bootcamp for Beginners(Easy) レポ

書きながら解いていく形にしています
ついでに新しく学んだ関数なども付記しておきます
https://kenkoooo.com/atcoder/#/training/Boot%20camp%20for%20Beginners

# テンプレート
```cpp
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

/* accelration */
// 高速バイナリ生成
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

/* alias */
using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using pii = pair<int, int>;

/* define */
#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

/* rep */
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rep1(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define repd1(i,n) for(ll i=n;i>=1;i--)

/* func */
inline int in_int() {int x; cin >> x; return x;}
inline string in_str() {string x; cin >> x; return x;}

void Main() {

}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(0);
  
  Main();
}
```

# 1. Power Socket
要求を満たす電源タップ数を求める問題。
1. 増やすべきソケット数`b-1` (欲しいソケット数`b` - 元からあるソケット数`1`)
2. 電源タップを一つ増やすごとに増えるソケット数 = `a-1`
3. **増やすべき電源タップ数 = `切り上げ(b-1 / a-1)`**

ここで、切り上げの手法には「分母に分子(分母-1)を加算する」という方法をとっている
`ceil()`でも実装できる（が、計算に扱うデータがint型であり、キャスト（型変換）が必要になるため用いなかった）

```cpp
void Main() {
  int a = in_int();
  int b = in_int();

  // 分子に(分母-1)を足して繰り上げ処理
  cout << ((b-1)+(a-2)) / (a-1) << endl;
}
```

# 2. Rally
住民の移動エネルギーの総和が最小となる座標を求める問題。
1. 住所の座標を格納する配列`x`の最大値、最小値をとる
2. 最小値から最大値の間で全探索
    a. かかる労力の総和`pwr`を求める
    b. 最小値`min_pwr`より小さければ置き換える

`minmax_element()`の扱い方は下にまとめる

```cpp
void Main() {
  int n = in_int();
  vi x(n);
  rep(i, n) x.at(i) = in_int();

  pair mm = minmax_element(all(x));
  // intの最大値を取得
  int min_pwr = numeric_limits<int>::max();
  for(int p=*mm.first; p<=*mm.second; p++) {
    int pwr = 0;
    rep(i, n) pwr += pow(x.at(i) - p, 2);
    min_pwr = min(min_pwr, pwr);
  }

  cout << min_pwr << endl;
}
```

## minmax_element(first, end)
引数として範囲の最初の*イテレータ*と最後の*イテレータ*をとり、返り値として「最小値・最大値」の*イテレータ*のペアを返す。
ここでいうイテレータとは、配列におけるポインタを指す。イテレータが示すデータを取り出すには、イテレータを格納している変数などの頭に`*`をつけるとよい。

本コードの中では`*mm.first`が最小値、`*mm.second`が最大値を示す。
また、`min_element()`、`max_element()`も存在するので、どちらか一方でよいならこちらを推奨する。

# 3. Qualification simulator
参加者が通過できたかを判定する問題。
そのまま実装するだけ　先人のコードを参考にしました（ｱｻﾞｽ）

```cpp
void Main() {
  int n, a, b;
  cin >> n >> a >> b;
  string s = in_str();

  int all = 0;
  int foreign = 0;
  rep(i, n) {
    char c = s.at(i);
    bool isPass = false;
    if(c == 'a') {
      if(all < a+b) {
        isPass = true;
        all++;
      }
    }else if(c == 'b') {
      if(all < a+b && foreign+1 <= b) {
        isPass = true;
        all++;
        foreign++;
      }
    }
    YesNo(isPass);
  }
}
```

# 4. Tax Rate
値段から定価を求める問題。
Xについて1~Nの範囲で消費税込みの価格を調べ、Nと一致したら値を返す。

「`N/8`すればいけそう」なんて思っていたが、問題文の通り**税込み価格として存在しない値がある**点に注意。（原価が1円上がるごとに0.08円加算され、この積み上げが1円を超えた時にスキップされる値がある）

```cpp
void Main() {
  int n = in_int();
  int ans;
  bool exist = false;

  rep1(i, n) {
    int price = (int)(i * 1.08);
    if(price > n) break;
    if(price == n) {
      exist = true;
      ans = i;
      break;
    }
  }

  if(exist) {
    cout << ans << endl;
  } else {
    cout << ":(" << endl;
  }
}

```

# 5. Can you solve this?
コードを表す整数値をもとに正常動作する行数を求める問題。
式が与えられているので、配列Aの各行に対して判定するように実装する

```cpp
void Main() {
  int n, m, c;
  cin >> n >> m >> c;
  vi b(m);
  rep(i, m) b.at(i) = in_int();
  vvi a(n, vi(m));
  rep(i, n) {
    rep(j, m) a.at(i).at(j) = in_int();
  }

  int cnt = 0;
  rep(i, n) {
    int sum = c;
    rep(j, m) sum += a.at(i).at(j) * b.at(j);
    if(sum > 0) cnt++;
  }

  cout << cnt << endl;
}
```
# 6. Bishop
将棋の角が動けるマス数を求める問題。
動けるマス数は**マスの総数÷2**であるため`h*w/2`をすれば求められる。（答えが小数の場合は切り上げ）

**w,hのどちらかが1をとる場合、角は動けない（動けるマス数は１になる）** ことに注意。
繰り上げは「分子に分母-1を加算すると繰り上げと同等の結果が得られる」という性質を利用している。

```cpp
void Main() {
  ull h = in_int();
  ull w = in_int();

  ull ans = ((h*w)+1)/2;
  if(h == 1 || w == 1) ans = 1;
  cout << ans << endl;
}
```

# 7.Bingo
ビンゴの記録をaにメモし、縦横斜めに探索。
どうでもいいけど変数をなるべく再利用する形で書いてみた。

```cpp

bool isBingo(int cnt) {
  if(cnt >= 3) {
    cout << "Yes" << endl;
    return true;
  }

  return false;
}

void Main() {
  vvi a(3, vi(3));
  rep(i, 3) rep(j, 3) a.at(i).at(j) = in_int();
  int n = in_int();
  vi b(n);
  rep(i, n) b.at(i) = in_int();

  vvi card(3, vi(3, 0));
  rep(i, n) {
    rep(r, 3) rep(c, 3) {
      if(a.at(r).at(c) == b.at(i)) card.at(r).at(c)++;
    }
  }
  
  int cnt;
  // 縦横
  rep(i, 3) {
    cnt = 0;
    rep(j, 3) cnt += card.at(i).at(j);
    if(isBingo(cnt)) return;

    cnt = 0;
    rep(j, 3) cnt += card.at(j).at(i);
    if(isBingo(cnt)) return;
  }

  //斜め
  rep(i, 3) {
    cnt = 0;
    rep(i, 3) cnt += card.at(i).at(i);
    if(isBingo(cnt)) return;

    cnt = 0;
    rep(i, 3) cnt += card.at(i).at(2-i);
    if(isBingo(cnt)) return;
  }

  cout << "No" << endl;
}
```

# 8.1 21
整数Nに対して平方根（整数値）を求め、これの二乗がNに等しいかを確認する。

```cpp
void Main() {
  string a = in_str();
  string b = a + in_str();
  int n = stoi(b);

  int sqrt_n = sqrt(n);
  YesNo(n == pow(sqrt_n, 2));
}
```

# 9.Collecting Balls (Easy Version)
タイプA,B両者を選んだ場合の歩数を逐一求め、小さいほうを合算していく。
移動距離は折り返しであるため、x2であることに注意。

```cpp
void Main() {
  int n = in_int();
  int k = in_int();
  vi x(n);
  rep(i, n) x.at(i) = in_int();

  int sum = 0;
  rep(i, n) sum += min(x.at(i), abs(x.at(i) - k)) * 2;

   cout << sum << endl;
}
```

# 10.Card Game For Two
渡された配列を降順（数値が大きい順）にソートして、上から交互に足していく
`sort()`して`reverse()`でもよいが、`sort()`関数の第三引数に`greater<int>()`を指定すると降順でソートしてくれて便利。

```cpp
void Main() {
  int n = in_int();
  vi a(n);
  rep(i, n) a.at(i) = in_int();
  
  int alice = 0;
  int bob = 0;
  // sort(all(a));
  // reverse(all(a));
  sort(all(a), greater<int>());
  rep(i, n) {
    if(i % 2 == 0) {alice += a[i];} else {bob += a[i];}
  }
  cout << alice - bob << endl;
}
```

## sort(..., greater<int>())
sort関数で降順に並べ替えるときの記述。
`greater<int>()`については「2つの値のうちより大きいほうを選択する構造体」という認識でいいかも（間違ってたらｺﾞﾒﾝﾅｻｲ）
[std::greater](https://en.cppreference.com/w/cpp/utility/functional/greater)

`greater<int>()`の部分に自作のソート関数を置けば、**独自の基準でソートする**ことも可能なよう。
[C++ ソートの補足](https://dai1741.github.io/maximum-algo-2012/docs/cpp-sort/)

# 11. Break Number
1~nを全探索するだけ

```cpp
void Main() {
  int n = in_int();
  int ret = 1;
  int max_cnt = 0;

  rep1(i, n) {
    int w = i;
    int cnt = 0;
    while(w % 2 == 0) {
      w /= 2;
      cnt++;
    }
    
    if(max_cnt < cnt) {
      max_cnt = cnt;
      ret = i;
    }
  }

  cout << ret << endl;
}
```

# 12.Traveling Salesman around Lake
この場合の最適解は「隣り合う家の距離の和 - 最大値」になる。
注意点として、**始端と終端はつながっている**ため、ここの距離も含める。

```cpp
void Main() {
  int k = in_int();
  int n = in_int();
  vi a(n);
  rep(i, n) a.at(i) = in_int();

  int ans = 0;
  vi diff(n);
  rep(i, n-1) diff.at(i) = abs(a.at(i) - a.at(i+1));
  diff.at(n-1) = (k - a.at(n-1)) + a.at(0);
  int max = *max_element(all(diff));
  int sum = 0;
  rep(i, n) sum += diff.at(i);
  ans = sum - max;

  cout << ans << endl;
}
```