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以下である。

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

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

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

$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実装例

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)

programming_algorithm/contest_history/atcoder/2020/0216_abc155.txt · 最終更新: 2020/02/21 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0