AtCoder Beginner Contest 168 E,F問題メモ
E - ∙ (Bullet)
問題
- $N$ 個の要素があり、$i$ 番目の要素は $A_i,B_i$ という2つのパラメータを持つ
- ここから1つ以上を選ぶが、選ばれたどの2つの要素 $(i,j)$ をとっても、以下の条件を満たしてはいけない
- $A_iA_j+B_iB_j=0$
- 選び方の個数を $\mod{10^9+7}$ で求めよ
- $1 \le N \le 2 \times 10^5$
- $-10^{18} \le A_i,B_i \le 10^{18}$
解法
今回の条件のような式が出てきたら、とりあえず移項して、左辺には $i$ だけ、右辺には $j$ だけみたいな形にしたい。
そうすれば、2個の関係でなく、単独の要素毎に考えられる可能性がある。
すると、$\dfrac{A_i}{B_i}=-\dfrac{B_j}{A_j}$ となった。 なので、$\dfrac{A_i}{B_i}$ ごとに要素数を数えておけば、その逆数の-1倍が「同時に選んではいけないペア」になるので、互いの個数がわかればパターン数も計算できる。
問題点が2つある。
- $A_i,B_i$ は0になり得るが、条件式の変形では $A_i,B_i$ で割るので、0の場合は別に計算が必要
- $A_i,B_i$ の範囲がでかいので、素直に割り算したら誤差で同じ要素を同じと判定できなくなるかも知れない
0の場合分け
$(A_i,B_i)=(0,0)$ の要素は、他のどの要素と同時に選ぶこともできない。ので、除いて考える。
「同時に選んではいけない」のであって、この要素のみを単独で選ぶのも1つの選び方となる点に注意。（見落としがち）
$(A_i,B_i)=(0, 非0)$ の要素は、$A_iA_j+B_iB_j=0+(非0 \times B_j)$ なので、これが0となるには $B_j=0$ が必要。
よって、$(A_i,B_i)=(0, 非0)$ と $(非0, 0)$ が同時に選んではいけないペアとなる。
値の同定方法
分子と分母の2数の形で持っておけばよい。最大公約数で割って既約分数化しておいて、また「$A_i$ は必ず正」となるようにすれば、同じ分数は同じ2数の組となる。
数え上げ
同時に選べない分数のペアが、一方は $p$ 個、もう一方は $q$ 個あったら、
- どちらも選ばない 1通り
- $p$ 個の方から1個以上好きなように選ぶ $2^p-1$ 通り
- $q$ 個の方から1個以上好きなように選ぶ $2^q-1$ 通り
上記の $2^p+2^q-1$ 通りの選び方がある。
これは他の選び方に影響したり、影響を受けたりすることはないので、ペアが複数あっても、かけあわせていけばよい。
最後に、ペアのいないのが $r$ 個残ったら、それは好きなように選べるので $2^r$ 通り。
これら全てを掛け合わせた結果には、ただし、「1つも選ばない」のも1通り数えられているので、1引く。
また、最初に言及したとおり「$(0,0)$ の要素を1つだけ選ぶ」のも可能なので、存在するならその要素数を加算する。
import sys
from collections import defaultdict
from math import gcd
MOD = 10 ** 9 + 7
n, *ab = map(int, sys.stdin.buffer.read().split())
ab_zero = 0
a_zero = 0
b_zero = 0
nonzero = defaultdict(int)
for a, b in zip(ab[0::2], ab[1::2]):
if a == 0 and b == 0:
ab_zero += 1
elif a == 0:
a_zero += 1
elif b == 0:
b_zero += 1
else:
g = gcd(a, b)
a //= g
b //= g
if a < 0:
a, b = -a, -b
if a == 0 and b < 0:
b = -b
nonzero[a, b] += 1
n -= ab_zero
# print(nonzero)
dame_pairs_pattern = 1
dame_pairs_cnt = 0
if a_zero > 0 and b_zero > 0:
dame_pairs_pattern *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
dame_pairs_cnt += a_zero + b_zero
checked = set()
for (a, b), cnt in nonzero.items():
if (a, b) in checked:
continue
if b < 0:
c, d = -b, a
else:
c, d = b, -a
if (c, d) in nonzero:
cnt2 = nonzero[c, d]
dame_pairs_pattern *= pow(2, cnt, MOD) + pow(2, cnt2, MOD) - 1
dame_pairs_pattern %= MOD
dame_pairs_cnt += cnt + cnt2
checked.add((c, d))
ans = dame_pairs_pattern * pow(2, n - dame_pairs_cnt, MOD) - 1
print((ans + ab_zero) % MOD)
F - . (Single Dot)
問題
- 無限に広い座標平面の原点に、点と見なせる牛がいる
- 南に $x$ [cm]、東に $y$ [cm]動いた位置を $(x,y)$ とする
- 垂直な線分が $N$ 本ある。$i$ 本目の線分は $(A_i,C_i)～(B_i,C_i)$ を結ぶ
- 水平な線分が $M$ 本ある。$i$ 本目の線分は $(D_i,E_i)～(D_i,F_i)$ を結ぶ
- 牛は線分（端点含む）を超えて移動できないとすると、牛が移動できる面積を求めよ
- ただし、無限に移動できる場合は'INF'と出力せよ
- 原点上には、線分は存在しない
- $1 \le N,M \le 1000$
- $-10^9 \le A_i,B_i,C_i,D_i,E_i,F_i \le 10^9$
- 入力は全て整数
解法
意味がわかると（実装が）怖い話。
要はペイントの「塗りつぶし」のようなことをしたい。 これは塗ったピクセルの隣接ピクセルが塗れるなら（間に線がなければ）塗りを広げる、ということを繰り返す単純な探索アルゴリズムで可能である。（またはUnion-Find）
しかし、いかんせん値の範囲がでかい。
なので、問題を解くにあたって同一視できるものをまとめてやる必要がある。 （「隣のピクセルが塗れるならここも絶対塗れる」「左に行くには位置 $y$ の線分で遮られる」など）
- ARMERIA氏がイメージ図を掲載されている
線分の端点となる $x$ 座標、$y$ 座標を変曲点として座標を圧縮すると、上限で約 $3000 \times 3000$ のグリッドになり、これなら何とか全てのグリッドを訪れることが可能である。
与えられた最も外側の $x,y$ 座標のさらに外側も1つのグリッドとして表現しておくと、探索の過程でそこを訪れ次第、答えはINFと確定する。
y -105 -2 0 4 37
j 0 1 2 3 4
x i +-----+--------+--+--+------+-----+
|(0,0)| | | | | |
-22 0 |-----|--------|--+--+------|-----+
| | | s|s | | |
0 1 |-----|--------|--+--+------|-----+
| | | s|s | | |
5 2 |-----+--------+--+--+------+-----+
| | | | | | |
12 3 |-----+--------+--+--+------+-----+
|(4,0)| | | | |(4,5)|
+-----+--------+--+--+------+-----+
座標圧縮で圧縮するのは各境界線の座標だが、探索はそれによって区切られたグリッド上で行うので、混乱しやすい。
$i$ 番目の横の境界線と $j$ 番目の縦の境界線の交点を左上に持つグリッドを、$(i+1,j+1)$ と表現する、のように、事前に図など書いてindexの対応を取っておくことが重要。
原点には線分はないので、上図の 's' で示した4グリッドは全て繋がっていることが保証されている。
壁の表現方法
方法の1つとしては、各グリッドについて「左に壁がある」「上に壁がある」フラグを持たせればよい。
左や上に行けるかは今いるグリッドを見ればいいし、右や下に行けるかは、行こうとしているグリッドの情報を見ればよい。
ただ、すごく長い境界線（だが座標は共有しない）が縦・横共に1000本あると、1本あたり2000～3000近くのグリッド間を遮ることになるので、 1グリッドずつ設定していては間に合わない（……とは言い切れないが、遅い言語だときつい）
累積和、俗に言うimos法を用いて計算すればよい。
左に壁があるグリッドを求める場合、$(A_i,C_i)～(B_i,C_i)$ の線分なら、$(A_i,C_i)$ に+1、$(B_i,C_i)$ に-1する。
そうして全ての線分を登録し追えたら、$(A_i,C_i)←(0,C_i)+(1,C_i)+...+(A_i,C_i)$ と累積和に置き換えれば、壁がないなら0、あるなら1以上になる。
グリッド数の節約（保留）
今までの説明では、線分の端点になる座標は全て座標圧縮に利用していた。
実行時間が速い人の実装を見ると、グリッド数はそこまで多くしなくても可能らしい。
なんかテストケースが弱かっただけで、嘘解法っぽい？
# Pythonで通そうと、よく分からないままnjit付けまくったコード
# やっぱり、ちょっとでも [(int, list)] みたいな
# 型の混じったデータ使った途端、高速化の恩恵が少なくなる感じ
import sys
import numpy as np
from numba import njit, types
from numba.typed import Dict
n, m, *abcdef = map(int, sys.stdin.buffer.read().split())
n3 = n * 3
aaa = abcdef[0:n3:3]
bbb = abcdef[1:n3:3]
ccc = abcdef[2:n3:3]
ddd = abcdef[n3 + 0::3]
eee = abcdef[n3 + 1::3]
fff = abcdef[n3 + 2::3]
x_list = {0}
x_list.update(ccc)
x_list.update(eee)
x_list.update(fff)
y_list = {0}
y_list.update(aaa)
y_list.update(bbb)
y_list.update(ddd)
@njit
def create_dict(x_list):
d = Dict.empty(key_type=types.int64, value_type=types.int64)
for i in range(len(x_list)):
d[x_list[i]] = i + 1
return d
x_list = np.array(sorted(x_list), dtype=np.int64)
y_list = np.array(sorted(y_list), dtype=np.int64)
x_dict = create_dict(x_list)
y_dict = create_dict(y_list)
row_real = len(x_list)
col_real = len(y_list)
row = row_real + 2
col = col_real + 2
total = row * col
banned_up = np.zeros(total, dtype=np.int16)
banned_left = np.zeros(total, dtype=np.int16)
@njit
def register_ver_lines(a, b, c, banned_left, x_dict, y_dict, row):
if a > b:
a, b = b, a
ai = y_dict[a] * row
bi = y_dict[b] * row
j = x_dict[c]
banned_left[ai + j] += 1
banned_left[bi + j] -= 1
@njit
def register_hor_lines(d, e, f, banned_up, x_dict, y_dict, row):
if e > f:
e, f = f, e
ri = y_dict[d] * row
ej = x_dict[e]
fj = x_dict[f]
banned_up[ri + ej] += 1
banned_up[ri + fj] -= 1
@njit
def accumulate_banned(banned_up, banned_left, row, col):
for i in range(1, col):
ri0 = row * (i - 1)
ri1 = row * i
for j in range(1, row):
banned_up[ri1 + j] += banned_up[ri1 + j - 1]
banned_left[ri1 + j] += banned_left[ri0 + j]
@njit
def solve(x_list, y_list, x_dict, y_dict, banned_up, banned_left, row, col):
s = row * y_dict[0] + x_dict[0]
enable = np.array([-1] * row + ([-1] + [0] * (row - 2) + [-1]) * (col - 2) + [-1] * row, dtype=np.int8)
enable[s] = 1
q = [s]
def check(nc):
nonlocal enable, q
if not enable[nc] == 1:
q.append(nc)
enable[nc] = 1
ans = 0
while q:
c = q.pop()
if not banned_up[c]:
nc = c - row
if enable[nc] == -1:
return -1
check(nc)
if not banned_left[c]:
nc = c - 1
if enable[nc] == -1:
return -1
check(nc)
nc = c + 1
if not banned_left[nc]:
if enable[nc] == -1:
return -1
check(nc)
nc = c + row
if not banned_up[nc]:
if enable[nc] == -1:
return -1
check(nc)
i, j = divmod(c, row)
t = y_list[i - 1]
b = y_list[i]
l = x_list[j - 1]
r = x_list[j]
ans += (b - t) * (r - l)
return ans
for a, b, c in zip(aaa, bbb, ccc):
register_ver_lines(a, b, c, banned_left, x_dict, y_dict, row)
for d, e, f in zip(ddd, eee, fff):
register_hor_lines(d, e, f, banned_up, x_dict, y_dict, row)
accumulate_banned(banned_up, banned_left, row, col)
ans = solve(x_list, y_list, x_dict, y_dict, banned_up, banned_left, row, col)
print(ans if ans != -1 else 'INF')
