第6回 ドワンゴからの挑戦状 予選 B,D,E問題メモ

Dwango Programming Contest 6th

なんかドワコンは毎回苦手意識がある。

B - Fusing Slimes

• 数直線上にスライムが $N$ 体並ぶ
• 左から $i$ 番目のスライムは、整数座標 $x_i$ に位置する
• 以下の操作を $N-1$ 回繰り返し、スライムを1匹になるまで合成する
  • 残っている中で右端の1匹を除くスライムを等確率で選ぶ
  • 選んだスライムを、右隣のスライムの位置まで移動させて、合成して1匹にする
• スライムの移動距離の総計の期待値に、$(N-1)!$ をかけた値を、$10^9+7$ で割った値を求めよ
• $2 \le N \le 10^5$
• $1 \le x_1 \lt x_2 \lt ... \lt x_N \le 10^9$

解説pdfの確率を利用する方法がよりスマート。自分は別の考え方で解いて、複雑なだけで特に優れている点は無いが、一応メモしておく。

出力すべき値はややこしい書き方をされているが、要はスライムを選ぶ順番が全部で $(N-1)!$ 通りあり全て等確率なので、全ての選び順においての移動距離の総和を求めればよい。 この「全ての選び順における移動距離の総和」を「総実現値」と呼ぶことにする。

1回の選び方ごとに移動距離を計算するのは難しいので、各隣接スライム間の距離を「区間」として、その区間が総実現値に何回足されることになるかを計算する。 スライム $i～i+1$ の区間を $d_i$ と表す。

i  1   2   3   4   5   6    スライムのindex
     1   2   3   4   5      区間のindex
------------------------
x  1   3   6  10  15  21    スライムの位置
d    2   3   4   5   6      区間長

区間 $d_i$ を通る可能性のあるスライムは、$1～i$ に限られる。まずはこの $i$ 個のみの、全ての選び順における通過回数を考える。

スライム $i$ が選択された時に、はじめて $d_i$ を1匹のスライムが通過する。 （それまでに他のスライムが選ばれていたとしても、どこかでせき止められている）

その時に区間の左側に残ったスライムの数を $k$ とすると、先ほどの1回に加え、あといくつのスライムが $d_i$ を通るか？

これは $k$ にのみ依存し、初期状態から区間 $k$ を通過するスライムの数と一致する。（ただし $k=0$ のとき 0）

😄  😄   😄    😄<---di--->🙂 ...

初手で選ばれたとき
😄  😄   😄     ・<---di--->🙂    残り3個 = 区間3を通るスライムの数と一致
↓
😄  😄   😄<--->                ←この通過回数と一致

いくつか合成されてから選ばれたとき
・   😄   ・     ・<---di--->🙂    残り1個 = 区間1を通るスライムの数と一致
↓
😄<-->・                         ←この通過回数と一致

よって $i$ が小さい方から、$d_i$ の総実現値への寄与回数を計算して、その結果を $R_i$ として記録しておくことで、動的計画法的に計算できる。

スライムを左から選ばれた順に並べ、スライム $i$ が選ばれたときに左に $k$ 個残っている場合に、$d_i$ が何回通過されるか（総実現値への $d_i$ の寄与回数）を考える。

|-------------------|  i個
○ ... ○ i ○ ... ○
|-------|   |-------|
 i-k-1個       k個

スライム $i$ 以外の $i-1$ 個の左右への振り分け方は ${}_{i-1}C_k$ 通り。

左側の（先に選ばれた）スライムの並び順は $(i-k+1)!$ 通り。

右側のパターン数は $R_k$ に包含されているので考えなくてよいが、 区間 $d_i$ 自体の寄与回数は、残る $k$ 個の選び順のパターン数だけ“1”が加算されるので、 $R_k+k!$

これらを掛け合わせて、$\displaystyle {}_{i-1}C_k(i-k+1)!(R_k+k!) = \frac{(i-1)!}{k!}(R_k+k!)$ となる。（あくまで $d_i$ より左のスライムのみに限定した場合）

今までは $k$ を固定して考えていたが、$k=0～i-1$ までの値を取るので、この総和を取ったものが $d_i$ の寄与回数となる。（あくまで $d_i$ より左のみ）

$\displaystyle (i-1)!\sum_{k=0}^{i-1}\frac{R_k+k!}{k!}$

これをこのまま計算すると各 $i$ の中で $k$ のループが回るので $O(N^2)$ だが、$\sum$ 内は $k$ のみに依存するので、 新しい $R_i$ が求められるたびに $\displaystyle \frac{R_i+i!}{i!}$ を加算していけば、毎回ループを回さなくても計算できる。

さて、これまでで区間より左に限定したスライムの寄与回数が決まったが、ここに区間より右のスライムの選び方を乗じる必要がある。

区間より右の $N-i$ 個のスライムは、いつ選ばれようと、区間 $d_i$ の加算数に影響することは無い。

つまり、区間より左 $i$ 個の選び順の、$i+1$ 箇所の好きな位置に、どのような順番で挟み込んでもよい。

v  v  v  v  v
 ○ ○ ○ ○

よって、どの位置（v）に何個入れるかで ${}_{i+1}H_{N-i}$ 通り、その時の並び順で $(N-i)!$ 通り、あわせて $\frac{N!}{i!}$ 通りとなる。

$R_0=0$ として、$\displaystyle dp[i]=\sum_{k=0}^{i}\frac{R_k+k!}{k!}$、つまり $dp[0]=1$ とする。

左の区間から、その区間の総実現値を計算していく。

区間 $d_i$ の総実現値への寄与は $\displaystyle d_i \times (i-1)! dp[i-1] \times \frac{N!}{i!}$ となるので、これを足し合わせていく。

同時に $\displaystyle dp[i]=dp[i-1]+\frac{(i-1)! dp[i-1] + i!}{i!}$ として次の区間の計算に備える。

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

ans = 0
dp = 1
for i in range(n - 1):
    cur = dp * factorials[i] % MOD
    ans = (ans + (xxx[i + 1] - xxx[i]) * cur * invs[i + 1]) % MOD
    dp = (dp + (cur + factorials[i + 1]) * invs[i + 1]) % MOD
ans = ans * factorials[n - 1] % MOD
print(ans)

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

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))

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$

$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

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)