AtCoder　DPまとめコンテスト　解答

# AtCoder　DPまとめコンテスト　解答

## はじめに

　DP問題解けるようになって舞い上がっちゃった勢いで書いています．現在（2019/01/16）**Rate192の初心者**です．DPに躓いている方も安心してください**灰色コーダーでも1週間頑張って勉強すれば何とかかけるようになりました!!**汚いコードばかりだと思いますのでお気づきになった点をご指導いただけると嬉しいです．

　10問ずつ全３回に分けて書きます．

　DPに苦手意識ある方も頑張ってチャレンジしてみてください．サクッと解けたら本当に楽しいです．

## [A - Frog1](https://atcoder.jp/contests/dp/tasks/dp_a)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N 個の足場があります。 足場には1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hi です。

最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

- 足場 i にいるとき、足場 i+1 または i+2 へジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。

カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください

### 制約

- 入力はすべて整数である。
- 2≤N≤100000
- 1≤hi≤10000

### 入力

入力は以下の形式で標準入力から与えられる。

```
N
h1 h2 …… hN
```

### 出力

カエルが支払うコストの総和の最小値を出力せよ。



　比較的簡単なDP問題です．DPの基本となる考えは全探索の簡略化です．重複している処理を省くことで高速な処理を実現します．深さ優先度探索をベースに組み立てていきましょう．ただ単に深さ優先度探索を実装すると処理の回数は指数のオーダーになるため時間内に答えを算出できません．一度探索した部分の答えを保持しておき，二度目以降は一度目の計算結果を返すことでO(n*n)まで減らすことができます．



**解答例**

```c++
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> h(100000);
vector<int> cost(100000);

int ans(int n)
{
    if (cost.at(n) != -1)
        return cost.at(n);
    cost.at(n) = min(ans(n - 1) + abs(h.at(n) - h.at(n - 1)),
                     ans(n - 2) + abs(h.at(n) - h.at(n - 2)));
    return cost.at(n);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
        cost.at(i) = -1;
    }
    cost.at(0) = 0;
    cost.at(1) = abs(h.at(1) - h.at(0));
    cout << ans(n - 1) << endl;
}
```

　インデックスエラーの対策を関数内に記述することが多いかと思いますが，私は初期値を用意することでインデックスエラーを回避しました．番兵法に似た考え方です．エラーの可能性をなくすことでif文を減らしています．

　c++で関数に値を渡す方法を覚えていないので変数をグローバルにすることで実装しました．競技ならこれでいいと思います．書くの楽ですし(笑)

　costにはそこにたどり着くまでに必要となるコストの最小値を保存します．n-1番目とn-2番目にたどり着くまでの最小コストが分かっていると仮定すると，n番目の最小コストは「n-1番目の最小コスト＋１移動するコスト」と「n-2番目の最小コスト＋２移動するコスト」の小さい方になります．この考え方で再帰的に定義すると，初期値が2つ（0番目と1番目）あれば，漸化的に全ての値を決定することができます．

　costをすべて-1で初期化しておくとすでにコストを計算した部分とまだ計算していない部分の判別がつきます．



## [B - Frog2](https://atcoder.jp/contests/dp/tasks/dp_b)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N 個の足場があります。 足場には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、足場 i の高さは hiです。

最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。

- 足場 i にいるとき、足場 i+1,i+2,…,i+Ki+1,i+2,…,i+K のどれかへジャンプする。 このとき、ジャンプ先の足場を j とすると、コスト |hi−hj||hi−hj| を支払う。

カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

### 制約

- 入力はすべて整数である。
- 2≤N≤100000
- 1≤K≤100
- 1≤hi≤10000

### 入力

入力は以下の形式で標準入力から与えられる。

```
N K
h1 h2 …… hN
```

### 出力

カエルが支払うコストの総和の最小値を出力せよ。



　Frog1よりカエルのジャンプ力が強くなりました．それ以外には大きな変化はありませんので同じようにDPを組んでいきましょう．

**解答例**

```c++
#include <iostream>
#include <vector>
using namespace std;
int n;
int k;
vector<int> h(100000);
vector<int> cost(100000);

int ans(int n, int k)
{
    if (cost.at(n) != -1)
        return cost.at(n);
    cost.at(n) = ans(n - 1, k) + abs(h.at(n) - h.at(n - 1));

    for (int i = 2; i <= k; i++)
    {
        cost.at(n) = min(cost.at(n), ans(n - i, k) + abs(h.at(n) - h.at(n - i)));
    }

    return cost.at(n);
}

void init(int k)
{
    cost.at(0) = 0;
    for (int i = 1; i < k; i++)
    {
        cost.at(i) = cost.at(i - 1) + abs(h.at(i) - h.at(i - 1));
        for (int j = 2; j <= i; j++)
        {
            cost.at(i) = min(cost.at(i), cost.at(i - j) + abs(h.at(i) - h.at(i - j)));
        }
    }
}

int main()
{
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h.at(i);
        cost.at(i) = -1;
    }
    init(k);
    cout << ans(n - 1, k) << endl;
}
```

　初期値がｋ個必要になるのでinit関数で初期化を定義しました．



## [C - Vacation](https://atcoder.jp/contests/dp/tasks/dp_c)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。

夏休みは N 日からなります。 各 i (1≤i≤N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。

- A: 海で泳ぐ。 幸福度 ai を得る。
- B: 山で虫取りをする。 幸福度 bi を得る。
- C: 家で宿題をする。 幸福度 ci を得る。

太郎君は飽き性なので、2 日以上連続で同じ活動を行うことはできません。

太郎君が得る幸福度の総和の最大値を求めてください。

### 制約

- 入力はすべて整数である。
- 1≤N≤100000
- 1≤ai,bi,ci≤10000

### 入力

入力は以下の形式で標準入力から与えられる。

```
N
a1 b1 c1
a2 b2 c2
:
aN bN cN
```

### 出力

太郎君が得る幸福度の総和の最大値を出力せよ。



　先ほどまでの問題と比べて少し難易度が上がります．数学でいう連立漸化式に落とし込みます．この問題で難しい点は２連続で同じものを選択できないことです．いきなりn番目の最大幸福度を求めようとすると難しそうです．

　そこで，n番目の選択肢を決めてしまいます．すると，n-1番目にとれる選択肢が決まり簡単に実装できます．うまく説明できる自信がないのでコードを見てください．

**解答例**

```c++
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a(100000);
vector<int> b(100000);
vector<int> c(100000);
vector<int> ha(100000);
vector<int> hb(100000);
vector<int> hc(100000);

int ans_a(int n);
int ans_b(int n);
int ans_c(int n);

int ans_a(int n)
{
    if (ha.at(n) != -1)
        return ha.at(n);
    ha.at(n) = max(ans_b(n - 1) + a.at(n), ans_c(n - 1) + a.at(n));
    return ha.at(n);
}

int ans_b(int n)
{
    if (hb.at(n) != -1)
        return hb.at(n);
    hb.at(n) = max(ans_a(n - 1) + b.at(n), ans_c(n - 1) + b.at(n));
    return hb.at(n);
}

int ans_c(int n)
{
    if (hc.at(n) != -1)
        return hc.at(n);
    hc.at(n) = max(ans_a(n - 1) + c.at(n), ans_b(n - 1) + c.at(n));
    return hc.at(n);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i) >> b.at(i) >> c.at(i);
        ha.at(i) = -1;
        hb.at(i) = -1;
        hc.at(i) = -1;
    }
    ha.at(0) = a.at(0);
    hb.at(0) = b.at(0);
    hc.at(0) = c.at(0);
    cout << max(ans_a(n - 1), max(ans_b(n - 1), ans_c(n - 1))) << endl;
}
```

　関数プロトタイプ宣言初めて使いました(笑)この機能役立つときあるんですね．

　ans_aではn番目にaを選んだ時の最大幸福度を計算します．ans_b, ans_cはそれぞれb, cを選んだ時の最大幸福度です．後はそれらを組み合わせて再帰的に定義したら完了です．

　出力はn番目にaを選ぶとき，bを選ぶとき，cを選ぶときの内最大のものです．



## [D - Knapsack1](https://atcoder.jp/contests/dp/tasks/dp_d)

### 問題文

N 個の品物があります。 品物には 1,2,…,Nと番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi で、価値は vi です。

太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

### 制約

- 入力はすべて整数である。
- 1≤N≤100
- 1≤W≤100000
- 1≤wi≤W
- 1≤vi≤1000000000

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
N W
w1 v1
w2 v2
:
wN vN
```

### 出力

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。



　タイトルの通りナップサック問題です．記録用の配列をうまく作ることがコツです．

**解答例**

```c++
#include <iostream>
using namespace std;
int n;
int max_weight;
int w[101];
long long int v[101];
long long int dp[101][100001];
long long int ans = 0;
int main()
{
    cin >> n >> max_weight;
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= max_weight; j++)
        {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (j + w[i] <= max_weight)
                dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }
    for (int i = 0; i <= max_weight; i++)
    {
        if (dp[n][i] >= ans)
            ans = dp[n][i];
    }
    cout << ans << endl;
}
```

　二次元のベクトルの書き方が分からなかったので配列で書きました．

　ナップサック問題では配列の作り方が大切になります．行，列，値を用いて品物，価格，重さを記録します．この対応はどれでも実装可能ですので，配列がなるべく小さくなるように選びます．今回は行を品物，列を重さにしました．この時の配列の値は重さに対する価格なので衝突した場合には高い方を記録しましょう．

　後はN番目の商品を入れたときと入れなかった時とで場合分けして配列に情報を突っ込めば完成です．関係ないところにも情報を書き込んでしまいますが，そこは最適解にならないので問題ありません．



## [E - Knapsack2](https://atcoder.jp/contests/dp/tasks/dp_e)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N 個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi で、価値は vi です。

太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W であり、持ち帰る品物の重さの総和は W 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

### 制約

- 入力はすべて整数である。
- 1≤N≤100
- 1≤W≤1000000000
- 1≤wi≤W
- 1≤vi≤1000

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
N W
w1 v1
w2 v2
:
wN vN
```

### 出力

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。

**解答例**

```c++
#include <iostream>
using namespace std;

int n;
long long int max_w;
long long int w[101];
int v[101];
long long int dp[101][100001];
int main()
{
    cin >> n >> max_w;
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
    }
    for (int i = 0; i < 101; i++)
    {
        for (int j = 0; j < 100001; j++)
        {
            dp[i][j] = 1000000001;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= 1000 * i + 1000; j++)
        {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            if (j + v[i] <= 100000)
            {
                dp[i + 1][j + v[i]] = min(dp[i + 1][j + v[i]], dp[i][j] + w[i]);
            }
        }
    }
    for (int i = 100000; i >= 0; i--)
    {
        if (dp[n][i] <= max_w)
        {
            cout << i << endl;
            break;
        }
    }
}
```

　この問題では配列の添え字をV，値をWとしました．この時，配列の値は価格に対する重さなので衝突した場合には低い方を記録しましょう．



## [F - LCS](https://atcoder.jp/contests/dp/tasks/dp_f)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。

### 注釈

文字列 x の*部分列*とは、x から 0 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。

### 制約

- s および t は英小文字からなる文字列である。
- 1≤|s|,|t|≤3000

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
s
t
```

### 出力

s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。



　これはうまく問題の入れ子構造を作れるかがカギになります．いきなり求めるのではなく，1つ文字が少ない状態の最長部分列から求めることができないかを考えます．これは結構場合分けが多いです．

　まず追加した文字が等しいか等しくないかで場合分け，等しくないときにはｔに一文字追加したときの最長部分列とsに一文字追加したときの最長部分列の内長い方を選択，等しい時にはこれに加えて元の最長部分列＋追加した文字の場合分けが入ります．dpテーブルには文字列を記録しましょう．そして，比較には文字列の長さを使います．ではコードを見ていきましょう

**解答例**

```c++
#include <iostream>
#include <string>
using namespace std;

int Ls, Lt;
string s, t;

string dp[3001][3001];

int main()
{
    cin >> s >> t;
    Ls = s.size();
    Lt = t.size();

    for (int i = Ls - 1; i >= 0; --i)
    {
        for (int j = Lt - 1; j >= 0; --j)
        {
            if (s[i] == t[j])
            {
                if (dp[i + 1][j + 1].size() + 1 > dp[i + 1][j].size())
                {
                    if (dp[i + 1][j + 1].size() + 1 > dp[i][j + 1].size())
                        dp[i][j] = s[i] + dp[i + 1][j + 1];
                    else
                        dp[i][j] = dp[i][j + 1];
                }
                else if (dp[i + 1][j].size() > dp[i][j + 1].size())
                    dp[i][j] = dp[i + 1][j];
                else
                    dp[i][j] = dp[i][j + 1];
            }
            else
            { 
                if (dp[i + 1][j].size() > dp[i][j + 1].size())
                    dp[i][j] = dp[i + 1][j];
                else
                    dp[i][j] = dp[i][j + 1];
            }
        }
    }
    cout << dp[0][0] << endl;

    return 0;
}
```

コーディングが雑すぎてごめんなさい

ifのネストが深すぎる．．．共同開発でやったり引継ぎ資料に残したりしたらTwitterで愚痴られるやつだわ

　ネットで検索をかけると長さを求めるアルゴリズムが出てきたので文字列を保存できるように拡張したらこうなりました．．．

きっともっと良い解法があるはずです．



## [G - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N 頂点 M 辺の有向グラフ G があります。 頂点には 1,2,…,N と番号が振られています。 各 i (1≤i≤M) について、i 番目の有向辺は頂点 xi から yi へ張られています。 G は**有向閉路を含みません**。

G の有向パスのうち、最長のものの長さを求めてください。 ただし、有向パスの長さとは、有向パスに含まれる辺の本数のことです。

### 制約

- 入力はすべて整数である。
- 2≤N≤100000
- 1≤M≤100000
- 1≤xi,yi≤N
- ペア (xi,yi) はすべて相異なる。
- G は**有向閉路を含まない**。

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
N M
x1 y1
x2 y2
:
xM yM
```

### 出力

Gの有向パスのうち、最長のものの長さを出力せよ。



　これは意外と単純な問題です．スタート地点が分かれば深さ優先度探索をDPすることでそのスタート地点からとれる最長パスが求まります．後はスタート地点を全部試して最も長いものを返すだけです．入力を受け取る際にベクトルをうまく用いて，任意のノードからの有向パスにO(1)でアクセスできるようにしましょう．



**解答例**

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

vector<int> v[100010];
bool vis[100010];
int ans, n, m, dist[100010];

int dfs(int u)
{
    vis[u] = 1;
    int sum = 1, maxv = 0;
    for (int i = 0; i < v[u].size(); i++)
    {
        int val;
        if (dist[v[u][i]] == 0)
            val = dfs(v[u][i]);
        else
            val = dist[v[u][i]];
        maxv = max(maxv, val);
    }
    sum += maxv;
    dist[u] = sum;
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            ans = max(ans, dfs(i));
        }
    }
    cout << ans - 1 << endl;
    return 0;
}
```

今回は友人のアドバイスで「ios::sync_with_stdio(false);」を使ってみました．入力がめちゃめちゃ速くなりました．

![キャプチャ.PNG](https://qiita-image-store.s3.amazonaws.com/0/327279/04e53a54-5f63-a918-4b38-22da37b36c1a.png)


こんなにも違いが!!!

入力が多い時には積極的に使っていきましょう．私は何も考えずにとりあえず書いています(笑)こういうところが灰色コーダー



## [H - Grid1](https://atcoder.jp/contests/dp/tasks/dp_h)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

縦 H 行、横 W 列のグリッドがあります。 上から i 行目、左から j 列目のマスを (i,j) で表します。

各 i,j (1≤i≤H, 1≤j≤W) について、マス (i,j) の情報が文字 ai,j によって与えられます。 ai,j が `.` ならばマス (i,j)は空マスであり、ai,j が `#` ならばマス (i,j) は壁のマスです。 マス (1,1)および (H,W) は空マスであることが保証されています。

太郎君は、マス (1,1) から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス (H,W) まで辿り着こうとしています。

マス (1,1) から (H,W) までの太郎君の経路は何通りでしょうか？ 答えは非常に大きくなりうるので、1000000000+7 で割った余りを求めてください。

### 制約

- H および W は整数である。
- 2≤H,W≤1000
- ai,j は `.` または `#` である。
- マス (1,1) および (H,W) は空マスである。

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
H W
a1,1……a1,W
:
aH,1……aH,W
```

### 出力

マス (1,1) から (H,W) までの太郎君の経路は何通りか？ 1000000000+7 で割った余りを出力せよ。



スタート地点から順に求めれば簡単に求まります，ある地点（i,j）に到達するには上から来るか，左から来るかの二択です．両方から来る経路数の和をとってやることで求まります．ポイントは和をとった時点であまりの計算もすることです．最後にあまりをとろうとするとそれまでに桁あふれが起きてしまします．



**解答例**

```c++
#include <bits/stdc++.h>
using namespace std;
int height, width;
long long int dp[1010][1010];
string a[1001];
int main()
{
    ios::sync_with_stdio(false);
    cin >> height >> width;
    for (int i = 0; i < height; i++)
        cin >> a[i];
    dp[0][0] = 1;
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            if (a[i][j] == '#')
                continue;
            if (a[i][j + 1] == '.')
            {
                dp[i][j + 1] += dp[i][j];
                dp[i][j + 1] %= 1000000007;
            }
            if (a[i + 1][j] == '.')
            {
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][j] %= 1000000007;
            }
        }
    }
    cout << dp[height - 1][width - 1] % (1000000007) << endl;
}
```





## [I - Coins](https://atcoder.jp/contests/dp/tasks/dp_i)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N を正の奇数とします。

N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、コイン i を投げると、確率 pi で表が出て、確率 1−pi で裏が出ます。

太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。

### 制約

- N は奇数である。
- 1≤N≤2999
- pi は実数であり、小数第 2 位まで与えられる。
- 0<pi<1

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
N
p1 p2 …… pN
```

### 出力

表の個数が裏の個数を上回る確率を出力せよ。 絶対誤差が 10^−9 以下ならば正解となる。



　これも簡単な問題から帰納的に定義することを考えます．コインの枚数が１枚少ない時の確率分布が分かっている場合はどうでしょう？例えばコインが1枚の時に表が０枚の確率は1/2, １枚の確率は1/2，コインが2枚の時にはそれを用いて0枚の確率 = 1/2 * 1/2，　1枚の確率 = 1/2 * 1/2 + 1/2 * 1/2, 　2枚の確率 = 1/2 * 1/2　と計算できます．これをnまで繰り返せば確率分布を求めることができます．



**解答例**

```c++
#include <bits/stdc++.h>
using namespace std;
int n;
double dp[3000][3000];
double p[2999];
double ans = 0;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i];
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }
    for (int i = n; i > n / 2; i--)
        ans += dp[n][i];

    printf("%.10lf\n", ans);
}
```

　この問題のみそは少数以下10桁表示するところですかね．C++の書き方が分からなかったのでCで代用しました．互換あるのって便利だなぁ．



## [J - Sushi](https://atcoder.jp/contests/dp/tasks/dp_j)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

### 問題文

N 枚の皿があります。 皿には 1,2,…,Nと番号が振られています。 最初、各 i (1≤i≤N) について、皿 i には ai(1≤ai≤3) 個の寿司が置かれています。

すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。

- 1,2,…,Nの目が等確率で出るサイコロを振り、出目を i とする。 皿 i に寿司がある場合、皿 i の寿司を 1 個食べる。 皿 i に寿司が無い場合、何も行わない。

すべての寿司が無くなるまでの操作回数の期待値を求めてください。

### 制約

- 入力はすべて整数である。
- 1≤N≤300
- 1≤ai≤3

------

### 入力

入力は以下の形式で標準入力から与えられる。

```
N
a1 a2 …… aN
```

### 出力

すべての寿司が無くなるまでの操作回数の期待値を出力せよ。 相対誤差が 10^-9以下ならば正解となる。



　これは深さ優先度探索で答えから逆算しましょう．状態の遷移をそのまま記述してやることで計算が可能です．と言いながら私は2時間悩んだ末諦めました．そのためこのコードだけはきれいです．

**解答例**

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

double dp[303][303][303];
int n;

void calc(int i, int j, int k)
{
    if (dp[i][j][k] >= 0)
        return;
    if (i)
        calc(i - 1, j, k);
    if (j)
        calc(i + 1, j - 1, k);
    if (k)
        calc(i, j + 1, k - 1);

    dp[i][j][k] = (i ? dp[i - 1][j][k] * i : 0) + (j ? dp[i + 1][j - 1][k] * j : 0) +
                  (k ? dp[i][j + 1][k - 1] * k : 0) + n;
    dp[i][j][k] *= 1.0 / (i + j + k);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    vector<int> cnt(5);
    int a;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        cnt[a]++;
    }

    memset(dp, -1, sizeof dp);
    dp[0][0][0] = 0.0;
    calc(cnt[1], cnt[2], cnt[3]);
    printf("%.10lf\n", dp[cnt[1]][cnt[2]][cnt[3]]);

    return 0;
}
```

ポイントは順序に意味がないことです．寿司の数だけに注目して数え上げましょう．





## 終わりに

灰色コーダーには全部書き上げる体力がありません，続きはまたいつか投稿します．いつかもっと強い競プロerになりたいので役立つ知識を教えていただけると嬉しいです！