ABC191
D苦手…WAが解決しない… 飛ばしてEはダイクストラでさっと解いて、残り30分 DをやるかFをやるかでFを考察する方が学びがありそうと判断し「いくつかの数のgcdであってmin以下のものの数」でサンプルは通ったがやっぱりTLE。この時点で残り13分なので残りはDをしてたけど最後まで解決せず4問
あー、そうか。Dは「10000倍して整数で扱おう…って二次関数の解を求めるところで平方根が出てくるじゃん…」となってたけど、そこを二分探索で求めるのか。数学的にはO(1)で解けるのでそれに無意識にこだわってしまったが、O(logR)でも間に合う、と。
Fは「いくつかの数のgcdであってmin以下のものの数」だと看破したのは正解であった。 それを効率よく求める方法が思いつけるとよかった。
水色に落ちるかなと思ったが、意外と+3だった
- 塗られるマスの四隅の角について「なければ追加、既にあるなら取り除く」をやる
python
def main():
H, W = map(int, input().split())
world = OneDimensionMap(H, W, 0)
for pos in world.allPosition():
if world.mapdata[pos] == 35:
start = pos
break
corner = set()
visited = set()
DIR4 = world.dir4()
def visit(pos):
visited.add(pos)
x, y = divmod(pos, W)
for xy in [(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)]:
if xy in corner:
corner.remove(xy)
else:
corner.add(xy)
for dir in DIR4:
newpos = pos + dir
if world.mapdata[newpos] == 35 and newpos not in visited:
visit(newpos)
visit(start)
print(len(corner))
- 公式解説を見るともっとシンプルに書けることがわかる。
- なければ足して、あれば取る、というのは要するに「処理が行われた回数が奇数回か？」ということと同値
- それが知りたいだけなら、足し算の順序は入れ替えても同じなので隣接順に処理する必要はない
- これでAC python
def main():
H, W = map(int, input().split())
world = OneDimensionMap(H, W, 0)
from collections import defaultdict
cornerCount = defaultdict(int)
for pos in world.allPosition():
if world.mapdata[pos] == 35:
for d in [0, 1, W, 1 + W]:
cornerCount[pos + d] += 1
print(sum(v % 2 for v in cornerCount.values()))
- 自己辺や多重辺があることに注意が必要
- 多重辺は一番短いものだけ残しておく
# (2)- 辺
edges[i][j]で持ってるので多重辺を持つの面倒だったから
- 辺
- 各点からダイクストラ法で他の点への距離を求める(
dist)# (3) edges[i][i]とdist[i][j] + dist[j][i]$(i \neq j)$の中で最小のものを見つければ良い# (1)について- 辺に重みのあるグラフは普段は
defaultdict(dict)で扱ってる - のだけど、今回
# (4)でアクセスする時に値が存在するかどうかチェックするのめんどいなと思った - ので、値が存在しない時INFになるようにした
- 普段からこれでいいな python
- 辺に重みのあるグラフは普段は
def main():
N, M = map(int, input().split())
from collections import defaultdict
INF = 9223372036854775807
edges = defaultdict(lambda: defaultdict(lambda: INF)) # (1)
for _i in range(M):
frm, to, cost = map(int, input().split())
# -1 for 1-origin vertexes
edges[frm-1][to-1] = min(edges[frm-1][to-1], cost) # (2)
dist = []
for start in range(N):
dist.append(one_to_all(start, N, edges, INF=INF)) # (3)
for i in range(N):
x = INF
for j in range(N):
if j == i:
x = min(x, edges[i][i]) # (4)
else:
x = min(x, dist[i][j] + dist[j][i])
if x == INF:
print(-1)
else:
print(x)
- 値はソートされていると考えて一般性を失わない
- 小さい例を考える
- 値が二つの時、A2がA1の倍数なら1通り、違うなら2通り
- リアルタイムのメモを見るとここからすぐ「A1より小さいgcd(Ai, Aj)の個数を調べれば良い」と結論してるけど、なんでそうなったんだっけ…
- gcdは取る順番によらないから引数は集合として考えてよくて、Aの部分集合のgcdがA1より小さくなった時にはそれを解にする手順が存在する
- 問題はこれをどうやって効率よく計算するかで、素朴な2^Nは当然無理なので悩ましい
- 4TLE python
def main():
from math import gcd
N = int(input())
AS = list(map(int, input().split()))
minA = min(AS)
ALL = set(AS)
NEW = set(AS)
while NEW:
next = set()
for x in ALL:
for y in NEW:
next.add(gcd(x, y))
ALL.update(NEW)
NEW = next - ALL
ret = 1
for x in ALL:
if x < minA:
ret += 1
print(ret)
- 公式解説
- $\exists (S \subset A) x = \gcd(S) \iff \gcd(y[x\text{ divides }y] ) = x$
- ある集合Sについて成り立つなら、そこにxの倍数を追加しても成り立つ
- なのですべての部分集合をケアする必要はない
- xの倍数であるものを全部含んだ集合だけを考えれば良い
- xがAのどの数の約数でもない場合、集合が空になるので考えなくて良い
- なのでいずれかの数の約数であるxについて、それと1対1対応する集合のgcdを取れば良い
- 約数個数は対数オーダーなのでAが10^9でも問題ない
- それでも3TLE
- 約数の数が多いテストケースで落ちるようになる
python
def main():
from math import gcd
from functools import reduce
N = int(input())
AS = list(map(int, input().split()))
minA = min(AS)
S = set(AS)
divisors = set()
for x in S:
divisors.update(get_divisors(x))
ret = 1
for d in sorted(divisors):
if d == minA:
break
targets = [x for x in S if x % d == 0]
if reduce(gcd, targets) == d:
ret += 1
print(ret)
- 約数列挙のタイミングでgcdまで計算すればAC
python
def main():
from math import gcd
from collections import defaultdict
N = int(input())
AS = list(map(int, input().split()))
minA = min(AS)
S = set(AS)
gcds = defaultdict(int)
for x in S:
for d in get_divisors(x):
gcds[d] = gcd(gcds[d], x)
ret = 1
for d in sorted(gcds):
if d == minA:
break
if gcds[d] == d:
ret += 1
print(ret)
- 前者がダメで後者ならOKなの、自明ではない気がする
- gcd
- 前者$\sum_i \sum_x [x < \min(A)][x \text{ divides } A_i]$
- 後者$\sum_i \sum_x [x \text{ divides } A_i]$
- 前者の方が小さいよな…
- 考察
- 部分集合の個数は2^2000、それに対して値の範囲は10^9
- 定義域より値域が狭い関数
- こういう時に値域と定義域の交換をする
- Xを像とする元は複数個あり得るのだけど、その中から構成しやすいものを選べば良い
- Zのような像にならない元は、何に写しても良い
- 元々の写像をf、反転した写像をgとするとき、ある元xがfの像に含まれるかどうかは $f(g(x)) = x$でわかる
- これは通常の意味での逆写像ではない
- 通常は$f(x) = y \iff g(y) = x$であるような写像f,gを互いにもう片方の逆写像といい、全単射の時だけ存在する
- 今回は与えられたfに対して$g(y) = x \Rightarrow f(x) = y$が成り立てば良い、ゆるい逆写像
- 今回の問題に関しては、$x = \gcd(S)$ のゆるい逆関数が $S = {y|y\in A, x\text{ divides }y }$であることに気付くのが問題変形の第一歩だった
- 実数に対する大小判定
- まずは誤差を考えずに素朴に書いてみる
- 二次関数の解の公式
- これでサンプルは全部通る python
def main_simple():
from math import floor, ceil, sqrt
X, Y, R = map(float, input().split())
ret = 0
for y in range(floor(Y - R), ceil(Y + R) + 1):
xcep = R ** 2 - (y - Y) ** 2
a = 1
b = -2 * X
c = X ** 2 - xcep
e = b * b - 4 * a * c
if e < 0:
continue
s = sqrt(e) # (1)
r1 = (-b + s) / (2 * a)
r2 = (-b - s) / (2 * a)
ret += floor(r1) - ceil(r2) + 1
print(ret)
- さてこれの整数版を作ろう…と思ったが
# (1)の平方根の計算が厄介- コンテスト中は平方根を使ったままなんとかしようとしてダメだった
- コンテスト後、これは二分探索で求めれば良いと気づいた
- 二分探索チェックリストを見ながらバグらせないように注意して書く
- AC
# (2)これは確実に円の外である必要がある。# (4)も同じfloor(fX - fR)だとちょうどピッタリ円周上になるケースがある
# (3)円の中心がちょうど整数である場合に、その頂点がダブルカウントされてしまわないように注意が必要 python
def main():
from math import floor, ceil, sqrt
fX, fY, fR = map(float, input().split())
X, Y, R = [round(x * 10000) for x in [fX, fY, fR]]
ret = 0
def isIn(x, y):
ret = (X - x * 10000) ** 2 + (Y - y * 10000) ** 2 <= R ** 2
return ret
for y in range(floor(fY - fR), ceil(fY + fR) + 1):
# find start
left = floor(fX - fR - 1) # (2)
init_right = right = floor(fX)
if isIn(right, y):
while left < right - 1:
x = (left + right) // 2
if isIn(x, y):
right = x
else:
left = x
ret += init_right - left
# find end
init_left = left = init_right + 1 # (3)
right = ceil(fX + fR + 1) # (4)
if isIn(left, y):
while left < right - 1:
x = (left + right) // 2
if isIn(x, y):
left = x
else:
right = x
ret += right - init_left
print(ret)