差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0209_yahoo-procon2019-qual [2019/02/11] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0209_yahoo-procon2019-qual [2019/02/11] (現在) – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======Yahoo Programming Contest | + | ======みんなのプロコン |
| [[https:// | [[https:// | ||
| 行 248: | 行 248: | ||
| そして制限を考慮に入れると、$i$ 人目までの赤と青のボールの数を数えておき、 | そして制限を考慮に入れると、$i$ 人目までの赤と青のボールの数を数えておき、 | ||
| - | * 青いボールを置けないなら左端の↓の遷移が無理 | + | * 青いボールの数が足りないなら左端の↓の遷移が無理 |
| - | * 赤いボールを置けないなら右端の↘の遷移が無理 | + | * 赤いボールの数が足りないなら右端の↘の遷移が無理 |
| なので、その遷移を除く。端以外はそれぞれ青、赤のボールがまだ余っているので、端のみ考慮すればよい。 | なので、その遷移を除く。端以外はそれぞれ青、赤のボールがまだ余っているので、端のみ考慮すればよい。 | ||
| 行 264: | 行 264: | ||
| こうして$DP[N][j]$ まで計算すると、「前半の $N$ 個までに赤を $j$ 個置いた場合の並び順の数」が各 $j$ についてわかる。 | こうして$DP[N][j]$ まで計算すると、「前半の $N$ 個までに赤を $j$ 個置いた場合の並び順の数」が各 $j$ についてわかる。 | ||
| - | すると、後半に赤をいくつ、青をいくつ並べればよいかが、$j$ より計算できる。赤の総数を $r$ とすると、残りは$r-j$ となる。 | + | すると、後半に赤をいくつ、青をいくつ並べればよいかが、$j$ より計算できる。赤の総数を $r$ とすると、$r-j$ となる。 |
| - | 後半の並べ方は特に制限は無いので、${}_NC_{r-j}$ となる。 | + | 後半の並べ方は特に制限は無いので、Combinationを用いて |
| 前半と合わせて、$\displaystyle \sum_{j=0}^N(DP[N][j] \times {}_NC_{r-j})$ が答えとなる。 | 前半と合わせて、$\displaystyle \sum_{j=0}^N(DP[N][j] \times {}_NC_{r-j})$ が答えとなる。 | ||
