差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2021/02/18] – [解法] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======第6回 ドワンゴからの挑戦状 予選 B問題メモ====== | + | ======第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ====== |
[[https:// | [[https:// | ||
行 22: | 行 22: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | 解説pdfの確率を利用する方法がよりスマートだが、一応自力解法をメモしておく。 | + | 解説pdfの確率を利用する方法がよりスマート。自分は別の考え方で解いて、複雑なだけで特に優れている点は無いが、一応メモしておく。 |
出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。 | 出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。 | ||
行 35: | 行 35: | ||
------------------------ | ------------------------ | ||
x 1 | x 1 | ||
- | d 2 | + | d 2 |
===区間より左のスライムの考察=== | ===区間より左のスライムの考察=== | ||
行 84: | 行 84: | ||
今までは $k$ を固定して考えていたが、$k=0~i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。(あくまで $d_i$ より左のみ) | 今までは $k$ を固定して考えていたが、$k=0~i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。(あくまで $d_i$ より左のみ) | ||
- | $\displaystyle \sum_{k=0}^{i-1}\frac{(i-1)!}{k!}(R_k+k!)$ | + | $\displaystyle |
- | これは、新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回 | + | これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、 |
+ | 新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回ループを回さなくても計算できる。 | ||
===区間より右のスライム=== | ===区間より右のスライム=== | ||
行 145: | 行 146: | ||
</ | </ | ||
+ | /* | ||
+ | |||
+ | ===== C - Cookie Distribution ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | |||
+ | ==== 例 ==== | ||
+ | |||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | |||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | */ | ||
+ | |||
+ | ===== D - Arrangement ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * $1~N$ の順列 $p_1, | ||
+ | * 条件 | ||
+ | * $i=1~N$ について、$i$ の右側に $a_i$ が来てはいけない | ||
+ | * 存在しない場合は '' | ||
+ | * $2 \le N \le 10^5$ | ||
+ | * $i \neq a_i$ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | まず、サンプルにあるが、$N=2$ の場合は $(a_1, | ||
+ | |||
+ | 辞書順最小でよくある解法は、先頭から「この後が破綻しない限り、貪欲に現在置ける最小のものを置く」というもの。 | ||
+ | |||
+ | 破綻するかどうかを手早く判定できることがポイントとなる。 | ||
+ | |||
+ | で、置ける条件、破綻する条件を探していく。これは実際にいろいろ試す。\\ | ||
+ | 直前に置いた値を $p$、残っている最小の値を $q$、その次に小さい値を $r$ とする。 | ||
+ | |||
+ | * $a_p \neq q$ の場合、ある1ケースを除いて、$q$ を置いてよい | ||
+ | * $a_p = q$ の場合、ある1ケースを除いて、$r$ を置いてよい | ||
+ | |||
+ | そして、ある1ケースとは「残っている全ての数字に対して $a_i=x$ となっている」場合。\\ | ||
+ | これは、今 $x$ を置いておかないと今後置ける機会が無くなってしまうので、大小にかかわらず $x$ を置く。 | ||
+ | |||
+ | 逆に、このようなケースが1度見つかったら、あとは「$x$ のすぐ右に置く数字は $a_x$ 以外」という他に制約は無くなるので、そこだけ注意して昇順に並べてよい。 | ||
+ | |||
+ | N = 9 | ||
+ | a : 2 3 5 5 4 5 5 5 5 | ||
+ | | ||
+ | 1 3 2 ・ここまで決めた後、5自身を除き全ての数字の ai = 5 | ||
+ | 1 3 2 5 ・5を置いておかないと、置ける機会が無くなる | ||
+ | 1 3 2 5 6 ・次に小さい値は4だが、a5 = 4なので置けず、次善の6を置く | ||
+ | 1 3 2 5 6 4 7 8 9 ・あとは昇順でよい | ||
+ | |||
+ | また、残りが2個になったら破綻する条件がもう1つ加わり、$q, | ||
+ | しかし実際は残り3個の状態で $q$ または $r$ を前に持ってくることで、破綻を防げる。 | ||
+ | |||
+ | 従って、以下のアルゴリズムで残り3個になるまで構築し、 | ||
+ | |||
+ | * 各数が「右隣においてはいけない数」として指定されている個数を管理(確定した数字の分はその都度減らす)する | ||
+ | * 「置くべき残り個数 - 1(自身の分)」と「自身が右隣においてはいけない数として指定されている個数」が等しい数があれば、その数を置く | ||
+ | * 残りはほぼ昇順に並べられる | ||
+ | * そうで無ければ、直前に置いた値を $p$、残っている最小の値を $q$、その次に小さい値を $r$ として、 | ||
+ | * $a_p \neq q$ の場合、$q$ を置く | ||
+ | * $a_p = q$ の場合、$r$ を置く | ||
+ | |||
+ | 残り3個になったら、総当たりしても高々6通りなので、破綻しない最小のものを探して後ろにくっつければよい。 | ||
+ | |||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <sxh python> | ||
+ | import sys | ||
+ | from collections import Counter | ||
+ | from heapq import heappop, heapreplace | ||
+ | from itertools import permutations | ||
+ | from operator import itemgetter | ||
+ | |||
+ | |||
+ | def fill_remaining(ans, | ||
+ | """ | ||
+ | xを先頭にして残りを昇順に追加 | ||
+ | ただしxの次の要素のみ、aaa[x]で禁止されていた場合はその次と入れ替える | ||
+ | remainingにはxを含め3要素以上残っていることが前提 | ||
+ | """ | ||
+ | ans.append(x) | ||
+ | i = len(ans) | ||
+ | while remaining: | ||
+ | k = heappop(remainings) | ||
+ | if k != x: | ||
+ | ans.append(k) | ||
+ | if aaa[x] == ans[i]: | ||
+ | ans[i], ans[i + 1] = ans[i + 1], ans[i] | ||
+ | |||
+ | |||
+ | def solve(n, aaa): | ||
+ | if n == 2: | ||
+ | return [-1] | ||
+ | |||
+ | in_degrees = Counter(aaa) | ||
+ | |||
+ | # 少なくとも残り個数がこれ+1になるまでは「ある条件」には当てはまらない | ||
+ | # ただし減少することはあるため、直前に再チェック必要 | ||
+ | curr_max = max(in_degrees.values()) | ||
+ | |||
+ | remainings = list(range(1, | ||
+ | |||
+ | aaa.insert(0, | ||
+ | |||
+ | ans = [] | ||
+ | banned = -1 | ||
+ | for i in range(n - 3): | ||
+ | if curr_max == n - i - 1: | ||
+ | curr_x, curr_max = max(in_degrees.items(), | ||
+ | if curr_max == n - i - 1: | ||
+ | fill_remaining(ans, | ||
+ | return ans | ||
+ | top = heappop(remainings) | ||
+ | if top == banned: | ||
+ | ans.append(heapreplace(remainings, | ||
+ | else: | ||
+ | ans.append(top) | ||
+ | banned = aaa[ans[-1]] | ||
+ | # 確定した数字の入り次数を削減 | ||
+ | if banned in in_degrees: | ||
+ | if in_degrees[banned] == 1: | ||
+ | del in_degrees[banned] | ||
+ | else: | ||
+ | in_degrees[banned] -= 1 | ||
+ | in_degrees.pop(ans[-1], | ||
+ | |||
+ | remainings.sort() | ||
+ | for i, j, k in permutations(remainings): | ||
+ | if i != banned and j != aaa[i] and k != aaa[j]: | ||
+ | ans += [i, j, k] | ||
+ | break | ||
+ | |||
+ | return ans | ||
+ | |||
+ | |||
+ | n, *aaa = map(int, sys.stdin.buffer.read().split()) | ||
+ | print(*solve(n, | ||
+ | |||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | ===== E - Span Covering ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 長さがそれぞれ $L_1, | ||
+ | * このシートを、両端の座標が整数になるよう区間 $[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 | ||
+ | |----| | ||
+ | |--| 独立した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 \dfrac{X}{L_i}$ で抑えられるので、全体で $O(NX^2)$ となる。 | ||
+ | |||
+ | より正確な見積もり | ||
+ | DP[i][j][k] | ||
+ | i: 区間数 | ||
+ | j: 重区間長合計 1~X × Li = O(N X^2) | ||
+ | k: 重区間数 | ||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <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) | ||
+ | |||
+ | </ | ||
+ | ++++ | ||