−目次

AtCoder Beginner Contest 356 D,E,F,G問題メモ
- D - Masked Popcount
  - 問題文
  - 制約
  - 解法
- E - Max/Min
  - 問題文
  - 制約
  - 解法
- F - Distance Component Size Query
  - 問題文
  - 制約
  - 解法
- G - Freestyle
  - 問題文
  - 制約
  - 解法

AtCoder Beginner Contest 356 D,E,F,G問題メモ

AtCoder Beginner Contest 356

D - Masked Popcount

問題文

整数 $N,M$ が与えられるので、 $\displaystyle \sum_{k=0}^{N}$ $\rm{popcount}$ $(k \& M)$ を $998244353$ で割った余りを求めてください。
- ただし、 $\mathbin{\&}$ はビット単位 $\rm{AND}$ 演算を表します。

制約

$N$ は $0$ 以上 $2^{60}$ 未満の整数
$M$ は $0$ 以上 $2^{60}$ 未満の整数

解法

2進数で桁毎に考える。

$M$ で'1'が立っている桁において、 $k$ でも'1'が立っているような $0 \le k \le N$ の全ての $k$ は、1ずつ答えに寄与する。

M    100101

 ..??1?????    ① 0≦k≦N でこんな k の個数

 ..?????1??    ② 0≦k≦N でこんな k の個数

 ..???????1    ③ 0≦k≦N でこんな k の個数
   
答え＝①+②+③
（※重複していてもよい、たとえば 100100 は①と②で2回数える）

なので、他の桁のことは気にせず、「 $d$ 桁目に1が立つような、 $0 \le k \le N$ となる $k$ は何個ある？」が独立に求められればいい。

a) d 桁目より上位の桁で、既に k＜N が確定している場合
       d
N  110110100

k  ????1????

前半の????の列に来るのは、0000～1100 の13通り。（N を d だけ右bitshiftした値）
それぞれに対し、後半の????の列には何を置いてもよいので0000～1111の16通りの数が来る。
→ 13 * 16 = 208 通り

b) d 桁目では k＜N は確定してない場合
       d
N  110110100

k  11011????

d以上の桁はNと一致している。そのうえで k の d 桁目が1なので、
まず、N の d 桁目も 1 である必要がある。
あとは、それより下位の桁でNを超えないような k を数えればよい。
Nの下位d-1桁（????部分）を取り出した値 + 1（0を含むため）が答えとなる。
→ 0100 + 1 = 5通り

これを、各桁について合計したものが、最終的な答えとなる。

Python3

E - Max/Min

問題文

長さ $N$ の数列 $A=(A_1,\ldots,A_N)$ が与えられます。
$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor$ を求めてください。
- ただし、 $\lfloor x \rfloor$ は $x$ 以下の最大の整数を表します。例えば、 $\lfloor 3.14 \rfloor=3$ 、 $\lfloor 2 \rfloor=2$ です。

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq A_i \leq 10^6$

解法

$A_i$ が大きい方（分子）になるような全ての $(j,i)$ ペアの答えを求めたい。（ひとまず、 $A_i$ は $A$ の中に1つしか無いとする）

すると、答えは以下のような範囲の合計となる。

例 A = (1 2 2 2 5 5 15 22)    Ai=22 について考える

         1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
  個数   1  3        2                             1

商1以上 |1--3--------2-----------------------------1---------------------|
商2以上 |1--3--------2------------------|
商3以上 |1--3--------2------|
商4以上 |1--3--------2|
商5以上 |1--3------|
商6以上 |1--3---|
商7以上 |1--3---|
商8以上 |1--3|
  :
商11以上|1--3|
商12以上|1|
  :
商22以上|1|

22が分子に来るようなペアにおける商の合計:
  1*22 + 3*11 + 2*4 + 1*1 = 64

たとえば商が4となる $A_j=5$ は、ちゃんと「商1以上～商4以上」の4回でそれぞれ足されている。 $A$ の中に2個あるので、2個ずつ足されている。
商を1段ずつに分解していると考える。

これ、商が小さいうちは、横に見て累積和で管理した方が効率がよい。
一方、商が大きい時は、対象範囲が同じものが続くので、縦にまとめて合計した方がよい。

なので、 $r = \lfloor \sqrt{A_i} \rfloor$ として、商 $r$ までは横に、以降の部分は縦に見るようにすると、 $A_i$ あたり計算量 $O(r)$ で答えが求められる。

以下を前計算しておくと、

$\mathrm{CNT}[i]=A$ の中の $i$ の個数
$\mathrm{ACC}[i]=$ ↑の累積和

$k=1～r$ についてそれぞれ横と縦で足し合わせて、重複する長方形部分を引けばよい。

横に合計: $\mathrm{ACC}[A_i // k]$
縦に合計: $\mathrm{CNT}[k] \times (A_i // k)$
重複部分: $\mathrm{ACC}[r] \times r$

$O(N \sqrt{A_{\max}})$ となる。

なお、 $A$ に同じ値が複数ある場合は、余分なペアを除く必要がある。
同じ値が $c$ 個あるような $A_i$ それぞれで、 $\frac{c(c+1)}{2}$ だけ余分に足されている。

Python3

F - Distance Component Size Query

問題文

整数 $K$ が与えられます。はじめ空である集合 $S$ に対して、次の $2$ 種類のクエリを順に $Q$ 個処理してください。
- '1 x'：整数 $x$ が与えられる。 $S$ に $x$ が含まれているならば、 $S$ から $x$ を取り除く。そうでないならば、 $S$ に $x$ を追加する。
- '2 x'： $S$ に含まれる整数 $x$ が与えられる。 $S$ に含まれる数を頂点とし、差の絶対値が $K$ 以下であるような数の間に辺を張ったグラフにおいて、 $x$ が属する連結成分の頂点数を出力する。

制約

$1 \leq Q \leq 2\times 10^5$
$0 \leq K \leq 10^{18}$
各クエリにおいて、 $1\leq x \leq 10^{18}$

解法

数直線をイメージする。

クエリ1で数直線上の $x$ の位置にコマを置いたり除いたりする。
$K$ 以下の距離にあるコマ同士は同じグループとしたとき、クエリ2では、指定されたコマの属するグループサイズを答える。

そう考えると、各グループは数直線上で連続した区間のコマとなる。

順序を保ったまま、要素を挿入・削除・二分探索できる SortedSet があれば、状態を管理できる。

$\mathrm{ALL}$ ：現在の全てのコマの位置の集合を管理するSortedSet
$\mathrm{LEFT}$ ：現在の「各グループで最も左端のコマ」の位置の集合を管理するSortedSet
$\mathrm{RIGHT}$ ：現在の「各グループで最も右端のコマ」の位置の集合を管理するSortedSet

クエリ1では、 $x$ を挿入（削除）することで両隣のコマ $l,r$ とのグループ関係がどうなるかを、丁寧に場合分けして更新する。
（別々だったグループが統合される、左端だけ・右端だけ伸びる、 $x$ 単体の新たなグループができる、など）

更新には $l,x,r$ の情報だけがあればよく、 $l$ よりさらに左のコマなどは知らなくても更新できるのがポイント。

クエリ2では、LEFT,RIGHT を二分探索することで $x$ の属するグループの左端・右端がわかるので、それぞれのALL上の位置を求めることで要素数が分かる。

Python は sortedcontainer がライブラリに入ったので、こういった問題がかなり解きやすくなった。

Python3

        
          
          
              
              from sortedcontainers import SortedSet
 
q, k = map(int, input().split())
INF = 1 << 62
total = SortedSet([-INF, INF])
left = SortedSet([-INF, INF])
right = SortedSet([-INF, INF])
buf = []
for _ in range(q):
    op, x = map(int, input().split())
    if op == 1:
        i = total.bisect_left(x)
        if total[i] == x:
            l = total[i - 1]
            r = total[i + 1]
            total.remove(x)
            if r - l <= k:
                pass
            elif x - l > k:
                if r - x > k:
                    left.remove(x)
                    right.remove(x)
                else:
                    left.remove(x)
                    left.add(r)
            elif r - x > k:
                right.remove(x)
                right.add(l)
            else:
                left.add(r)
                right.add(l)
        else:
            l = total[i - 1]
            r = total[i]
            total.add(x)
            if r - l <= k:
                pass
            elif x - l > k:
                if r - x > k:
                    left.add(x)
                    right.add(x)
                else:
                    left.remove(r)
                    left.add(x)
            elif r - x > k:
                right.remove(l)
                right.add(x)
            else:
                left.remove(r)
                right.remove(l)
    else:
        li = left.bisect_right(x) - 1
        ri = right.bisect_left(x)
        l = left[li]
        r = right[ri]
        tli = total.index(l)
        tri = total.index(r)
        ans = tri - tli + 1
        buf.append(ans)
 
print('\n'.join(map(str, buf)))

            

        
      

G - Freestyle

問題文

高橋くんは $N$ 種類の泳ぎ方ができます。
高橋くんが $i$ 種類目の泳ぎ方で泳ぐと、 $1$ 秒あたり体力を $A_i$ 消費して $B_i$ [m] 進みます。
$Q$ 個のクエリに答えてください。そのうち $i$ 個目は次の通りです。
- 消費する体力の合計を $C_i$ 以下にして $D_i$ [m] 進むことができるか判定し、進める場合は必要な最小の秒数を求めよ。
ただし、高橋くんは泳ぎ方を自由に組み合わせることができ、泳ぎ方を変える体力と時間は無視できます。
- ※各泳ぎ方で泳ぐ時間は小数でもよい

制約

$1 \le N \le 2 \times 10^5$
$1 \le A_i,B_i \le 10^9$
$1 \le Q \le 2 \times 10^5$
$1 \le C_i,D_i \le 10^9$

解法

泳ぎ方の点 $(A_i,B_i)$ をグラフにプロットして、意味を考えてみる。

「原点から、各泳ぎ方の点へのベクトル」が、1秒間、その泳ぎ方で進むことを表す。
2秒、3秒、泳いだらベクトルが2倍、3倍に伸びていくイメージ。

「ベクトルの傾き」が体力効率を示す。
各泳ぎ方の点の $y$ 座標が速度（時間効率）を示す。クエリで秒数を最小化する上ではなるべく速い（高い位置にある）泳ぎ方を使いたい。

泳ぎ方の点同士を結ぶ線分上の点は、「1秒間内でその2つの泳ぎ方を組み合わせる」ことを表す。
体力効率を上げる代わりに速度を落とす（または逆）みたいな選択ができる。
泳ぐ時間は小数でもよいので、線分上の任意の泳ぎ方ができる。

3つ以上の泳ぎ方を組み合わせるのは、「 $i,j$ を結ぶ線分上の点と、別の泳ぎ方の点 $k$ の間」に同様に線分を引くことを繰り返せば表現できる。
（結果的に、3つ以上を組み合わせた泳ぎ方は、下記の“意味のある泳ぎ方”になることはないが）

ある泳ぎ方に対し、体力効率も時間効率も劣る泳ぎ方は採用する意味が無いので、意味のある泳ぎ方は凸包みたいな形になる。
ただし、上側凸包でよく、さらに $y$ 座標は狭義単調増加する範囲で良い。

まずこの部分的な凸包を構築する。

クエリが来たら、

最大体力効率より高い体力効率を求められるクエリは不可
意味のある泳ぎ方の中で最低体力効率（必然的に最速）以下の体力効率しか求められないクエリは、最速の泳ぎ方

その間にあるものは、凸包と、原点→クエリ点を結ぶ線の交点が、ちょうどよい体力効率の1秒当たりの泳ぎ方を示す。

Python3

        
          
          
              
              from collections import defaultdict
 
 
def ccw(ax, ay, bx, by, cx, cy):
    """
        C         :1
    A------>B  C  :0
        C         :-1
    """
    dx1 = bx - ax
    dy1 = by - ay
    dx2 = cx - ax
    dy2 = cy - ay
    if dy1 * dx2 > dy2 * dx1:
        return -1
    if dx1 * dy2 > dy1 * dx2:
        return 1
    if dx1 * dx2 < 0 or dy1 * dy2 < 0:
        return 1
    if dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2:
        return -1
    return 0
 
 
def intersection(x1, y1, x2, y2, x3, y3):
    """
    2つの直線が交わる座標を求める関数
 
    引数:
      x1, y1: 1つ目の直線の1つ目の点の座標
      x2, y2: 1つ目の直線の2つ目の点の座標
      x3, y3: 2つ目の直線の1つ目の点の座標 (原点(0, 0))
    返り値:
      交点の座標 (x, y) のタプル。交差しない場合は (None, None) を返す。
    """
 
    # 1つ目の直線の傾きと切片を求める
    dx1 = x2 - x1
    dy1 = y2 - y1
    if dx1 == 0:
        slope1 = None
    else:
        slope1 = (y2 - y1) / (x2 - x1)
    intercept1 = y1 - slope1 * x1
 
    # 2つ目の直線の傾きと切片を求める
    dx2 = x3
    dy2 = y3
    if dx2 == 0:
        slope2 = None
    else:
        slope2 = y3 / x3
    intercept2 = 0
 
    # 2つの直線が平行かどうか判定する
    if slope1 == slope2:
        return None, None
 
    # 交点のx座標を求める
    if slope1 is None:
        x = x3
    elif slope2 is None:
        x = x1
    else:
        x = (intercept2 - intercept1) / (slope1 - slope2)
 
    # 交点のy座標を求める
    if slope1 is None:
        y = slope2 * x + y3
    elif slope2 is None:
        y = slope1 * x + y1
    else:
        y = slope1 * x + intercept1
 
    # 交点の座標を返す
    return x, y
 
 
n = int(input())
points = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    points[a] = max(points[a], b)
 
uch = [(0, 0)]  # upper convex hull
for a in sorted(points.keys()):
    b = points[a]
    if uch[-1][1] >= b:
        continue
    while len(uch) >= 2:
        if ccw(uch[-2][0], uch[-2][1], uch[-1][0], uch[-1][1], a, b) == 1:
            uch.pop()
        else:
            break
    uch.append((a, b))
 
uch.pop(0)
 
pa, pb = uch[0]
qa, qb = uch[-1]
m = len(uch)
 
q = int(input())
buf = []
for _ in range(q):
    c, d = map(int, input().split())
    if qb * c >= qa * d:
        buf.append(d / qb)
        continue
    if pb * c < pa * d:
        buf.append(-1)
        continue
    l = 0
    r = m
    while l + 1 < r:
        mid = (l + r) // 2
        ra, rb = uch[mid]
        if rb * c > ra * d:
            l = mid
        else:
            r = mid
    x, y = intersection(uch[l][0], uch[l][1], uch[r][0], uch[r][1], c, d)
    buf.append(d / y)
 
print('\n'.join(map(str, buf)))

            

        
      