差分

このページの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,D問題メモ======
+======第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ======
 [[https://atcoder.jp/contests/dwacon6th-prelims|Dwango Programming Contest 6th]]
@@ 行 179: / 行 179: @@
   * $1～N$ の順列 $p_1,p_2,...,p_N$ であって、以下の条件を満たすもののうち辞書順最小のものを求めよ
   * 条件
-    * $i$ の右側に $a_i$ が来てはいけない
+    * $i=1～N$ について、$i$ の右側に $a_i$ が来てはいけない
   * 存在しない場合は ''-1'' を答えよ
   * $2 \le N \le 10^5$
@@ 行 309: / 行 309: @@
 ==== 問題 ====
+  * 長さがそれぞれ $L_1,L_2,...,L_N$ の $N$ 個のシートがある
+  * このシートを、両端の座標が整数になるよう区間 $[0,X)$ からはみ出さないように全て置く
+  * $[0,X)$ の中でシートに覆われていない箇所が無いような置き方の個数を $\mod{10^9+7}$ で求めよ
+  * $1 \le N \le 100$
+  * $1 \le L_i \le X \le 500$
+==== 解法 ====
-==== 例 ====
+DPというと「遷移が同じになる状態を上手くまとめて、一気に計算することで計算量を減らす」テクニックだが、
+この問題は「まさかそこまでまとめられるとは」と唸らされる。
+まず、まとめられそうなものといえば、複数のシートが重なることで合計長 $l$ の区間が出来た場合、具体的な中身の位置は気にせずまとめて考えられそう。\\
+「1つ以上のシートが重なってなる、1つの一連の区間」を重区間と呼ぶことにする。
-==== 解法 ====
+  |------|  |-----|
+     |--------|
+         |------|
+         ↓
+  |===============|  重区間
+そして、DPで、既存の重区間にシートを1つずつ、重ねたり、ずらしたり、新規に作ったりしていく感じの遷移をイメージする。
+その場合、$L_i$ を大きい順にソートし、この順に置いていくのがよい。\\
+これにより、「既にある重区間の両端からはみ出す」「3つ以上の重区間が併合される」という面倒くさそうな遷移が発生しなくなり、遷移のパターンがぐっと減らせる。
+既存の重区間が新しい1シートによってどう拡張されるかのパターンは、大まかにこの4通りとなる。
+  OLD     |============|
+              |------|          完全に覆われる
+        |--------|              左右からはみ出る
+  OLD     |=====| |=====|
+              |----|            2つの重区間を繋ぐ
+                          |--|  独立した1つの重区間となる
+そして以下のようなDPを考えるが、当然、計算量的に大きすぎる。
+  * （ダメ）$DP[i][S]=L_i$ まで考慮して、重区間の長さの組が $S=\{l_1,l_2,...\}$ であるような場合の数
+しかし、実はこの $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,l_2,...,l_k$ の重区間について合計すると、$j-k(L_i-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
+  |=====|...|=====|
+      |-----|        Li=7
+       |-----|
+        |-----|
+  * $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]                 1回の遷移
+  i: 区間数       1～N
+  j: 重区間長合計 1～X    ×    Li    =    O(N^2 X^2)
+  k: 重区間数     1～N        (最大X)
+だめじゃん。
+だが、重区間の個数 $k$ の上限を注意深く考えると、実はそこまで大きくならない。
+たとえば $X=80,L_{30}=10$ のような状況の時、あり得る重区間の個数は何個か？と考えると、それより前の29個の区間は（大きい方から処理してるので）長さ $10$ 以上である。
+よって、独立した重区間の個数は最大でも8個にしかならず、DPの第3添字 $k$ は $1～8$ の範囲だけ考えればよい。
+より一般化すると、$i$ 番目の区間について考慮するとき、区間数は $k \le \dfrac{X}{L_i}$ で抑えられるので、全体で $O(NX^2)$ となる。
+  より正確な見積もり
+  DP[i][j][k]                 1回の遷移
+  i: 区間数       1～N
+  j: 重区間長合計 1～X    ×    Li    =    O(N X^2)
+  k: 重区間数     1～X/Li
 ++++ Python3 |
 <sxh python>
+import os
+import sys
+import numpy as np
+np.set_printoptions(linewidth=10000, edgeitems=30)
+def solve(inp):
+    n = inp[0]
+    x = inp[1]
+    lll = np.sort(inp[2:])[::-1]
+    MOD = 10 ** 9 + 7
+    l0 = lll[0]
+    m_limit = np.searchsorted(lll[:0:-1].cumsum(), x - l0, side='right') + 1
+    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 = '(i8[:],)'
+if sys.argv[-1] == 'ONLINE_JUDGE':
+    from numba.pycc import CC
+    cc = CC('my_module')
+    cc.export('solve', SIGNATURE)(solve)
+    cc.compile()
+    exit()
+if os.name == 'posix':
+    # noinspection PyUnresolvedReferences
+    from my_module import solve
+else:
+    from numba import njit
+    solve = njit(SIGNATURE, cache=True)(solve)
+    print('compiled', file=sys.stderr)
+inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
+ans = solve(inp)
+print(ans)
 </sxh>