差分

このページの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://atcoder.jp/contests/dwacon6th-prelims|Dwango Programming Contest 6th]]
@@ 行 146: / 行 146: @@
 </sxh>
+/*
+===== C - Cookie Distribution =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_c|C - Cookie Distribution]]
+==== 問題 ====
+==== 例 ====
+==== 解法 ====
+++++ Python3 |
+<sxh python>
+</sxh>
+++++
+*/
+===== D - Arrangement =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d|D - Arrangement]]
+==== 問題 ====
+  *  $1～N$  の順列  $p_1,p_2,...,p_N$  であって、以下の条件を満たすもののうち辞書順最小のものを求めよ
+  * 条件
+    *  $i=1～N$  について、 $i$  の右側に  $a_i$  が来てはいけない
+  * 存在しない場合は ''-1'' を答えよ
+  *  $2 \le N \le 10^5$
+  *  $i \neq a_i$
+==== 解法 ====
+まず、サンプルにあるが、 $N=2$  の場合は  $(a_1,a_2)=(2,1)$  の1通りしか無く、これは破綻する。以下、 $N \ge 3$  とする。
+辞書順最小でよくある解法は、先頭から「この後が破綻しない限り、貪欲に現在置ける最小のものを置く」というもの。
+破綻するかどうかを手早く判定できることがポイントとなる。
+で、置ける条件、破綻する条件を探していく。これは実際にいろいろ試す。\\
+直前に置いた値を  $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
+3 2                ・ここまで決めた後、5自身を除き全ての数字の ai = 5
+3 2 5              ・5を置いておかないと、置ける機会が無くなる
+3 2 5 6            ・次に小さい値は4だが、a5 = 4なので置けず、次善の6を置く
+3 2 5 6 4 7 8 9    ・あとは昇順でよい
+また、残りが2個になったら破綻する条件がもう1つ加わり、 $q,r$  が  $a_q=r, a_r=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, aaa, x, remaining):
+    """
+    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, n + 1))
+    aaa.insert(0, 0)
+    ans = []
+    banned = -1
+    for i in range(n - 3):
+        if curr_max == n - i - 1:
+            curr_x, curr_max = max(in_degrees.items(), key=itemgetter(1))
+            if curr_max == n - i - 1:
+                fill_remaining(ans, aaa, curr_x, remainings)
+                return ans
+        top = heappop(remainings)
+        if top == banned:
+            ans.append(heapreplace(remainings, top))
+        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], 0)
+    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, aaa))
+</sxh>
+++++
+===== E - Span Covering =====
+[[https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_e|E - Span Covering]]
+==== 問題 ====
+  * 長さがそれぞれ  $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>
+++++