Codeforces Round #552 (Div. 3) E. Two Teams

問題概要

$n$ 人の人間が横一列に並んでおり, $i$ 番目の人間は能力値 $a_i$ を持つ. このとき, $a$ は長さ $n$ の順列になっている. この $n$ 人を, 以下に従って二つのチームに分ける.

チーム番号 $x$ を $x=1$ として初期化する.
$a$ の中で最大の能力を持つ人間を探し, その人間をチーム $x$ に分類する. また, この人の番号を $i$ とする.
人 $i$ より右にいる人 $k$ 人をチーム $x$ に分類し, その $k$ 人を $a$ から取り除く. 右にいる人が $k$ 人に満たない場合は右にいる人を全員 $x$ に分類した後 $a$ から取り除く.
人 $i$ より左にいる人も同様に(最大) $k$ 人分類し $a$ から取り除く.
$x$ を $3-x$ に変更し, また人 $i$ を $a$ から取り除く. $a$ に人が残っている場合 2. に進み, 残っていない場合終了.

このとき, それぞれはどちらのチームに分類されるか？

解法

「自分にとって左」と「自分にとって右」が管理できれば, 同じ人は一回しか見ないので愚直に実行すれば間に合います. では, この情報はどのように管理すればよいでしょうか.

Dancing Links と呼ばれるデータ構造を使えば良いです. 詳しくはこれのC問題を見てくれればいいんですが, 大雑把に言えば, 次のようになります.

$l_i :=$ (自分の左の人のindex), $r_i :=$ (自分の右の人のindex)とします. もし自分が消えると, 影響を及ぼすのは自分の両隣で, 左の人にとっての右が自分から自分の右の人に, また右の人にとっての左が自分から自分の左の人になります. これを数式でかけば, $i$ 番目の人が消えるとき, $r_{l_i} \leftarrow r_i, l_{r_i} \leftarrow l_i$ とすればよいわけです. なんのこっちゃわからん人はおとなしく上のリンク先のスライドをよく読んでください.

遅延セグ木でガチってもできると思います. 知らんけど

実装

めっちゃばぐった

Submission #145116767 - Codeforces