差分
このページの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:// | ||
行 146: | 行 146: | ||
</ | </ | ||
+ | /* | ||
+ | |||
+ | ===== C - Cookie Distribution ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | |||
+ | ==== 例 ==== | ||
+ | |||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | |||
+ | ++++ Python3 | | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | |||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | */ | ||
+ | |||
+ | ===== D - Arrangement ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 1~N の順列 p1,p2,...,pN であって、以下の条件を満たすもののうち辞書順最小のものを求めよ | ||
+ | * 条件 | ||
+ | * i=1~N について、i の右側に ai が来てはいけない | ||
+ | * 存在しない場合は '' | ||
+ | * 2≤N≤105 | ||
+ | * i≠ai | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | まず、サンプルにあるが、N=2 の場合は (a1,a2)=(2,1) の1通りしか無く、これは破綻する。以下、N≥3 とする。 | ||
+ | |||
+ | 辞書順最小でよくある解法は、先頭から「この後が破綻しない限り、貪欲に現在置ける最小のものを置く」というもの。 | ||
+ | |||
+ | 破綻するかどうかを手早く判定できることがポイントとなる。 | ||
+ | |||
+ | で、置ける条件、破綻する条件を探していく。これは実際にいろいろ試す。\\ | ||
+ | 直前に置いた値を p、残っている最小の値を q、その次に小さい値を r とする。 | ||
+ | |||
+ | * ap≠q の場合、ある1ケースを除いて、q を置いてよい | ||
+ | * ap=q の場合、ある1ケースを除いて、r を置いてよい | ||
+ | |||
+ | そして、ある1ケースとは「残っている全ての数字に対して ai=x となっている」場合。\\ | ||
+ | これは、今 x を置いておかないと今後置ける機会が無くなってしまうので、大小にかかわらず x を置く。 | ||
+ | |||
+ | 逆に、このようなケースが1度見つかったら、あとは「x のすぐ右に置く数字は ax 以外」という他に制約は無くなるので、そこだけ注意して昇順に並べてよい。 | ||
+ | |||
+ | 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,r が aq=r,ar=q のような状態で残ると破綻してしまう。\\ | ||
+ | しかし実際は残り3個の状態で q または r を前に持ってくることで、破綻を防げる。 | ||
+ | |||
+ | 従って、以下のアルゴリズムで残り3個になるまで構築し、 | ||
+ | |||
+ | * 各数が「右隣においてはいけない数」として指定されている個数を管理(確定した数字の分はその都度減らす)する | ||
+ | * 「置くべき残り個数 - 1(自身の分)」と「自身が右隣においてはいけない数として指定されている個数」が等しい数があれば、その数を置く | ||
+ | * 残りはほぼ昇順に並べられる | ||
+ | * そうで無ければ、直前に置いた値を p、残っている最小の値を q、その次に小さい値を r として、 | ||
+ | * ap≠q の場合、q を置く | ||
+ | * ap=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:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 長さがそれぞれ 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 | | ||
+ | |||
+ | <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) | ||
+ | |||
+ | </ | ||
+ | ++++ | ||