目次
文書の過去の版を表示しています。
AtCoder Regular Contest 101
C - Candles
問題
- 数直線上に $N$ 本のろうそく
- ろうそくの存在する座標は、昇順に $x_1,x_2,...,x_N$
- 同じ座標に複数のろうそくはない
- すぬけ君は座標0にいて、$K$ 本のろうそくに火を付けたい
- 座標 $x$ にいるとき、$x$ にあるろうそくに火を付けられる
- 最小の移動距離を求めよ
- $1 \le K \le N \le 10^5$
- $-10^8 \le x_i \le 10^8$
例
N=5 本中 K=3 本に火を付ける
-30 -10 10 20 50
-----------------------------
,-- 0
`---------->
40動けば、-10,10,20の3本に火を付けられる
解法
連続する $K$ 本につけることになる。また、行ったり来たりは無駄なので、取りうる行動は
- ずっと $K$ 本目まで右に行く
- 最初右に行き、途中で引き返す
- 最初左に行き、途中で引き返す
- ずっと $K$ 本目まで左に行く
となる。これは、火を付ける $K$ 本の両端の座標を $l,r$ とすると
- 0から $l$ まで行き、$l$ から $r$ まで行く$=|l|+(r-l)$
- 0から $r$ まで行き、$r$ から $l$ まで行く$=|r|+(r-l)$
のいずれかとなる。
ずっとK本目まで右に行く = 0→l→r
0 l r
---|--|--------------|--
最初右に行き、途中で引き返す = 0→r→l
l 0 r
-----|----------|----|--
最初左に行き、途中で引き返す = 0→l→r
l 0 r
-----|---|-----------|--
ずっとK本目まで左に行く = 0→r→l
l r 0
--|--------------|---|--
$0,l,r$ の位置関係が上記の通りでない場合、計算結果は無駄に距離が長くなるだけなので、最小値を求める過程では気にしなくてよい。
$l,r$ について全探索すればよい。
n, k = map(int, input().split()) xxx = list(map(int, input().split())) print(min(min(abs(l), abs(r)) + r - l for l, r in zip(xxx, xxx[k - 1:])))
D - Median of Medians
問題
- 数列 $b$ の中央値とは、要素を昇順にソートしたものを $b'$ とすると、$b'$ の $|b|/2+1$ 番目の要素を指す
- (1,2,3)→2
- (1,2,3,4)→3
- 長さ $N$ の数列 $A={a_1,a_2,...,a_N}$ がある
- ある連続部分列 $a_l,a_{l+1},...,a_r$ を決めたとき、その中央値を $m_{l,r}$ とする
- $A$ から取れる全ての連続部分列の $m_{l,r}$ を並べて数列 $m$ を作る
- $m$ の中央値を求めよ
- $1 \le N \le 10^5$
解法
以下、解説の写経。
中央値を求めるアルゴリズム
今回の「中央値」の定義の場合、数列 $A$ の中央値 $d$ をプログラム的に扱いやすく定義すると、以下のようになるらしい。
- $A$ の中に $d$ 以上の要素が $|A|/2$ 個以上ある（切り上げ）
- そのような数の中で、$d$ は最大である
A = 3 5 5 5 6 7 7 8 d = 5 を確認 d以上: x o o o o o o o → |A|/2=4 個以上 d = 6 を確認 d以上: x x x x o o o o → 4個以上 d = 7 を確認 d以上: x x x x x o o o → 4個未満 よって中央値は6
そしてこれはさすがに1発では求められないので、2分探索によって求めることになる。
今回の問題で必要な情報
さて、この性質を今回の問題に適用すると、ある $d$ について、$m$ の中央値以上か未満かチェックするとき、
- 全ての連続部分列の中央値のうち、$d$ 以上になるものの個数が、$|m|/2$ 個以上か
を求めればよい。$|m|=$連続部分列の個数$=\frac{|A||A+1|}{2}$ であり、条件を満たせば答えは $d$ 以上である。
しかし、こうしたところで「全ての連続部分列の中央値」をどうやって求めるんだという話になる。1つ1つ求めていくと当然TLE。
ここで「中央値そのもの」の値は必要なく「中央値が $d$ 以上になるかどうか」だけの情報が必要であることに着目する。
ある長さ $k$ の連続部分列 $S_{l,r}$ において、$d$ 以上の値が $|k|/2$ 個以上含まれるなら、その中央値は $d$ 以上である。
S_lr = 3 5 5 5 6 7 7 8
d = 5 をチェック
d以上: x o o o o o o o → |S_lr|/2 = 4 個以上含まれる
→ (具体的にはわからないけど)中央値は5以上
d = 7 をチェック
d以上: x x x x x o o o → 4 個未満
→ (具体的にはわからないけど)中央値は7未満
すると、$d$ を仮定すれば数列 $A$ から具体的な数値は捨象してよく、各要素が「$d$ 未満か以上か」でまとめてしまえることがわかる。
効率化
- 連続部分列のうち「$d$ 以上の要素の個数 $\ge d$ 未満の要素の個数」となるものの個数
を求めればよいことがわかったので、この条件を高速に判定する方法を考える。
これは、ある部分列 $S_{l,r}$ が条件を満たすか判定する方法を考えると、要素を置き換えて和を計算する方法だと簡単に求めることができる。
つまり、あらかじめ $A$ の要素を $d$ 以上なら1、未満なら-1に置き換えると、
- $S_{l,r}$ の和が0以上 ⇔ $d$ 以上の値が半分以上
- $S_{l,r}$ の和が0未満 ⇔ $d$ 以上の値が半分未満
となる。そして、部分列の和と言えば、おなじみ累積和を用いる。
- $S_{l,r}$ の和が0以上 ⇔ 累積和 $R_r - R_{l-1} \ge 0$
すると結局、
- 全ての $(l,r)$ の組で、$R_{l-1} \le R_r$ であるものの個数
を求めればよいことになる。これは、Binary Index Tree などを使って計算できる。BITは、以下の2つを高速に処理できる。
- add(i,x): 数列の $i$ 番目に 値 $x$ を加算する
- sum(i): 現時点の 1～$i$ の和を求める
累積和 $R$ を順番に処理する。処理中の累積和の値を $p$ とすると
- sum(p): $p$ を $R_r$ と見做して、自身より左に出てきた、自身以下の値の個数
- add(p,1): $p$ を $R_{l-1}$ と見做して、以降の処理のために自身の存在を記録
この2処理を順次行うと、sum(p)の合計が、条件を満たす $(l,r)$ の組の個数となる。（ただし累積和は負にもなるが、BITの処理を行う上でpは正である必要があるため、あらかじめNなどを加算して調整しておく）
これにより、仮定した中央値 $d$ が、真の中央値以上か未満か判定し、2分探索で答えを求めることになる。
発想の転換が3回くらい必要な問題。
from itertools import accumulate
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
def reset(self):
self.tree = [0] * (self.size + 1)
def solve(n, aaa):
t = n * (n + 1) // 4
alt = sorted(set(aaa))
l, r = 0, len(alt) - 1
bt = Bit(n * 2)
while l <= r:
m = (l + r) // 2
am = alt[m]
ccc = accumulate(1 if a - am >= 0 else -1 for a in aaa)
bt.add(n, 1)
right_order = 0
for p in ccc:
p += n
right_order += bt.sum(p)
bt.add(p, 1)
if right_order >= t:
l = m + 1
else:
r = m - 1
bt.reset()
return alt[r]
n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
