ABC-C第13弾

<img width="870" alt="result.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/13d5bd2b-c223-dd5a-dccd-3d3d6de99978.png">




- [バチャ第13弾](https://not-522.appspot.com/contest/6590538069311488)



# ABC061 「[Big Array](https://beta.atcoder.jp/contests/abc061/tasks/abc061_c)」

## 考察と解法

- $a$が$b$個あるという情報を`map`で管理する。
- あとは愚直にやるだけ。



## [コード](https://beta.atcoder.jp/contests/abc061/submissions/2421725)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll N, K;
map<ll, ll> mp;

int main() {
   cin >> N >> K;
   for (int i = 0; i < N; i++) {
      ll a, b;
      cin >> a >> b;
      mp[a] += b;
   }

   ll cnt = 0;
   for (auto x : mp) {
      cnt += x.second;
      if (cnt >= K) {
         cout << x.first << endl;
         return 0;
      }
   }

   return 0;
}
```



## 感想

- オーバーフローで1WAでた。
- なんか上位陣は`K -= x.second`とかしてたけど、僕はああいう考え方できない。


# ABC062 「[Chocolate Bar](https://beta.atcoder.jp/contests/abc062/tasks/arc074_a)」

## 考察

- なにをするのが最善かよく分らないため、いくつか分割パターンを考えてみる
- すると、以下の4パターンがあることがわかる。
- 左2つと右2つは反転させただけなのでほとんど同じ。なので、右2つについてのみ考察すればよい。


![a.png](https://qiita-image-store.s3.amazonaws.com/0/218584/f0cd37d9-baa7-c2fc-ca61-95a82a86cbff.png)


- まず、愚直な方法として全探索をしてみたくなる。すると、以下のように赤線と緑線を全探索することになる。

<img width="201" alt="e.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/f1318164-b2b2-d669-9e8b-c57ff14348fa.png">


- でも、それでは$O(H^2 )$とかそんな感じの計算量になるため間に合わない。
- なので、**値を固定する**という考え方を使う。**ある値を固定して、その状況から他の値を求める**というもの。ここでは、赤線を固定することにする。そのとき、緑線が$O(1)$くらいでどこかに確定できないかを考える。ここで、緑戦は残った部分の半分くらいの場所がいいのでは？と思いつく。ただ、ホントに半分でいいかわからないため、実験してみる。ソースは以下のような感じ。この実験コードは縦と横に分ける場合のみを考えている。

### 実験コード

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
   ll H, W; cin >> H >> W;

   for (int h = 1; h < H; h++) { // 横に分割
      for (int w = 1; w < W; w++) {
         // 縦に分割
         ll a = h * W;
         ll b = (H-h)*w;
         ll c = (H-h)*(W-w);
         ll diff = abs(max({a, b, c}) - min({a, b, c}));
         printf("%d: %d\n", w, diff);
      }
      puts("--------------");
   }

   return 0;
}
```

- 例えば入力例2で試すと以下のような結果が得られる。これにより、残りを半分で割ればいいのでは？というのがなんとなく正しい気がしてくる。ここで考察終了！

```
4 5
1: 9
2: 4 // 半分のとき
3: 4 // 半分のとき
4: 9
--------------
1: 8
2: 6 // 半分のとき
3: 6 // 半分のとき
4: 8
--------------
1: 14
2: 13 // 半分のとき
3: 13 // 半分のとき
4: 14
--------------
```



## 解法

<img width="594" alt="f.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/436e297d-fa45-38a0-3f96-b3812dc4a5f9.png">


-  縦をどこで分割するかを全探索する。
- 縦の分割地点を固定したとき、残りの部分は半分に切る
- あとは縦と横を反転させて同じことをする



## [コード](https://beta.atcoder.jp/contests/abc062/submissions/2454090) 

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
   ll H, W; cin >> H >> W;

   ll ans = 1e18;
   for (int k = 0; k < 2; k++) {
      for (int i = 1; i < H; i++) {
         ll a = i*W; // 一番上のやつの面積
         // 縦と横に3分割したとき 
         ll b = (W/2) * (H-i);
         ll c = ((W+1)/2) * (H-i);
         ans = min(ans, abs(max({a, b, c}) - min({a, b, c})));
         // 縦に3分割したとき 
         b = ((H-i)/2) * W;
         c = ((H-i+1)/2) * W;
         ans = min(ans, abs(max({a, b, c}) - min({a, b, c})));
      }
      swap(H, W);
   }

   cout << ans << endl;

   return 0;
}
```



## 感想

- 必要最小限のパターンを自分で考えるみたいな思考は大事な気がする。
- **まずは全探索を考える！！！これすごい大事だと思う！！！**なんかいつもきれいに解く方法を優先して考えてしまうけど、全探索から計算量を落とすっていう問題も結構ある気がする。
- でもどこで区切るかを全探索しよう！ってなかなかならない。3つに区切りたい→2つ切る場所がある→その2つの切る場所を全探索しよう！みたいな流れかなー？
- 比率を考えるとか。その他いろいろ
- **計算量を落とすときは値を固定する**っていうのすごい大事だと思う。よく使う考え方だけどなかなか思いつかない。全探索を考えるとき、値を固定して計算量落とせないかなーと考える癖をつけたいところ。
- 上位陣のコードを参考に書いた。縦と横を90ど回転させて同じ処理をするだけだから`swap(H, W)`とするのはすごい頭いいと思った。関数にしてもいいと思うけどめんどかったら`swap`でよさげ



## おまけ

- この問題について考えたことを適当に書くだけ。ほんとにテキトー

### 他の思いつき方

#### 横に3分割する場合を考える

- まず、横に3分割する場合を考える。すると、大体縦の長さはそれぞれ$\frac{H}{3}$になる。きれいに3で割り切れない場合がある。そのときは、最大で2余る。2余ったやつは2つの欠片に割り当てる。C, Bの順に優先して足していく。
- すると、以下の図のようになる。よって、3で割り切れる場合は0、3で割り切れない場合は$(\frac{H}{3}+1)W - \frac{H}{3}$となる。（式変形すれば答えがWになることに気が付くけど別にそこまでしなくてもいいや）

<img width="797" alt="c.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/57c4d807-b282-70c6-f9a2-71dbffb26a59.png">


#### 縦と横に3分割した場合を考える

![half.png](https://qiita-image-store.s3.amazonaws.com/0/218584/ece0faa9-5307-15a1-a0dd-12ebd995c377.png)


- 次に、縦と横に3分割した場合を考える。


- できるだけ均等に分けたいとき、上の画像のように分けたいなーと直感的に思う。でも、上の画像は$A:B:C=2:1:1$になっているため均等ではない。均等にするためには、Aの境界線を上に引き上げる必要がある。境界線を上に引き上げていけば、Aの面積は小さくなり、B, Cの面積は大きくなっていく。
- でも、どこまで引き上げればいいかわからない。なので、縦の範囲をぜんたんさくして　分割する地点を探せばいい。

### 解法

- 横に3分割した場合を考える。HかWが3で割れたら0、割れなければ$(\frac{H}{3}+1)W - \frac{H}{3}$となる。
- 縦と横に3分割した場合を考える。このとき、横に分割する線をループで探索して、下の四角形を半分にする。
- 上記の2つを縦について、横について両方やる。

#### 思いつき方1のコード

- [思いつき方1のコード](https://beta.atcoder.jp/contests/abc062/submissions/2439798)





# ABC063 「[Bugged](https://beta.atcoder.jp/contests/abc063/tasks/arc075_a)」

## 考察と解法

- 典型的なDPでできそうなので漸化式を立ててみる。
- すると、だいたい以下のような感じになる。

```math
dp[i+1][j] = \left\{
\begin{array}{ll}
dp[i][j]  \\
dp[i][j] \  or \ dp[i][j-s[i]] & (j \geq s[i]) \\
\end{array}
\right.
```

## [コード](https://beta.atcoder.jp/contests/abc063/submissions/2423454)

```cpp
#include <bits/stdc++.h>
using namespace std;

int N;
int s[111];
bool dp[111][11111];

int main() {
   cin >> N;
   for (int i = 0; i < N; i++) {
      cin >> s[i];
   }

   dp[0][0] = true;
   int ans = 0;
   for (int i = 0; i < N; i++) {
      for (int j = 0; j <= 11111; j++) {
         dp[i+1][j] |= dp[i][j];
         if (j >= s[i]) {
            if (dp[i][j-s[i]]) {
               dp[i+1][j] = true;
               if (j % 10 != 0) ans = max(ans, j);
            }
         }
      }
   }

   cout << ans << endl;

   return 0;
}
```

- DPの途中で`ans`を更新している。
- ARCの上位陣の解法を見ると1次元のDPで解いているが、なにやってるのかよくわからない。





## もう1つの解法

- 合計値をあらかじめ求めておく。
- 合計値が10の倍数でなければそれが答え。
- 合計値が10の倍数ならば、そこから1つ引く。その結果が10の倍数でなければそれが答え
- 答えが見つからなければ0になる。

### 疑問

- 確かに見た感じ自明に見えるけど、よくよく考えるとそんなに自明でもなくない？
- 1つ引いたときがほんとに答えなの？2つ引いた時が答えになったりしない？
- $sum-s[i]$をから1つ引いたのが答えになるのか？$s[i]$単体が答えになるかもしれないし、いくつか組み合わせたやつが答えになるかもしれないじゃん
- なんかよくわからん





## 感想

- **想定解法が理解できない。1次元のDPが書けない。**なのでいずれ見直してみる。
- 脳死でDPするの良くない気がするけど確実に求められるので使ってしまった...
- 典型的なDPは少しできるようになってきたかなーといった感じ。





# ABC064 「[Colorful Leaderboard](https://beta.atcoder.jp/contests/abc064/tasks/abc064_c)」

## 解法

- 最小値は、「$max(1,レート3200未満の人の数)$」となる
- 最大値は「$レート3200未満の人の数+レート3200以上の人の数$」となる



## [コード](https://beta.atcoder.jp/contests/abc064/submissions/2423471)

```cpp
#include <bits/stdc++.h>
using namespace std;

int N;
int cnt = 0;
bool flg[10];

int main() {
   fill(flg, flg+10, false);
   cin >> N;
   for (int i = 0; i < N; i++) {
      int a;
      cin >> a;
      bool ok = false;
      for (int i = 1; i <= 8; i++) {
         if (a < 400 * i) {
            ok = true;
            flg[i-1] = true;
            break;
         }
      }
      if (!ok) cnt++;
   }

   int num = count(flg, flg+8, true);
   cout << max(1, num) << " ";
   cout << num + cnt << endl;

   return 0;
}
```



## 感想

- 最小値をレート3200未満の人の数としてしまったため1WAを食らってしまった。全員がレート3200以上である場合を考えていなかった。
- **物事の最小、最大をちゃんと定義するのは結構大事な気がする。**ふんわりと考えるんじゃなくて、抜けがないかとか考えるべきだったなーと。
- コーナーケースの対処もそうだけど、他にもこの考え方を使う機会があった気がする
- コーナーケースの対処法未だによくわかんないんだけど。普通に見落としてしまう。



# ABC065 「[Reconciled?](https://beta.atcoder.jp/contests/abc065/tasks/arc076_a)」

## 考察と解法

- MとNの差が2以上になるとき、指定された並べ方をすることはできない。
- MとNの差が1のとき、`oxoxoxo`といった並べ方しかないため、$M!N!$が答えになる
- MとNが等しいとき、`oxoxox`と`xoxoxo`のように2通りの組み合わせが考えられるので、$2M!N!$が答えとなる。



## [コード](https://beta.atcoder.jp/contests/abc065/submissions/2423477)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long ;

const ll MOD = 1e9+7;
ll N, M;

ll kai(ll x) {
   ll ret = 1;
   while (x > 0) {
      ret = ((ret%MOD) * (x%MOD))%MOD;
      x--;
   }
   return ret;
}

int main() {
   cin >> N >> M;

   if (abs(N-M) >= 2) {
      cout << 0 << endl;
      return 0;
   }

   ll Min = min(N, M), Max = max(N, M);
   if (Min == Max) {
      cout << ((2*kai(Min))%MOD * (kai(Min))%MOD)%MOD << endl;
   } else {
      cout << ((kai(Min)%MOD) * (kai(Max)%MOD))%MOD << endl;
   }


   return 0;
}
```