差分
このページの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:// | ||
行 179: | 行 179: | ||
* 1~N の順列 p1,p2,...,pN であって、以下の条件を満たすもののうち辞書順最小のものを求めよ | * 1~N の順列 p1,p2,...,pN であって、以下の条件を満たすもののうち辞書順最小のものを求めよ | ||
* 条件 | * 条件 | ||
- | * i の右側に ai が来てはいけない | + | * i=1~N について、i の右側に ai が来てはいけない |
* 存在しない場合は '' | * 存在しない場合は '' | ||
* 2≤N≤105 | * 2≤N≤105 | ||
行 309: | 行 309: | ||
==== 問題 ==== | ==== 問題 ==== | ||
+ | * 長さがそれぞれ L1,L2,...,LN の N 個のシートがある | ||
+ | * このシートを、両端の座標が整数になるよう区間 [0,X) からはみ出さないように全て置く | ||
+ | * [0,X) の中でシートに覆われていない箇所が無いような置き方の個数を mod109+7 で求めよ | ||
+ | * 1≤N≤100 | ||
+ | * 1≤Li≤X≤500 | ||
+ | ==== 解法 ==== | ||
- | ==== 例 ==== | + | DPというと「遷移が同じになる状態を上手くまとめて、一気に計算することで計算量を減らす」テクニックだが、 |
+ | この問題は「まさかそこまでまとめられるとは」と唸らされる。 | ||
+ | まず、まとめられそうなものといえば、複数のシートが重なることで合計長 l の区間が出来た場合、具体的な中身の位置は気にせずまとめて考えられそう。\\ | ||
+ | 「1つ以上のシートが重なってなる、1つの一連の区間」を重区間と呼ぶことにする。 | ||
- | ==== 解法 | + | |------| |
+ | | ||
+ | | ||
+ | ↓ | ||
+ | |===============| | ||
+ | そして、DPで、既存の重区間にシートを1つずつ、重ねたり、ずらしたり、新規に作ったりしていく感じの遷移をイメージする。 | ||
+ | |||
+ | その場合、Li を大きい順にソートし、この順に置いていくのがよい。\\ | ||
+ | これにより、「既にある重区間の両端からはみ出す」「3つ以上の重区間が併合される」という面倒くさそうな遷移が発生しなくなり、遷移のパターンがぐっと減らせる。 | ||
+ | |||
+ | 既存の重区間が新しい1シートによってどう拡張されるかのパターンは、大まかにこの4通りとなる。 | ||
+ | |||
+ | OLD | ||
+ | |------| | ||
+ | |--------| | ||
+ | OLD | ||
+ | |----| | ||
+ | |--| 独立した1つの重区間となる | ||
+ | |||
+ | そして以下のようなDPを考えるが、当然、計算量的に大きすぎる。 | ||
+ | |||
+ | * (ダメ)DP[i][S]=Li まで考慮して、重区間の長さの組が S={l1,l2,...} であるような場合の数 | ||
+ | |||
+ | しかし、実はこの S の情報は「合計長と個数」にまとめてしまえる。 | ||
+ | |||
+ | * DP[i][j][k]=Li まで考慮して、重区間の合計長が j、個数が k 個であるような場合の数 | ||
+ | |||
+ | 重区間の合計長と個数さえ同じなら遷移が同じというのは驚き。\\ | ||
+ | 以下、各パターンの遷移を見ていく。 | ||
+ | |||
+ | なお、DPの実装における細かな留意点として | ||
+ | |||
+ | * 2つの重区間が隙間を空けずに、たとえば [2,5) と [5,8) が並んでいる場合、これを1つと捉えるか2つと捉えるか | ||
+ | * 重区間の並び順による増加分を、DPの段階で反映するか、最後に反映させるか | ||
+ | |||
+ | などの差異があるが、これはどの方針でいくかを決めてしまえば、遷移は変わるもののどちらでも数え上げられる。 | ||
+ | |||
+ | 以下では、隙間を空けない2区間はそのまま2区間、並び順による増加分はDPの段階で反映させるとする。 | ||
+ | |||
+ | == 完全に覆われる場合 == | ||
+ | |||
+ | 長さ l の重区間に、Li の区間をはみ出ないように置く置き方は l−Li+1 通り。 | ||
+ | これを長さ l1,l2,...,lk の重区間について合計すると、j−k(Li−1) となる。 | ||
+ | |||
+ | * DP[i][j][k]+=DP[i−1][j][k]×(j−k(Li+1)) | ||
+ | |||
+ | == 独立した新規重区間とする場合 == | ||
+ | |||
+ | 並び順を考慮すると、挿入位置は k+1 個ある。合計長は純粋に Li 増える。 | ||
+ | |||
+ | * DP[i][j+Li][k+1]+=DP[i−1][j][k]×(k+1) | ||
+ | |||
+ | == 左右にはみ出る場合 == | ||
+ | |||
+ | どの重区間からはみ出すかで k 通り、はみ出す方向が2通りある。 | ||
+ | |||
+ | 1~Li−1 だけはみ出る余地がある。 | ||
+ | |||
+ | * DP[i][j+1][k+1]+=DP[i−1][j][k]×2k | ||
+ | * DP[i][j+2][k+1]+=DP[i−1][j][k]×2k | ||
+ | * ... | ||
+ | * DP[i][j+Li−1][k+1]+=DP[i−1][j][k]×2k | ||
+ | |||
+ | == 2つの重区間を繋げる場合 == | ||
+ | |||
+ | k≥2 の場合に限る。どの2区間を繋げるかで k−1 通り。 | ||
+ | |||
+ | 繋げる2つの重区間の距離がどれだけ開いていたかで 0~Li−2 の場合分けがあり、距離 e だけあいていた場合、それが Li のどこに当たるかで Li−e−1 通り。 | ||
+ | |||
+ | e=3 | ||
+ | |=====|...|=====| | ||
+ | |-----| | ||
+ | | ||
+ | |-----| | ||
+ | |||
+ | * DP[i][j+0][k−1]+=DP[i−1][j][k]×(k−1)(Li−0−1) | ||
+ | * DP[i][j+1][k−1]+=DP[i−1][j][k]×(k−1)(Li−1−1) | ||
+ | * ... | ||
+ | * DP[i][j+Li−2][k−1]+=DP[i−1][j][k]×(k−1)(Li−(Li−2)−1) | ||
+ | |||
+ | === 計算量 === | ||
+ | |||
+ | さて、しかしここまでやっても、雑な見積もりでは状態数が O(N2X)、1回の遷移が O(Li) で、全体で O(N2X2) となってしまう。 | ||
+ | |||
+ | DP[i][j][k] | ||
+ | i: 区間数 | ||
+ | j: 重区間長合計 1~X × Li = O(N^2 X^2) | ||
+ | k: 重区間数 | ||
+ | |||
+ | だめじゃん。 | ||
+ | |||
+ | だが、重区間の個数 k の上限を注意深く考えると、実はそこまで大きくならない。 | ||
+ | |||
+ | たとえば X=80,L30=10 のような状況の時、あり得る重区間の個数は何個か?と考えると、それより前の29個の区間は(大きい方から処理してるので)長さ 10 以上である。 | ||
+ | よって、独立した重区間の個数は最大でも8個にしかならず、DPの第3添字 k は 1~8 の範囲だけ考えればよい。 | ||
+ | |||
+ | より一般化すると、i 番目の区間について考慮するとき、区間数は k≤XLi で抑えられるので、全体で O(NX2) となる。 | ||
+ | |||
+ | より正確な見積もり | ||
+ | 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) | ||
</ | </ |