ABC 225 H — Social Distance 2

考察

固定席の間で隣接着席位置の差の積が因数分解する。未着席のD=M−K人をどの空席に置くかだけを先に数え、最後に相異なる人の割当てD!を掛ける。

内部の固定席a<bの間の空席数をq=b−a−1とする。k人を追加すると正の距離がk+1個、その和はq+1である。距離gの重みgを表す母関数はΣ_{g≥1}g z^g=z/(1−z)²なので、内部区間の係数は

[z^(q+1)](z/(1−z)²)^(k+1)=C(q+k+1,2k+1)。

左端または右端の固定席までの空席数qでは、固定席に向かうk個の距離だけに重みが付き、外端側の空席には重みがない。母関数に1/(1−z)を一つ掛け、係数はC(q+k,2k)となる。k=0でも1である。

K=0なら端の二つの空席部分が無重み、着席者間のk−1個の距離が重み付きである。左右の余白をe_L,e_R≥0、着席者間の距離をg_1,…,g_{k−1}≥1とすると、e_L+Σg_i+e_R=N−1。したがってN席にk≥1人を置く重み和は

[z^(N−1)] (z/(1−z)²)^(k−1) / (1−z)²
= [z^(N−k)] (1−z)^(−2k)
= C(N+k−1,2k−1)

となる。距離の和は席数Nではなく最初から最後までの差N−1である。この場合はk=Mを評価し、相異なるM人の割当てM!を掛ける。N=M=2ならC(3,3)·2!=2で、二つの座り方のスコア1ずつに一致する。一般にM=NならC(2N−1,2N−1)=1なので答えはN!。

K≥1では各空席区間についてP_q(x)=Σ_{k=0}^{min(q,D)}係数_k x^kを作り、その積のD次係数へD!を掛ける。全区間の空席数はN−Kなので、多項式の総次数も高々N−K。小次数からNTTで積み、毎回D次で打ち切ればO(N log²N)で足りる。

典型の発動条件

固定点による区間独立化

発動条件: 一次元配置の評価が隣接選択点間の積で、いくつかの選択点が既に固定されているとき。

固定点間と両端の区間を分離し、各区間へ追加する人数だけを共有変数として残す。

生成多項式の積による人数配分

発動条件: 独立な部品ごとに使用個数別の重みがあり、全部品で使う総数を固定したいとき。

各区間のk人分のスコア和をx^kの係数にし、多項式積の指定次数を畳み込みで求める。

問題固有の要素

距離の積という非加法的なスコアが、固定席で切った各区間のスコアの積としてちょうど因数分解する。

別の問題へ持ち帰る視点: 隣接要素間の積を全配置で足す問題では、固定境界で独立成分へ切り、各成分の重みを生成関数の係数にする。

正当性

内部区間では着席位置と正の距離の組が一対一であり、各距離の重みgを掛けた係数抽出が全位置選択のスコア和になる。端区間では無重みの端の余白を一つ、固定席なしでは二つ加えることで同じ対応が成立する。固定席をまたぐ距離は存在せず、スコアは区間ごとの積なので、人数配分は多項式の積の次数で合成できる。位置のみを数えた後にD!で人の区別を戻す。 固定席なしでは距離と両余白の和がN−1であり、係数はC(N+k−1,2k−1)。k=Mを代入してM!を掛けると全員の着席を数える。

実装上の注意

  • qは空席数。内部ではC(q+k+1,2k+1)、端ではC(q+k,2k)。同じ未定義のnを使って式を混ぜない。
  • q=0の内部区間でもk=0の係数は隣接固定席の距離1であり1。
  • K=0はC(N+M−1,2M−1)·M!の別式、K=Mは積の定数項。階乗表の上限は2N程度で足り、各積はD次まででよい。

復習の核

  • 隣接距離の積は足し算DPへ急いで落とさず、固定点で切ったとき区間ごとの積へ分解するかを確認する。

計算量と制約

時間

O(N log²N)。区間多項式の総次数≤N−K、係数作成O(N)、均衡する積木または小次数優先NTTでO(N log²N)。

空間

O(N)。消費した入力多項式を解放し、NTT作業領域と現在の積だけを保持する。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 2 \leq M \leq N; 0 \leq K \leq M; 1 \leq A_1 \lt A_2 \lt \ldots \lt A_K \leq N; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Social Distance 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 組合せを生成関数へ符号化する

主題
追加で学ぶ技能
既習技能

主タグ: 畳み込み・相互相関 生成関数による組合せ構造の符号化

補助タグ: 組合せ係数・数え上げ

執筆: abc-explanation-author1.1.1 / revision 3

学習の位置

体系上の位置: 組合せを生成関数へ符号化する

  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。
  • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。

先に読む単元:

この解説で扱わないこと:

  • 係数列同士を単に畳み込む相互相関、および係数の組合せ的意味を持たない信号処理。

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題