ABC194 振り返りメモ(D問題まで)

#結果
ABCまでの3完で, レート変化は747→<font color="Maroon">738</font>(-9)
なかなか緑になれない...

#[A問題 ( I Scream )](https://atcoder.jp/contests/abc194/tasks/abc194_a)
###概要
> 与えられた条件の通りに実装する

###方針
問題文をよく読んで, その通りに実装する.

C++ での実装例は以下のようになる.

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

int main() {
    int a, b; cin >> a >> b;
    int ans = 0;
    if (a + b >= 15 && b >= 8) ans = 1;
    else if (a + b >= 10 && b >= 3) ans = 2;
    else if (a + b >= 3) ans = 3;
    else ans = 4;
    cout << ans << endl;

} 
```

#[B問題 ( Job Assignment )](https://atcoder.jp/contests/abc194/tasks/abc194_b) 
###概要
> あなたの会社には A, B の2つの仕事があり, 従業員は N 人いる. 従業員 i は仕事 A は A [ i ] 分, 仕事 B は B [ i ] 分でこなすことができる. A, B にそれぞれ1人ずつ従業員を配置するとき, A, B が完了する最小の時間を求める. 

### 方針
N が小さいので, 全部試す.
i と j が異なる場合には, 作業時間は 

```cpp
max(a[i], b[j])
```
となり, i と j が等しいときは, 

```cpp
a[i] + b[j]
```

となる. これをi = 0 ~ n-1, j = 0 ~ n-1 まで全探索すると良い.
B問題は制約が緩く, 素直に全探索をすると解ける問題が多い.
C++ での実装例は以下のようになる.

```cpp:b.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    int ans = 1000000; // 適当な値で初期化
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) ans = min(ans, max(a[i], b[j]));
            else ans = min(ans, a[i]+b[i]);
        }
    }
    cout << ans << endl;
} 
```

#[C問題 ( Squared Error )](https://atcoder.jp/contests/abc194/tasks/abc194_c)
###概要
> 長さ N の数列 A が与えられる. 

>```math
\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2
```
を求める.

### 方針
( 方針1 ) 式変形する
与えられた式は変形すると ( 解説参照 ), 以下のような式になる.

```math
N\sum_{i = 1}^n A_i^2 - (\sum_{i = 1}^n A_i)^2
```
後は, A [ i ] の2乗と A [ i ] の累積和を計算すれば良い.

C++ での実装例は以下のようになる.

```cpp:c.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    // s1はA[i]の累積和, s2はA[i]^2の累積和
    vector<ll> s1(n + 1), s2(n + 1);
    s1[0] = 0, s2[0] = 0;
    for (int i = 1; i <= n; i++) {
        s1[i] = s1[i - 1] + a[i - 1];
        s2[i] = s2[i - 1] + a[i - 1] * a[i - 1];
    }
    cout << n * s2[n] - s1[n] * s1[n] << endl;
}
```

( 方針2 ) | A | <= 200 という制約を利用する.
N の大きさに対して, A は多くても400種類しか出てこないので, 同じ A の値のものをまとめて計算する. cnt という配列を用意し, -200 ~ 200 までの各値が A にそれぞれ何回ずつ登場するかを数える. そして, -200 <= i < j <= 200 という条件のもとで,

```cpp:c.cpp
cnt[i + 200] * cnt[j + 200] * (i - j) * (i - j);
```

を足し合わせて行けば良い. 配列の添字が負の値にならないように, +200 している.

C++ での実装例は以下のようになる.

```cpp:c.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> cnt(405);
    rep(i, n) {
        cnt[a[i]+200]++;
    }
    ll ans = 0;
    for (int i = -200; i <= 200; i++) {
        for (int j = i + 1; j <= 200; j++) {
            ans += cnt[i + 200] * cnt[j + 200] * (i - j) * (i - j);
        }
    }
    cout << ans << endl;

}
```

制約が緩い時は, それを利用する解法を考えると良い.

#[D問題 ( Journey )](https://atcoder.jp/contests/abc194/tasks/abc194_d)
###概要
> 1 種類当たっている状態から, N 種類のものをコンプリートするまでの回数の期待値を求める.

### 方針
期待値に関する重要な事実, 
> 確率 p ( p ≠ 0 ) で成功する試行を成功するまで行うときの試行回数の期待値は 1 / p である.

を利用する.

現在 i 種類コンプリートしている状態であるとすると, i + 1 種類コンプリートするためには, ( N - i ) / N の確率で, 今までに引いたことの無いものを引かなければならず, これが成功するまでの試行回数の期待値は前述の事実より, N / ( N - i ) である. 最初は1種類コンプリートの状態で, 最後 N 種類コンプリートしたら終了なので, 

```math
\frac{N}{N - 1} + \frac{N}{N - 2} + \frac{N}{N - 3} + \dots + \frac{N}{1}
```

を計算すれば良いということになる.
C++ での実装例は以下のようになる.

```c++:d.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    ll n;
    cin >> n;
    double ans = 0.0;
    for (int i = 1; i < n; i++) {
        ans += (double)n / (n - i);
    }
    printf("%.10f\n", ans);
} 
```

上述の事実を知らなくても, 期待値DPの考え方をすれば解ける.
以下のような考え方をする.
![スクリーンショット 2021-03-08 4.54.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/981458/01b123c7-8c95-6ca0-28e0-52810cc9dd10.png)

C++ での実装例は以下のようになる.

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

int main() {
    ll n;
    cin >> n;
    vector<double> dp(n+1,0);
    for (ll i = n-1; i >= 1; i--) {
        dp[i] = dp[i+1] + (double)n / (n - i);
    }
    printf("%.10f\n", dp[1]);
} 
```

後者の解法の方が汎用性がある.
類題： [ABC184-D](https://atcoder.jp/contests/abc184/tasks/abc184_d)