差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2021/02/17] – [問題] ikatakos | programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2021/02/18] – ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======第6回 ドワンゴからの挑戦状 予選 B, | + | ======第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ====== |
[[https:// | [[https:// | ||
行 309: | 行 309: | ||
==== 問題 ==== | ==== 問題 ==== | ||
+ | * 長さがそれぞれ $L_1, | ||
+ | * この区間を、左端座標が整数になるよう $[0,X)$ からはみ出さないように全て置く | ||
+ | * $[0,X)$ が全て少なくとも1つの区間に覆われるような置き方の個数を $\mod{10^9+7}$ で求めよ | ||
+ | * $1 \le N \le 100$ | ||
+ | * $1 \le L_i \le X \le 500$ | ||
+ | ==== 解法 ==== | ||
- | ==== 例 ==== | + | DPというと「遷移が同じになる状態を上手くまとめて、一気に計算することで計算量を減らす」テクニックだが、 |
+ | この問題は「まさかそこまでまとめてしまっても遷移が同じになるとは」とうならされる。 | ||
+ | まず、まとめられそうなものといえば、複数の区間が重なることで合計長 $l$ の独立した区間が出来た場合、これはまとめて考えられそう。\\ | ||
+ | 「1つ以上の区間が重なってなる、1つの一連の区間」を重区間と呼ぶことにする。 | ||
- | ==== 解法 | + | |------| |
+ | | ||
+ | | ||
+ | ↓ | ||
+ | |===============| | ||
+ | そして、既存の重区間に、区間を1つずつ、重ねたり、ずらしたり、新規に作ったりしていく感じの遷移をイメージする。 | ||
+ | |||
+ | その場合、$L_i$ を大きい順にソートし、この順に置いていくのがよい。\\ | ||
+ | これにより、「既にある重区間の両端からはみ出す」という面倒くさそうな遷移が発生しなくなり、遷移のパターンがぐっと減らせる。 | ||
+ | |||
+ | 既存の重区間が新しい1区間によってどう拡張されるかのパターンは、大まかにこの4通りとなる。 | ||
+ | |||
+ | OLD | ||
+ | |------| | ||
+ | |--------| | ||
+ | OLD | ||
+ | |----| | ||
+ | |--| 独立した1つの重区間となる | ||
+ | |||
+ | そして以下のようなDPを考えるが、当然、計算量的に大きすぎる。 | ||
+ | |||
+ | * (ダメ)$DP[i][S]=L_i$ まで考慮して、重区間の長さの組が $S=\{l_1, | ||
+ | |||
+ | しかし、実はこの $S$ の情報は「合計長と個数」にまとめてしまえる。 | ||
+ | |||
+ | * $DP[i][j][k]=L_i$ まで考慮して、重区間の合計長が $j$、個数が $k$ 個であるような場合の数 | ||
+ | |||
+ | 重区間の合計長と個数さえ同じなら遷移が同じというのは驚き。 | ||
+ | |||
+ | なお、DPの実装における細かな留意点として | ||
+ | |||
+ | * 2つの重区間が隙間を空けずに、たとえば $[2,5)$ と $[5,8)$ が並んでいる場合、これを1つと捉えるか2つと捉えるか | ||
+ | * 重区間の並び順を、DPの段階で反映するか、最後に反映させるか | ||
+ | |||
+ | などの差異があるが、これはどの方針でいくかを決めてしまえば、遷移は変わるもののどちらでも数え上げられる。 | ||
+ | |||
+ | 以下では、隙間を空けない2区間はそのまま2区間、並び順による増加分はDPの段階で反映させるとする。 | ||
+ | |||
+ | == 完全に覆われる場合 == | ||
+ | |||
+ | 長さ $l$ の重区間に、$L_i$ の区間をはみ出ないように置く置き方は $l-L_i+1$ 通り。 | ||
+ | これを長さ $l_1, | ||
+ | |||
+ | * $DP[i][j][k]+=DP[i-1][j][k] \times (j-k(L_i+1))$ | ||
+ | |||
+ | == 独立した新規重区間とする場合 == | ||
+ | |||
+ | 並び順を考慮すると、挿入位置は $k+1$ 個ある。合計長は純粋に $L_i$ 増える。 | ||
+ | |||
+ | * $DP[i][j+L_i][k+1]+=DP[i-1][j][k] \times (k+1)$ | ||
+ | |||
+ | == 左右にはみ出る場合 == | ||
+ | |||
+ | どの重区間からはみ出すかで $k$ 通り、はみ出す方向が2通りある。 | ||
+ | |||
+ | $1~L_i-1$ だけはみ出る余地がある。 | ||
+ | |||
+ | * $DP[i][j+1][k+1]+=DP[i-1][j][k] \times 2k$ | ||
+ | * $DP[i][j+2][k+1]+=DP[i-1][j][k] \times 2k$ | ||
+ | * ... | ||
+ | * $DP[i][j+L_i-1][k+1]+=DP[i-1][j][k] \times 2k$ | ||
+ | |||
+ | == 2つの重区間を繋げる場合 == | ||
+ | |||
+ | $k \ge 2$ の場合に限る。どの2区間を繋げるかで $k-1$ 通り。 | ||
+ | |||
+ | 繋げる2つの重区間の距離がどれだけ開いていたかで $0~L_i-2$ の場合分けがあり、距離 $e$ だけあいていた場合、それが $L_i$ のどこに当たるかで $L_i-e-1$ 通り。 | ||
+ | |||
+ | e=3 | ||
+ | |=====|...|=====| | ||
+ | |-----| | ||
+ | | ||
+ | |-----| | ||
+ | |||
+ | * $DP[i][j+0][k-1]+=DP[i-1][j][k] \times (k-1)(L_i-0-1)$ | ||
+ | * $DP[i][j+1][k-1]+=DP[i-1][j][k] \times (k-1)(L_i-1-1)$ | ||
+ | * ... | ||
+ | * $DP[i][j+L_i-2][k-1]+=DP[i-1][j][k] \times (k-1)(L_i-(L_i-2)-1)$ | ||
+ | |||
+ | === 計算量 === | ||
+ | |||
+ | さて、しかしここまでやっても、雑な見積もりでは状態数が $O(N^2X)$、1回の遷移が $O(L_i)$ で、全体で $O(N^2X^2)$ となってしまう。 | ||
+ | |||
+ | DP[i][j][k] | ||
+ | i: 区間数 | ||
+ | j: 重区間長合計 1~X × Li = O(N^2 X^2) | ||
+ | k: 重区間数 | ||
+ | |||
+ | だめじゃん。 | ||
+ | |||
+ | だが、重区間の個数 $k$ の上限を注意深く考えると、実はそこまで大きくならない。 | ||
+ | |||
+ | たとえば $X=80, | ||
+ | よって、独立した重区間の個数は最大でも8個にしかならず、DPの第3添字 $k$ は $1~8$ の範囲だけ考えればよい。 | ||
+ | |||
+ | より一般化すると、$i$ 番目の区間について考慮するとき、区間数は $k \le \min(i-1, \dfrac{X}{L_i})$ で抑えられるので、全体で $O(NX^2)$ となる。 | ||
+ | |||
+ | より正確な見積もり | ||
+ | DP[i][j][k] | ||
+ | i: 区間数 | ||
+ | j: 重区間長合計 1~X × Li = O(N X^2) | ||
+ | k: 重区間数 | ||
++++ Python3 | | ++++ Python3 | | ||
<sxh python> | <sxh python> | ||
+ | import os | ||
+ | import sys | ||
+ | import numpy as np | ||
+ | |||
+ | np.set_printoptions(linewidth=10000, | ||
+ | |||
+ | |||
+ | def solve(inp): | ||
+ | n = inp[0] | ||
+ | x = inp[1] | ||
+ | lll = np.sort(inp[2: | ||
+ | MOD = 10 ** 9 + 7 | ||
+ | |||
+ | l0 = lll[0] | ||
+ | m_limit = np.searchsorted(lll[: | ||
+ | |||
+ | dp_from = np.zeros((m_limit + 1, x + 1), np.int64) | ||
+ | dp_to = np.zeros_like(dp_from) | ||
+ | |||
+ | dp_from[1, l0] = 1 | ||
+ | |||
+ | for i in range(1, n): | ||
+ | l = lll[i] | ||
+ | dp_to.fill(0) | ||
+ | |||
+ | for m in range(1, min(i, m_limit) + 1): | ||
+ | for k in range(l0, x + 1): | ||
+ | if dp_from[m, k] == 0: | ||
+ | continue | ||
+ | dp_to[m, k] += dp_from[m, k] * (k - m * (l - 1)) % MOD | ||
+ | if k + l <= x: | ||
+ | dp_to[m + 1, k + l] += dp_from[m, k] * (m + 1) % MOD | ||
+ | for e in range(1, min(l - 1, x - k) + 1): | ||
+ | dp_to[m, k + e] += dp_from[m, k] * 2 * m % MOD | ||
+ | if m > 1: | ||
+ | for e in range(min(l - 2, x - k) + 1): | ||
+ | dp_to[m - 1, k + e] += dp_from[m, k] * (m - 1) * (l - e - 1) % MOD | ||
+ | |||
+ | dp_to %= MOD | ||
+ | dp_from, dp_to = dp_to, dp_from | ||
+ | |||
+ | return dp_from[:, x].sum() % MOD | ||
+ | |||
+ | |||
+ | SIGNATURE = ' | ||
+ | if sys.argv[-1] == ' | ||
+ | from numba.pycc import CC | ||
+ | |||
+ | cc = CC(' | ||
+ | cc.export(' | ||
+ | cc.compile() | ||
+ | exit() | ||
+ | |||
+ | if os.name == ' | ||
+ | # noinspection PyUnresolvedReferences | ||
+ | from my_module import solve | ||
+ | else: | ||
+ | from numba import njit | ||
+ | |||
+ | solve = njit(SIGNATURE, | ||
+ | print(' | ||
+ | |||
+ | inp = np.fromstring(sys.stdin.read(), | ||
+ | ans = solve(inp) | ||
+ | print(ans) | ||
</ | </ |