−目次

AtCoder Beginner Contest 155 D～F問題メモ
- D - Pairs
  - 問題
  - 解法
- E - Payment
  - 問題
  - 解法
- F - Perils in Parallel
  - 問題
  - 解法

AtCoder Beginner Contest 155 D～F問題メモ

AtCoder Beginner Contest 155

アルストツカに栄光あれ

D - Pairs

問題

$N$ 個の整数 $A_1,A_2,...,A_N$ がある
ここから2個選んで積をとってできる $\dfrac{N(N-1)}{2}$ 個の整数の内、 $K$ 番目に小さいものを求めよ
$2 \le N \le 2 \times 10^5$
$-10^9 \le A_i \le 10^9$

解法

実装がちょっと面倒な二分探索。

このように、 $X$ 個中の $K$ 番目を求めたいが、 $X$ が巨大すぎて全部を実際に計算してられない問題は、「答えが $a$ だとして、積が $a$ 以下となるペアが $K$ 個以上できるか？」をチェックする二分探索で求められることがある。（ペアが $K$ 個以上できる最小の $a$ が答えとなる）

まず問題を仮に $A_i$ が全て正として単純化し「積が $M$ 以下となるペアが $K$ 個以上できるか」を判定する方法を説明する。

積が $M$ 以下のペアの個数は、ペアの一方を $A_i$ と固定するともう一方は $\dfrac{M}{A_i}$ 以下（切り捨て）なので、各 $i$ についてこれを求めて合計すればよい。

これは $A_i$ をあらかじめ昇順ソートしておくことで、尺取りまたは二分探索で求めることができる。

各 $i$ について、 $A_i$ とペアになると $M$ を超過する最小の $A_j$ の位置 $j$ を尺取りで探索する。

$i$ が大きい方が $j$ は小さくなる。従って、 $i$ を大→小、 $j$ を小→大で動かすと、 $j$ は $i$ のループごとにリセットせず、全体で1回 $A$ を走査すればよいことを利用する。

M = 12               凡例
A   1  2  3  4  6    o: チェックしてM以下と判明
i               !    *: M以下にならない最小のj（jの現在位置）
j   o  o  *          v: 既にK以下と判明しているためチェックの必要なし
                 
i            !       ↖Ai = 6 のとき、2個    
j   v  v  o  *       ←Ai = 4 のとき、3個

i         !
j   v  v  v  o  *      Ai = 3 のとき、4個

i      !
j   v  v  v  v  o  *   Ai = 2 のとき、5個

i   !
j   v  v  v  v  v  *   Ai = 1 のとき、5個  → 計 19個が積が12以下

※これは(a,a)など同じ要素を選んでいたり、(a,b)と(b,a)を区別した上での数なので、この問題の定義におけるペア数とは異なる。が、後述の方法で簡単に求められる。

結果、積が12以下であるペアが8個と判明したとすると、 $K \gt 8$ であれば答えは12より大きく、 $K \le 8$ なら答えは12以下である。

類題: E - Handshake

しかし、今回は負の数も絡むというのが厄介で、

ペアの一方が正の場合は、もう一方も大きくなるほど積も大きくなる
ペアの一方が負の場合は、もう一方は小さくなるほど積は大きくなる

このため、尺取りや二分探索がそのままでは使えず、場合分けが必要となる。

$A_i$ を正の要素と負の要素に分けた数列を $A$ と $B$ とし、昇順にソートしておく。（0は捨て置く）

負の要素は $|A| \times |B|$ 個、正の要素は $\dfrac{|A|(|A|-1)}{2} + \dfrac{|B|(|B|-1)}{2}$ 個、それ以外は0なので、 $K$ の値によって答えが正か負か0かはわかる。

負の場合

ペアの正負は(負, 正)となる。負の方 $x$ を固定し、正の数列 $A$ に $\dfrac{a}{x}$ 「以上」となる数がいくつあるかを尺取りで求めていけばよい。

絶対値が大きいほど小さい数である、という点に注意。

正の場合

$A,B$ それぞれ、同じ方から2つ選べばよい。組合せなので「同じ要素は選べない」「(a,b)と(b,a)は同じ」ことに留意する必要がある。

とはいえ、まずは気にせず全て数えてしまった方が楽なので数える。

その後「数列に含まれる $\sqrt{a}$ 以下の値の数だけ同じ要素が選ばれているので引く」「残る値は全て2回ずつ同じペアが数えられているので、2で割る」とすると、正しい値となる。

境界に注意

$\dfrac{a}{x}$ を整数に丸める際の方向
- 小数のままでもいいのだが、誤差が発生するとヤなのと、一般に型を揃えた方が高速に動作する場合が多い
「以下」か「未満」か

実装においては、これらの丸める方向のために1だけズレた、みたいなことが発生しやすい。

特に負の数では、int(-2.5) はどちらに切り捨てられるか、など言語仕様にも絡んでくる。（Pythonでは絶対値の小さい方に丸められ、-2となる）

何か、混乱しない考え方みたいなのはないだろうか……。とりあえずこの辺に注意して実装する必要がある。

Pythonでは

計算量を最悪ケースで考えると二分探索は全体で $O(N \log^2{N})$ 、尺取りでは $O(N \log{N})$ となり、尺取りの方が速い。

実際、判定に二分探索を用いる方法では、PyPyを使ってもTLEが解消できないケースがあった。

二分探索はbisectモジュール一発で楽なのだが、尺取りでの書き方も覚えておいた方がよい。

また、NumPyでは複数の値を一気に二分探索できる searchsorted() があるので、そちらを使ってもよい。

Python実装例

        
          
          
              
              from bisect import bisect
 
 
def check_neg(m, k, pos, neg, len_pos):
    less = 0  # m 未満になるペア数
    j = 0
    for a in neg:
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if len_pos == j:
            break
        less += len_pos - j
    return less < k
 
 
def check_pos(m, k, pos, neg, len_pos, len_neg):
    less_eq = 0  # m 以下になるペア数
    j = 0
    for i in range(len_pos - 1, -1, -1):
        a = pos[i]
        d = m // a
        while j < len_pos and pos[j] <= d:
            j += 1
        if j == len_pos:
            less_eq += len_pos * (i + 1)
            break
        less_eq += j
 
    j = 0
    for i in range(len_neg - 1, -1, -1):
        a = neg[i]
        d = m // a
        while j < len_neg and neg[j] <= d:
            j += 1
        if j == len_neg:
            less_eq += len_neg * (i + 1)
            break
        less_eq += j
 
    m_sqrt = int(m ** 0.5)
    less_eq -= bisect(pos, m_sqrt)
    less_eq -= bisect(neg, m_sqrt)
 
    less_eq //= 2
 
    return less_eq < k
 
 
def solve(n, k, aaa):
    pos = [a for a in aaa if a > 0]
    neg = [a for a in aaa if a < 0]
    len_pos = len(pos)
    len_neg = len(neg)
    neg_mul = len_pos * len_neg
    pos_mul = len_pos * (len_pos - 1) // 2 + len_neg * (len_neg - 1) // 2
    if neg_mul >= k:
        l = -(10 ** 18)
        r = 0
        while l + 1 < r:
            m = (l + r) // 2
            if check_neg(m, k, pos, neg, len_pos):
                l = m
            else:
                r = m
        return l
    elif n * (n - 1) // 2 - pos_mul >= k:
        return 0
    else:
        k -= n * (n - 1) // 2 - pos_mul
        l = 0
        r = 10 ** 18
        neg = [-a for a in neg]
        neg.reverse()
        while l + 1 < r:
            m = (l + r) // 2
            if check_pos(m, k, pos, neg, len_pos, len_neg):
                l = m
            else:
                r = m
        return r
 
 
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(n, k, aaa))

            

        
      

E - Payment

問題

ある国には、通貨として1円、10円、100円、……、 $10^{\infty}$ 円玉がある
お店で $N$ 円の品物を購入したとき、「支払う硬貨の枚数」と「お釣りとして受け取る硬貨の枚数」の合計を最小化せよ
$1 \le N \le 10^{1000000}$

解法

実生活でもよくやるやつ。300円なら100円玉×3で払うけど、800円なら1000円札出して100円玉×2受け取った方が楽、みたいな。

すると、各桁につき、有効な出し方はある程度制限されてくる。

ぴったり出す
1枚多く出す
出さない

ただ、「出さない」を選択できるのは上位桁で1枚多く出しているときのみ、など、それぞれを取れる「状態」がある。

上の桁からDPで決めていくことを考えると、いろいろな $N$ で試した結果、状態は以下の2つに集約できる。

ぴったり出している状態（ぴ）
上位桁で1枚多く出している状態（超）

遷移は、以下のケースが考えられる。現在の桁の $N$ における数字を $d$ として、

（ぴ）→ぴったり出す→（ぴ） … d 枚
（ぴ）→1枚多く出す→（超） … d+1 枚
（超）→ぴったり出す→（ぴ） … d+1 枚
（超）→1枚多く出す→（超） … d+2 枚
（超）→出さない→（超） … 9-d 枚お釣り

（ぴ）は、 $N$ の最上位から完全にぴったり、というわけではなく、途中で1枚多い状態になって再度この状態になる、ということも可能である。引き算の筆算で、繰り下がり用の「1」を保持しているか否か、と言い換えた方がいいかも。

たとえば、N=28119を支払うとき、30120を払って2001返されるのが最適である。

    2  8  1  1  9
    3  0  1  2  0
   超 超 ぴ 超 超

この時、真ん中の1は、超過からぴったりに戻す、と考える。

既に上位の桁で $N$ 円以上であることは確定しているので、金額的には次の桁で「出さない」を選択することも可能だが、そうすると必ずくり下がりが発生し、お釣りが9枚になる桁が出来て得にならない。

    2  8  1  1  9      3桁目でぴったりの枚数出した後、4桁目で出さない
    3  0  1  0?     → 3桁目でお釣りが9枚となることが確定する
                    → なら最初から0枚で（超）のまま遷移させておいた方が8枚となり損しない

先頭の処理

N=99の時、100円出して1円お釣りが最適である。このように、 $N$ より1桁上位の硬貨を出して、いきなり（超）状態ではじめることも考慮に入れる必要がある。

末尾の処理

（超）の状態は、繰り下がり用の1を常に用意しているようなものなので、それが不要になったとき、および末尾が（超）で終わった場合については、お釣りに1枚プラスされる。

N   2  8  1  1  9  1  9
    3  0  1  2  0  2  0
   超 超 ぴ 超 超 超 超
   +3 +1 +1 +2 +0 +2 +0
        +1      +1    +1
        ↑      ↑    ↑
        こことこことここで、上位桁から引き継がれていた1がお釣りとして清算される

（超）の状態からぴったりまたは1枚多く出すと、その時点で上位桁からの繰り下がりが不要になり、1つ上位桁の硬貨のお釣りが1枚増える。

遷移では、これを下位桁の遷移時に+1することで、辻褄を合わせている。

        
              n = input()
precise = 0
over = 1
for d in n:
    d = int(d)
    new_over = min(precise + d + 1, over + d + 2, over + 9 - d)
    precise = min(over + d + 1, precise + d)
    over = new_over
over += 1
print(min(precise, over))

F - Perils in Parallel

問題

ON/OFFのスイッチが $N$ 個あり、 $i$ 番目のスイッチは座標 $A_i$ に置かれ初期状態は $B_i$ (0/1) である
取れる操作が $M$ 個あり、 $i$ 番目の操作では、区間 $[L_i, R_i]$ にあるスイッチのON/OFFを一斉に切り替える
全てのスイッチをOFFにすることが可能か判定し、可能なら操作手順も求めよ
$1 \le N \le 10^5$
$1 \le M \le 2 \times 10^5$
$1 \le A_i,L_i,R_i \le 10^9$

解法

区間に対する一律の操作は、隣接要素の差分に変換し、両端への2回の操作に置きかえるのがよくある解法。

今回の場合、スイッチを並べ、隣の要素のON/OFFと同じなら0、異なるなら1とした差分列を作る。

スイッチ         0   0   1   1   0   1   0   1
差分           0   0   1   0   1   1   1   1   1
↓                 |---------------|       この区間を反転
スイッチ         0   1   0   0   1   1   0   1
差分           0   1   1   0   1   0   1   1   1

差分において、反転区間の両端の0/1のみが切り替わっているのがわかる

で、差分を全て0にできれば、スイッチは全て同じ状態となっている。そのままでは全て“0”か“1”かわからないので、元のスイッチ列の先頭か末尾にダミーで“0”を入れておくと、“0”となっていることが保証できる。

下準備

スイッチを座標 $A_i$ の昇順に並べ、indexを振りなおす。ON/OFF状態 $B_i$ も、連動して並べ替えておく。

区間 $[L_i, R_i]$ を、座標ではなくスイッチのindex（何番目から何番目のスイッチを切り替えるのか）に置きかえ、 $[l_i, r_i)$ の形にしておく。二分探索が使える。

$B$ に、両端にダミーの“0”を追加した上で隣接要素の差分をとり、 $C$ とする。

さて、これで各操作は「 $C_{li},C_{ri}$ の0/1を切り替える」という処理に変わり、これを上手く選んで $C$ を全て0にすればよいということになった。

入力例1
A スイッチ座標       5    8   10
B スイッチON/OFF     1    0    1
C 差分            1    1    1     1
操作1             *               *
操作2             *    *
操作4                  *    *          ※操作3は意味が無いので除外

操作の組合せの探索

ここからどうしようか倦ねる。

解説では、 $(l_i,r_i)$ を辺として結んだグラフから全域森を作るといいらしい。

全域森以外の辺は考えなくていいのかと思うが、一例を示せばいいので「全域木でできること」が示せるならそれでいい。

一応、ざっくりした理解としては、全域森以外の辺を採用すると閉路が出来るが、

i        0   1   2   3   4   5
操作1    *-----------*
操作2                *-------*
操作3    *---*
操作4        *---------------*

ここで、「閉路のどれか1つの操作」を行った結果は、「閉路のそれ以外の全ての操作」を行った結果と一致する。今回は特に操作回数の最小化などは求められていないので、等価なものがあるなら考慮から省いてよい。

さて、木構造に辺を絞ると、ある辺（に相当する操作）が必要かどうか、考えやすくなる。

全域森の1つの木 $T$ に含まれる $C_i$ のXORを $S_T$ とすると、操作によって、 $S_T$ は変化しない。（常に $T$ 内の2つに対して操作を行うため）

よって、 $S_T=1$ である木が1つでもあれば、その木に含まれる $C_i$ の全てを0にすることは不可能であり、全体としても不可能である。

逆に $S_T=0$ なら、必ず全てを0にすることができる。

手順としては、適当に根を決め、葉から順に $C_i$ が1なら親 $j$ と結ばれる辺を採用し、 $C_i,C_j$ を反転させる、を繰り返せばよい。

$S_T$ も、あらかじめ求めずとも、最終的に根の $C_i$ が1であれば $S_T=1$ であったとわかる。

        
          
          
              
              import sys
from bisect import bisect_left, bisect
 
sys.setrecursionlimit(10 ** 5 + 5)
 
 
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
 
 
def solve(n, m, aaa, bbb, lll, rrr):
    aaa, bbb = map(list, zip(*sorted(zip(aaa, bbb))))
    ccc = [bbb[0]] + [b0 ^ b1 for b0, b1 in zip(bbb, bbb[1:])] + [bbb[-1]]
    cords = [set() for _ in range(n + 1)]
    uft = UnionFind(n + 1)
    for i, (l, r) in enumerate(zip(lll, rrr), start=1):
        li = bisect_left(aaa, l)
        ri = bisect(aaa, r)
        if li == ri or uft.find(li, ri):
            continue
        cords[li].add((ri, i))
        cords[ri].add((li, i))
        uft.union(li, ri)
 
    use_cords = set()
 
    def dfs(v, p):
        res = ccc[v]
        for u, cord in cords[v]:
            if u == p:
                continue
            ret = dfs(u, v)
            if ret == 1:
                use_cords.add(cord)
            ccc[u] = 0
            res ^= ret
        return res
 
    for v in range(n + 1):
        if ccc[v]:
            res = dfs(v, -1)
            if res == 1:
                print(-1)
                return
 
    print(len(use_cords))
    print(*sorted(use_cords))
 
 
inp = list(map(int, sys.stdin.buffer.read().split()))
n, m = inp[:2]
aaa = inp[2:2 * n + 2:2]
bbb = inp[3:2 * n + 2:2]
lll = inp[2 * n + 2::2]
rrr = inp[2 * n + 3::2]
solve(n, m, aaa, bbb, lll, rrr)

            

        
      