差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2018/08/27] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/17] – [解法] ikatakos
@@ 行 1: / 行 1: @@
-======AtCoder Regular Contest 101======
+======AtCoder Regular Contest 101 C,D,F問題メモ======
 [[https://beta.atcoder.jp/contests/arc101|AtCoder Regular Contest 101]]
@@ 行 224: / 行 224: @@
 </sxh>
+===== E - Ribbons on Tree =====
+[[https://beta.atcoder.jp/contests/arc101/tasks/arc101_c|E - Ribbons on Tree]]
+==== 問題 ====
+==== 例 ====
+==== 解法 ====
+<sxh python>
+</sxh>
+===== F - Robots and Exits =====
+[[https://beta.atcoder.jp/contests/arc101/tasks/arc101_d|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つについて独立に座標圧縮をしておく。
+（実際には、座標圧縮は「右までの距離の集合」のみでよいが、説明上、左も行っているものとする）
+例えば左右の出口までの距離の集合が以下のようだったとして、
+  左  右
+   3
+   2
+   4
+   1
+   4
+   2
+次元座標上にプロットすると以下の感じになる。
+  右 4|       o  o
+|    o
+|       o     o
+|          o
+|
+     --------------------
+  1  2  3  4  左
+$(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。
+上か右のみに移動することになる。
+実際の移動ではなく、最大距離な点に注意。(左→左→右)の移動は(2,1)でなく(2,0)である。(左→左→右→右→右)ではじめて、(2,1)となる。
+例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。
+  右 4|       o  o
+|    o
+| R  R【o】   o      Lを通過: 左から出る
+|       L  o         Rを通過: 右から出る
+|       L
+     --------------------
+  1  2  3  4  左
+これを踏まえて、以下のDPを考える。
+  * $DP[i][j] = (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数
+  * $DP[0][0] = 1$
+これは何を示すかというと、
+「左までの距離が $i$ のロボットに関して、右までの距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す」場合の組合せ数を示している。
+$i-1$ 以前のロボットについては通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を数え上げる。
+ただし $j$ については、必要無いのに無駄に右に進むことはせず、
+ロボットを落とすのに必要最小限の距離についてのみ記録するとする。
+$i=1$ のロボットを左から出すとき、右には1つも動かなくていい。右から出すとき、右に3動く必要がある。
+座標上の動きで解釈すると、
+（"左"座標の正の向きが"右"なのでややこしいが、座標上の動きを説明するときは、上移動と右移動という言葉を用いる）
+$(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。
+  右 4|       o  o
+  j  3| ,→1
+| |     o     o
+| |        o
+| 1→1
+     --------------------
+  1  2  3  4  左(i)
+$i=2$ のロボットのうち、$(2,4)$ について右から出そうと思えば、
+「(1,0)から4つ上がる」「(1,3)から1つ上がる」の経路がある。これは、(1,3)を左右どちらに落としたかに相当する。
+  右 4|     【2】o
+|   [1]            【 】: 着目中の座標
+|   [ ] o     o     [ ] : 遷移元とできる範囲
+|   [ ]    o
+| 1 [1]
+     --------------------
+  1  2  3  4  左
+しかし、$(2,2)$ については、直前で(1,3)を経由している経路については既に出口は右と確定しているので、
+(1,3)の通り数の中に既に織り込まれていると解釈できる。
+よって、遷移元とすることが可能な範囲は、$(1,0),(1,1)$ に限られる。
+  右 4|       2  o
+|    1              [ ]: 遷移元とできる範囲
+|     【1】   o
+|   [ ]    o
+| 1 [1]
+     --------------------
+  1  2  3  4  左
+また、「全て左から出す」「(1,3)のロボットは右から出したが、(2,4)は左から出す」ということを表現するため、
+$i=1$ の結果はそのまま $i=2$ にスライドさせる。
+  右 4|       2  o
+|    1【1】
+|       1     o
+|          o
+| 1  1【1】
+     --------------------
+  1  2  3  4  左
+$i=3$ 以降も同様に、「$(i,j)$ のロボットを右から出すためには
+$(i-1, 0)～(i-1,j-1)$ から遷移できる（これらの和だけの経路がある）」として
+座標を埋めていくと、以下のような感じになる。
+  右 4|       2  5  5
+|    1  1  1  1
+|       1  1  3
+|          1  1
+| 1  1  1  1  1
+     --------------------
+  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, 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))
+</sxh>
+答えは $10^9+7$ で割った結果で出力するが、今回の問題では（超えはするものの）そこまで過剰に値が爆発することはない。
+そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。
+割り算遅いっすね。いや、どちらかというと多倍長が（表面上は何の工夫もせずに書ける割に）高速なのか。