ペペロパーティー

残った贈り手と受け手をそれぞれ番号順に並べ、同じ順位同士を対応させる。最初は自分自身との対応なので有効である。この対応が有効で、対応先の番号が贈り手の元の番号以下という不変条件を維持する。

贈り手$i$の対応先を$x$、その直前の残った受け手を$y$とする。直前がなければ$y=0$とする。$L_i>y$の人を詰まった贈り手と呼ぶ。先頭の贈り手は常に詰まっている。最も右の詰まった贈り手$i$を選ぶ。

応答$j$は$j\geq L_i>y$なので$x$より左にはない。$i$とを除くと、その間の贈り手の対応先が受け手1人分ずつ左にずれる。の右に詰まった人はいないので、下限を満たし続ける。対応先は小さくなるので上限も保たれる。したがって、インタラクターのどの選択に対しても毎ターン成功する。

残った各贈り手について

$$D_i=\operatorname{rank}_{\rm giver}(i)-\#\{\text{残った受け手 }j<L_i\}-1$$

を管理する。順位は1から数える。有効な対応では$D_i\geq0$であり、詰まった人はちょうど$D_i=0$の人である。贈り手$i$と受け手を除くと、かつを満たす人のだけが1減る。の人は必ずの右にいるため、2つの順位の変化が相殺される。

元の贈り手の番号を大きさ$B$のブロックに分ける。各ブロックを$L_i$順に並べ、遅延セグメント木で接頭辞への減算と最小値を管理する。選択した人のブロックは遅延値を展開し、直接更新して再構築する。右側の完全なブロックは$L_k\leq j$の接頭辞を1減らす。最小値0のブロック集合から最も右の0を探せる。

時間計算量は$O(N(B+(N/B)\log B))$、空間計算量は$O(N)$であり、実装では$B=1024$とする。では順序対応を配列で直接管理する解法でよい。では贈り手と受け手の使用状況を2つのビットマスクで表し、すべての応答を調べる完全探索で解ける。

Solution written by GPT6.1