ABC-C第17弾

<img width="873" alt="result.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/b1d313b5-225f-51ef-ce0d-a1c57555ce84.png">




- [ABC-C第17弾](https://not-522.appspot.com/contest/5967154167939072)




# ABC081 「[C - Not so Diverse](https://beta.atcoder.jp/contests/abc081/tasks/arc086_a)」

## 考察と解法

- 個数の少ない種類のボールを取り除く方法が得する。
- 取り除く種類数は$max(0, 入力の種類数-K)$個となる。

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

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

int main() {
   int N, K;
   cin >> N >> K;
   map<int, int> mp;
   while (N--) {
      int a;
      cin >> a;
      mp[a]++;
   }
   vector<int> v;
   for (auto x : mp) {
      v.push_back(x.second);
   }
   sort(v.begin(), v.end());

   int cnt = max(0, (int)mp.size()-K); // 種類の個数
   cout << accumulate(v.begin(), v.begin()+cnt, 0) << endl;

   return 0;
}
```

- [accumulate使わない実装](https://beta.atcoder.jp/contests/abc081/submissions/2510964) 



### accumulate関数

- 上位陣はこの関数使ってたので僕も使ってみた。
- `accumulate(最初のイテレータ, 最後のイテレータ, 初期値)`といった使い方をするとその範囲の値の和を返してくれる。`count()`と同じような使い方
- 和だけでなく、積とかも計算できたりする
- 初期値の型には気を付ける。オーバーフローとか、浮動小数点数とか。今回も`0LL`とかで初期化した方が安全だったかもしれない
- 公式リファレンス以外に[このブログ](http://d.hatena.ne.jp/formula_cpp/20081205/1228506506)が分かりやすかった。



## 感想

- 適当な実装してWA出してしまった
- `accumulate`関数、便利だな...コーディング量が減って楽できる。



# ABC082 「[Good Sequence](https://beta.atcoder.jp/contests/abc082/tasks/arc087_a) 」

## 考察と解法

- 数aがb個あるとする。
- $a<b$なら$b-a$個取り除く必要がある
- $a>b$ならb個すべてを取り除く必要がある



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

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

using ll = long long;

int main() {
   int N;
   cin >> N;
   map<ll, ll> mp;
   while (N--) {
      ll a;
      cin >> a;
      mp[a]++;
   }

   ll ans = 0;
   for (auto x : mp) {
      if (x.first <= x.second) {
         ans += x.second - x.first;
      } else {
         ans += x.second;
      }
   }
   cout << ans << endl;

   return 0;
}
```



## 感想

- 4が2個あるとき、どう頑張っても4を4個にできない。なので、2個取り除いて4を消し去るという発想を出すのが遅れた。



# ABC083 「[Multiple Gift](https://beta.atcoder.jp/contests/abc083/tasks/arc088_a) 」

## 考察と解法

- $A_i < A_{i+1}$かつ$A_{i+1} = nA_{i}$になるようにする。数列を長くするためには$A_{i+1}$ができるだけ小さくなるようにしたい。$n=2$のときがこの条件を満たす最小の値となる。よって、毎回2倍していくのが最適解となる。

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

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

using ll = long long;

int main() {
   ll X, Y;
   cin >> X >> Y;
   ll ans = 0;
   while (X <= Y) {
      ans++;
      X*=2;
   }
   cout << ans << endl;

   return 0;
}
```

- 僕は[こんなコード](https://beta.atcoder.jp/contests/abc083/submissions/2511153)を書いちゃったわけだがwhileで書いた方が楽そう



# ABC084 「[Special Trains](https://beta.atcoder.jp/contests/abc084/tasks/abc084_c) 」

## 考察と解法

<img width="144" alt="a.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/1c5a8cab-9533-1455-536b-97fcc94732d9.png">


- 問題文を要約すると、上の図のように各駅から目的地までの最短時間を求めたい。
- 全体像が分かったところで、部分的なところを考える。
- 駅$j$→$j+1$の最短移動時間が分かればよさそう。
- 駅$j$→$j+1$の移動時間は「駅$j$を出発する時刻 + 駅$j+1$へ移動する時間」となる。
- 駅$j$を出発する時刻は、$S[j]+F[j] \times k$となる($k$は適当な整数)。出発する時刻は現在時刻$t$以上である必要があるので、$S[j]+F[j] \times k \geq t$とする。$k$が何になるかを求めたいので、$k \geq \frac{t-S[j]}{F[j]}$という式に変形する。$k$は右辺を切り上げた数値となるので、$k=\frac{(t-S[j]+F[j]-1)}{F[j]}$となる。$k$はマイナスの値になる場合もあるので、その時は$k=0$にする。
- 駅$j+1$へ移動する時間は$C[j]$である
- 以上から、駅$j→j+1$の移動時間は$S[j]+F[j]\times k + C[j]$で、$k=max(0,\frac{(t-S[j]+F[j]-1)}{F[j]})$となる。



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

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

int N;
int C[555], S[555], F[555];

int main() {
   cin >> N;
   for (int i = 0; i < N-1; i++) {
      cin >> C[i] >> S[i] >> F[i];
   }

   for (int i = 0; i < N; i++) { // 駅iを始点とする
      int t = 0; // 現在時刻
      for (int j = i; j < N-1; j++) {
         // 駅jから駅j+1までにかかる時間を計算
         int k = max(0, (t - S[j] + F[j] - 1) / F[j]);
         t = S[j] + F[j]*k + C[j];
      }
      cout << t << endl;
   }

   return 0;
}
```
- 一応$k$をループで求めてもACできる。[コード](https://beta.atcoder.jp/contests/abc084/submissions/2520397) 
- $k$を求める計算量がどれだけになるかはよくわかんないけど、数学を使えばループ処理を$O(1)$にできるってすごい不思議。なんで$O(1)$になったの！？！？！？って感じがする。数学しゅごい...


## 感想

- この問題、問題文を読み取るのがまず難しい。コンテスト中(バチャじゃない)は問題文を何回も読み直した記憶。結局解けなかったんだけど。
- **問題文から式を作る**っていう発想と**式を変形して求めたい数値を計算する**という発想が必要だった。この発想コンテスト中になかなか思いつかない...
- この問題は「駅$j$→$j+1$の移動時間」が何になるかを求めればOKということが分かればコンテスト中に解けたのかも。何を重点的に考えるか？本質を見極めたい。
- 解説見てもわからなかった問題がわかったのでまあ良しとしよう...



# ABC085 「[Otoshidama](https://beta.atcoder.jp/contests/abc085/tasks/abc085_c) 」

## 考察と解法

- 10000円札をa枚、5000円札をb枚、1000円札をc枚とすると以下の2つの式が作れる
  - $a+b+c=N$
  - $10000a+5000b+1000c=Y$
- a, b, cを全探索すれば答えが求まるが、TLEになってしまう。そこで、式変形して$c=N-a-b$にすることで計算量を1つ落とす



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

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

using ll = long long;

int main() {
   int N, Y;
   cin >> N >> Y;

   for (int a = 0; a <= 2000; a++) {
      for (int b = 0; b <= 2000; b++) {
         int c = N - a - b;
         int sum = 10000*a + 5000*b + 1000*c;
         if (c >= 0 && c <= N && sum == Y) {
            printf("%d %d %d\n", a, b, c)
            return 0;
         }
      }
   }
   printf("%d %d %d\n", -1, -1, -1);

   return 0;
}
```