ペペロの贈り物

小課題1 残る人の集合をビットマスクで表す。各状態で送り手$a$と最も近い受け手$b$をすべて試し、$2$人を消した状態へ遷移する。選択を保存すれば操作列も復元できる。時間計算量は$O(2^N N^2)$、空間計算量は$O(2^N+N^2)$である。

最小値 時計回りに隣り合う人の間隔を$D_1,\ldots,D_N$とし、$D_N=L-X_N+X_1$とする。奇数番目の間隔の和を、偶数番目をとすると答えはである。

任意の操作列は完全マッチングを作る。各組が移動する最短の弧を取り、各間隔を覆う弧の本数を数える。各人を端点とする弧はちょうど$1$本なので、左右の間隔の本数の偶奇は異なる。したがって奇数番目または偶数番目の間隔がすべて奇数回覆われ、総距離は$\min(A,B)$以上である。

交互の隣接マッチング$2$通りのうち和が小さい方を選ぶ。その和は$L/2$以下なので、選んだ各間隔も最短の弧である。あとは最近傍規則に従って実行できることを示す。

操作順 残っている人の間隔は選択・非選択が交互に並ぶ。その和を$A\le B$とする。どの選択組も両方向で不合法なら、各選択間隔は左右両方の非選択間隔より長い。すべて足すと$2A>2B$となり矛盾する。よって少なくとも一方向で実行できる組がある。

長さ$d$の組を消すと、隣接する非選択間隔と選択間隔が結合し、和は$A-d$と$B+d$になる。不等式は保たれるので最後まで繰り返せる。残り$2$人は互いに最近傍である。

双方向連結リストで円上の現在の隣人を管理する。毎回残る人を走査し、決めた相手までの距離が左右の隣人までの距離以下ならその向きで操作する。円上の最近傍は左右の隣人のどちらかである。時間計算量は$O(N^2)$、空間計算量は$O(N)$である。

Solution written by GPT6.1