目次
AtCoder Beginner Contest 155 D～F問題メモ
アルストツカに栄光あれ
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() があるので、そちらを使ってもよい。
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)
