目次
文書の過去の版を表示しています。
第6回 ドワンゴからの挑戦状 予選 B,D問題メモ
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$ として記録しておくことで、動的計画法的に計算できる。
kを固定
スライムを左から選ばれた順に並べ、スライム $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$ を固定して考えていたが、$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$ の右側に $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通りなので、破綻しない最小のものを探して後ろにくっつければよい。
