目次
AtCoder Regular Contest 101 C,D,F問題メモ
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分探索によって求めることになる。
今回の問題で必要な情報
さて、この性質を今回の問題に適用して2分探索で答えを求めるとき、ある $d$ が、$m$ の中央値以上か未満か判定する必要がある。
- 全ての連続部分列の中央値のうち、$d$ 以上になるものの個数が、$|m|/2$ 個以上か
を求めればよい。$|m|=$連続部分列の個数$=\frac{|A||A+1|}{2}$ であり、条件を満たせば $m$ の中央値は $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$ と見做して、自身より左に出てきた、自身以下の値の個数（$r$ とペアになれる $l$ の個数）
- add(p,1): $p$ を $R_{l-1}$ と見做して、以降の処理のために自身の存在を記録
この2処理を順次行うと、sum(p)の合計が、条件を満たす $(l,r)$ の組の個数となる。（ただし累積和は負にもなるが、BITの処理を行う上でpは正である必要があるため、あらかじめNなどを加算して調整しておく）
これにより、$m$ の中央値が $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))
E - Ribbons on Tree
問題
例
解法
F - Robots and Exits
問題
- 数直線上にロボットが $N$ 体、出口が $M$ 個
- ロボットの座標は $x_1,x_2,...,x_N$
- 出口の座標は $y_1,y_2,...,y_M$
- 座標は全て異なる
- ロボットに対して、以下の2つの操作を好きな順序で何回でも繰り返せる
- 残る全てのロボットの位置を一斉に+1する
- 残る全てのロボットの位置を一斉に-1する
- ロボットが出口に重なると、そのロボットは取り除かれる
- 今、全てのロボットが取り除かれるまで操作を行った
- (ロボット1が出た出口, …, ロボットNが出た出口) の組としてあり得るものの個数を、$\mod{10^9+7}$ で求めよ
- $1 \le N,M \le 10^5$
- $1 \le x_i,y_i \le 10^9$
解法
あるロボットが出る出口は、初期位置の左右両脇にある2通りの出口のどちらかしかあり得ない。 （ただし、左右最も外側の出口より外のロボットは1通りのため、考慮から除いてよい）
一斉に動かすので、例えば「左の出口まで距離2、右まで3」というロボットが2つあったら、 どう足掻いてもこの2つを、一方は左、一方は右から出す、などと分けることは出来ない。
また、「①左まで3、右まで4」と「②左まで2、右まで5」というロボット①、②があったら、 ①を左から出しつつ、②を右から出すことは出来ない。 なぜなら、まずは左右どちらかから一方を出さないといけないが、 ①を左まで持ってったら②が既に左から出ているし、逆も然りなためである。 その他の左右の組合せは可能。
で、こういう条件が沢山あるのをまとめ上げるのに、解説pdfに倣い、2次元座標に変換して考える。
「左出口までの距離」を「左距離」、「右出口までの距離」を「右距離」と言うことにする。
前処理として、各ロボットの「左距離の集合」「右距離の集合」の2つについて独立に座標圧縮をしておく。 （実際には、座標圧縮は右のみでよく、左はソートさえすればよいが、説明上、左も行っているものとする）
例えば左右距離の集合が以下のようだったとして、
左 右 1 3 2 2 2 4 3 1 3 4 4 2
2次元座標上にプロットすると以下の感じになる。
右 4| o o
3| o
2| o o
1| o
0|
--------------------
0 1 2 3 4 左
$(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。 つまり、上か右のみに移動することになる。
実際の移動ではなく、初期位置からの最大距離な点に注意。(左→左→右)の移動は(2,1)でなく(2,0)であり、(左→左→右→右→右)ではじめて、(2,1)となる。
例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。
右 4| o o
3| o
2| R R【o】 o Lを通過: 左から出る
1| L o Rを通過: 右から出る
0| L
--------------------
0 1 2 3 4 左
これを踏まえて、以下のDPを考える。
- $DP[i][j] = (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数
- $DP[0][0] = 1$
これは何を示すかというと、
- 左距離が $i$ 以下のロボットについてのみ考える
- 左距離がずばり $i$ のロボットに関して、右距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す場合の組合せ数を示している
- 左距離が $i-1$ 以前のロボットについては経路によって左も右もあり得るが、それらを踏まえた組合せ数である
ただし $j$ については、必要無いのに無駄に右に進むことはせず、 ロボットを落とすのに必要最小限の距離についてのみ記録するとする。
$i=1$ のロボットを左から出すとき、右には1つも動かなくていい。右から出すとき、右に3動く必要がある。
座標上の動きで解釈すると、 $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。 （“左”座標の正の向きが“右”なのでややこしいが、座標上の動きを説明するときは、上と右で表現する）
右 4| o o
j 3| ,→1
2| | o o
1| | o
0| 1→1
--------------------
0 1 2 3 4 左(i)
$i=2$ のロボットのうち、$(2,4)$ について右から出そうと思えば、 「(1,0)から4つ上がる」「(1,3)から1つ上がる」の2通りの経路がある。この2つは、(1,3)を左右どちらに落としたかに相当する。
右 4| 【2】o
3| [1] 【 】: 着目中の座標
2| [ ] o o [ ] : 遷移元とできる範囲
1| [ ] o
0| 1 [1]
--------------------
0 1 2 3 4 左
しかし、$(2,2)$ については、直前で(1,3)を経由している経路については既に出口は右と確定しているので、 (1,3)の通り数の中に既に織り込まれていると解釈できる。
よって、遷移元とすることが可能な範囲は、$(1,0)$ に限られる。
右 4| 2 o
3| 1 [ ]: 遷移元とできる範囲
2| 【1】 o
1| [ ] o
0| 1 [1]
--------------------
0 1 2 3 4 左
また、「全て左から出す」「(1,3)のロボットは右から出したが、(2,4)は左から出す」ということを表現するため、 $i=1$ の結果はそのまま $i=2$ にスライドさせる。
右 4| 2 o
3| 1【1】
2| 1 o
1| o
0| 1 1【1】
--------------------
0 1 2 3 4 左
$i=3$ 以降も同様に、「$(i,j)$ のロボットを右から出すためには $(i-1, 0)～(i-1,j-1)$ から遷移できる（これらの和だけの経路がある）」として 座標を埋めていくと、以下のような感じになる。
右 4| 2 5 5
3| 1 1 1 1
2| 1 1 3
1| 1 1
0| 1 1 1 1 1
--------------------
0 1 2 3 4 左
答えは、最右列の総和、11となる。
実装
上記のように、各ロボット $(i,j)$ について毎回 $DP[i-1][0]～DP[i-1][j-1]$ の和を求める必要がある。
これは、DPをBinary Indexed Treeで持っておけば効率的に算出できる。
同じ $i$ のロボットが複数ある場合、$j$ の大きい方から更新していけば、 先に更新された分が後に処理する方の計算結果の邪魔をすることはないので、 BITreeは1つだけ作り、あとはin-placeに更新が可能である。
from bisect import bisect
from collections import defaultdict
class Bit:
def __init__(self, n, MOD):
self.size = n
self.tree = [0] * (n + 1)
self.depth = n.bit_length()
self.mod = MOD
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s % self.mod
def add(self, i, x):
while i <= self.size:
self.tree[i] = (self.tree[i] + x) % self.mod
i += i & -i
def debug_print(self):
for i in range(1, self.size + 1):
j = (i & -i).bit_length()
print(' ' * j, self.tree[i])
def lower_bound(self, x):
sum_ = 0
pos = 0
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k <= self.size and sum_ + self.tree[k] < x:
sum_ += self.tree[k]
pos += 1 << i
return pos + 1, sum_
n, m = map(int, input().split())
xxx = list(map(int, input().split()))
yyy = list(map(int, input().split()))
ab = defaultdict(set)
coordinates = set()
for x in xxx:
if x < yyy[0] or yyy[-1] < x:
continue
i = bisect(yyy, x)
a = x - yyy[i - 1]
b = yyy[i] - x
ab[a].add(b)
coordinates.add(b)
# Bitは1-indexで作っているが、今回、既存の座標に加えて"0"も取る必要があるので、全体を1ずらす
cor_dict = {b: i for i, b in enumerate(sorted(coordinates), start=2)}
cdg = cor_dict.get
MOD = 10 ** 9 + 7
bit = Bit(len(coordinates) + 1, MOD)
bit.add(1, 1)
for a in sorted(ab):
bbb = sorted(map(cdg, ab[a]), reverse=True)
for b in bbb:
bit.add(b, bit.sum(b - 1))
print(bit.sum(bit.size))
答えは $10^9+7$ で割った結果で出力するが、今回の問題では（超えはするものの）そこまで過剰に値が爆発することはない。
そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。
割り算遅いっすね。いや、どちらかというと多倍長が（表面上は何の工夫もせずに書ける割に）高速なのか。
