差分
このページの2つのバージョン間の差分を表示します。
次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2018/08/27] – 作成 ikatakos | programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======AtCoder Regular Contest 101====== | + | ======AtCoder Regular Contest 101 C, |
[[https:// | [[https:// | ||
行 99: | 行 99: | ||
A = 3 5 5 5 6 7 7 8 | A = 3 5 5 5 6 7 7 8 | ||
| | ||
- | d = 5 を確認 | + | d = 5 をチェック |
d以上: x o o o o o o o → |A|/2=4 個以上 | d以上: x o o o o o o o → |A|/2=4 個以上 | ||
- | d = 6 を確認 | + | d = 6 をチェック |
d以上: x x x x o o o o → 4個以上 | d以上: x x x x o o o o → 4個以上 | ||
- | d = 7 を確認 | + | d = 7 をチェック |
d以上: x x x x x o o o → 4個未満 | d以上: x x x x x o o o → 4個未満 | ||
| | ||
行 112: | 行 112: | ||
===今回の問題で必要な情報=== | ===今回の問題で必要な情報=== | ||
- | さて、この性質を今回の問題に適用すると、ある $d$ についてチェックするとき、 | + | さて、この性質を今回の問題に適用して2分探索で答えを求めるとき、ある $d$ が、$m$ の中央値以上か未満か判定する必要がある。 |
* 全ての連続部分列の中央値のうち、$d$ 以上になるものの個数が、$|m|/ | * 全ての連続部分列の中央値のうち、$d$ 以上になるものの個数が、$|m|/ | ||
- | を求めればよい。$|m|=$連続部分列の個数$=\frac{|A||A+1|}{2}$ である。 | + | を求めればよい。$|m|=$連続部分列の個数$=\frac{|A||A+1|}{2}$ |
- | かといってこれはこれで扱いにくい。 | + | しかし、こうしたところで「全ての連続部分列の中央値」をどうやって求めるんだという話になる。1つ1つ求めていくと当然TLE。 |
- | しかし、ここで「中央値そのもの」の値は必要なく「中央値が $d$ 以上になるかどうか」だけの情報が必要であることに着目する。 | + | ここで「中央値そのもの」の値は必要なく「中央値が $d$ 以上になるかどうか」だけの情報が必要であることに着目する。 |
ある長さ $k$ の連続部分列 $S_{l,r}$ において、$d$ 以上の値が $|k|/2$ 個以上含まれるなら、その中央値は $d$ 以上である。 | ある長さ $k$ の連続部分列 $S_{l,r}$ において、$d$ 以上の値が $|k|/2$ 個以上含まれるなら、その中央値は $d$ 以上である。 | ||
行 138: | 行 138: | ||
* 連続部分列のうち「$d$ 以上の要素の個数 $\ge d$ 未満の要素の個数」となるものの個数 | * 連続部分列のうち「$d$ 以上の要素の個数 $\ge d$ 未満の要素の個数」となるものの個数 | ||
- | を求めればよいことがわかった。しかしこれを1つ1つ確認するわけにもいかない。 | + | を求めればよいことがわかったので、この条件を高速に判定する方法を考える。 |
- | まず、ある部分列 $S_{l,r}$ が条件を満たすか判定する方法を考えると、要素を置き換えて和を計算する方法だと簡単に求めることができる。 | + | これは、ある部分列 $S_{l,r}$ が条件を満たすか判定する方法を考えると、要素を置き換えて和を計算する方法だと簡単に求めることができる。 |
つまり、あらかじめ $A$ の要素を $d$ 以上なら1、未満なら-1に置き換えると、 | つまり、あらかじめ $A$ の要素を $d$ 以上なら1、未満なら-1に置き換えると、 | ||
行 162: | 行 162: | ||
累積和 $R$ を順番に処理する。処理中の累積和の値を $p$ とすると | 累積和 $R$ を順番に処理する。処理中の累積和の値を $p$ とすると | ||
- | * sum(p): $p$ を $R_r$ と見做して、自身より左に出てきた、自身以下の値の個数 | + | * sum(p): $p$ を $R_r$ と見做して、自身より左に出てきた、自身以下の値の個数($r$ とペアになれる $l$ の個数) |
* add(p,1): $p$ を $R_{l-1}$ と見做して、以降の処理のために自身の存在を記録 | * add(p,1): $p$ を $R_{l-1}$ と見做して、以降の処理のために自身の存在を記録 | ||
この2処理を順次行うと、sum(p)の合計が、条件を満たす $(l,r)$ の組の個数となる。(ただし累積和は負にもなるが、BITの処理を行う上でpは正である必要があるため、あらかじめNなどを加算して調整しておく) | この2処理を順次行うと、sum(p)の合計が、条件を満たす $(l,r)$ の組の個数となる。(ただし累積和は負にもなるが、BITの処理を行う上でpは正である必要があるため、あらかじめNなどを加算して調整しておく) | ||
- | これにより、仮定した中央値 $d$ が、真の中央値以上か未満か判定し、2分探索で答えを求めることになる。 | + | これにより、$m$ の中央値が $d$ 以上か未満か判定し、2分探索で答えを求めることになる。 |
発想の転換が3回くらい必要な問題。 | 発想の転換が3回くらい必要な問題。 | ||
行 224: | 行 224: | ||
</ | </ | ||
+ | ===== E - Ribbons on Tree ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | |||
+ | ==== 例 ==== | ||
+ | |||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | ===== F - Robots and Exits ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 数直線上にロボットが $N$ 体、出口が $M$ 個 | ||
+ | * ロボットの座標は $x_1, | ||
+ | * 出口の座標は $y_1, | ||
+ | * 座標は全て異なる | ||
+ | * ロボットに対して、以下の2つの操作を好きな順序で何回でも繰り返せる | ||
+ | * 残る全てのロボットの位置を一斉に+1する | ||
+ | * 残る全てのロボットの位置を一斉に-1する | ||
+ | * ロボットが出口に重なると、そのロボットは取り除かれる | ||
+ | * 今、全てのロボットが取り除かれるまで操作を行った | ||
+ | * (ロボット1が出た出口, | ||
+ | * $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」というロボット①、②があったら、 | ||
+ | ①を左から出しつつ、②を右から出すことは出来ない。 | ||
+ | なぜなら、出す出口の左右を分けるにしても、まずは左右どちらかから一方を出さないといけないが、 | ||
+ | ①を左まで持ってったら②が既に左から出ているし、逆も然り。 | ||
+ | |||
+ | で、こういう条件が沢山あるのをまとめ上げるのに、2次元座標に変換して考える(解説pdf)。 | ||
+ | |||
+ | <wrap hi> | ||
+ | |||
+ | 例えば左右の出口までの距離の集合が以下のようだったとして、 | ||
+ | |||
+ | 左 右 | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | 2次元座標上にプロットすると以下の感じになる。 | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | | ||
+ | | ||
+ | 0| | ||
+ | | ||
+ | 0 1 2 3 4 左 | ||
+ | |||
+ | $(0,0)$ からスタートして、座標を「左右それぞれ移動させたことのある最大距離」と解釈して移動を行う。 | ||
+ | 上か右のみに移動することになる。 | ||
+ | |||
+ | 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | 2| R R【o】 | ||
+ | | ||
+ | | ||
+ | | ||
+ | 0 1 2 3 4 左 | ||
+ | |||
+ | これを踏まえて、以下のDPを考える。 | ||
+ | |||
+ | * $DP[i][j]=$ 左出口までの距離が $i$ であるロボットまでを見て、最後に左に1つ進めるまでの右に進んだ最大距離が $j$ だった時の、出口の組の個数 | ||
+ | * $DP[0][0] = 1$ | ||
+ | |||
+ | ただし $j$ については、必要無いのに無駄に右に進むことはせず、 | ||
+ | ロボットを落とすのに必要最小限の距離についてのみ記録するとする。 | ||
+ | |||
+ | $i=1$ のロボットを左から出すとき、右には1つも動かなくていい。右から出すとき、右に3動く必要がある。 | ||
+ | |||
+ | 座標上の動きで解釈すると、 | ||
+ | (" | ||
+ | $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。 | ||
+ | |||
+ | 右 4| | ||
+ | j 3| ,→1 | ||
+ | 2| | | ||
+ | 1| | o | ||
+ | 0| 1→1 | ||
+ | | ||
+ | 0 1 2 3 4 左(i) | ||
+ | |||
+ | $i=2$ のロボットのうち、$(2, | ||
+ | 「(1, | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | | ||
+ | | ||
+ | 0| 1 [1] | ||
+ | | ||
+ | 0 1 2 3 4 左 | ||
+ | |||
+ | しかし、$(2, | ||
+ | (1, | ||
+ | |||
+ | よって、遷移元とすることが可能な範囲は、$(1, | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | | ||
+ | | ||
+ | 0| 1 [1] | ||
+ | | ||
+ | 0 1 2 3 4 左 | ||
+ | |||
+ | また、「全て左から出す」「(1, | ||
+ | $i=1$ の結果はそのまま $i=2$ にスライドさせる。 | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | | ||
+ | | ||
+ | 0| 1 1【1】 | ||
+ | | ||
+ | 0 1 2 3 4 左 | ||
+ | |||
+ | $i=3$ 以降も同様に、「$(i, | ||
+ | $(i-1, 0)~(i-1, | ||
+ | 座標を埋めていくと、以下のような感じになる。 | ||
+ | |||
+ | 右 4| | ||
+ | | ||
+ | | ||
+ | | ||
+ | 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に更新が可能である。 | ||
+ | |||
+ | <sxh python> | ||
+ | from bisect import bisect | ||
+ | from collections import defaultdict | ||
+ | |||
+ | |||
+ | class Bit: | ||
+ | def __init__(self, | ||
+ | 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(' | ||
+ | |||
+ | def lower_bound(self, | ||
+ | sum_ = 0 | ||
+ | pos = 0 | ||
+ | for i in range(self.depth, | ||
+ | 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, | ||
+ | yyy = list(map(int, | ||
+ | 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で作っているが、今回、既存の座標に加えて" | ||
+ | cor_dict = {b: i for i, b in enumerate(sorted(coordinates), | ||
+ | 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, | ||
+ | for b in bbb: | ||
+ | bit.add(b, bit.sum(b - 1)) | ||
+ | |||
+ | print(bit.sum(bit.size)) | ||
+ | </ | ||
+ | |||
+ | 答えは $10^9+7$ で割った結果で出力するが、今回の問題では(超えはするものの)そこまで過剰に値が爆発することはない。 | ||
+ | |||
+ | そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。 | ||
+ | |||
+ | 割り算遅いっすね。いや、どちらかというと多倍長が(表面上は)何の工夫もせずに書ける割に高速なのか。 | ||