[[第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ]]
現在位置: トップページ » アルゴリズム » contest_history » 索引 » 2020 » 第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ
文書の表示
管理サイトマップ

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
programming_algorithm:contest_history:atcoder:2020:0111_dwacon6th_prelims [2020/01/14] – [解法] ikatakosprogramming_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]] [[https://atcoder.jp/contests/dwacon6th-prelims|Dwango Programming Contest 6th]]
行 146: 行 146:
 </sxh> </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
 +  
 +      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$ が $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>
 +++++
  
  
programming_algorithm/contest_history/atcoder/2020/0111_dwacon6th_prelims.1578975474.txt.gz · 最終更新: 2020/01/14 by ikatakos
文書の表示
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0