ABC191
D苦手…WAが解決しない…
飛ばしてEはダイクストラでさっと解いて、残り30分
DをやるかFをやるかでFを考察する方が学びがありそうと判断し「いくつかの数のgcdであってmin以下のものの数」でサンプルは通ったがやっぱりTLE。この時点で残り13分なので残りはDをしてたけど最後まで解決せず4問
あー、そうか。Dは「10000倍して整数で扱おう…って二次関数の解を求めるところで平方根が出てくるじゃん…」となってたけど、そこを二分探索で求めるのか。数学的にはO(1)で解けるのでそれに無意識にこだわってしまったが、O(logR)でも間に合う、と。
Fは「いくつかの数のgcdであってmin以下のものの数」だと看破したのは正解であった。
それを効率よく求める方法が思いつけるとよかった。
https://gyazo.com/11f20f1d7f862d6ea4fde7731ce46ca4
水色に落ちるかなと思ったが、意外と+3だった
https://gyazo.com/eb5db44a3f3f5b810b54a1c41e614c55
https://gyazo.com/3a4098e5ac9f0a03bf0a1639e4628c98
なるほど、DとFがかなり難易度高いのか。
https://gyazo.com/1a741c4111bc4f5db792ae0c93d2b057
塗られるマスの四隅の角について「なければ追加、既にあるなら取り除く」をやる
https://gyazo.com/8f0bc7be1602e914181bc557889c5ef7
code:python
def main():
H, W = map(int, input().split())
world = OneDimensionMap(H, W, 0)
for pos in world.allPosition():
if world.mapdatapos == 35: start = pos
break
corner = set()
visited = set()
DIR4 = world.dir4()
def visit(pos):
visited.add(pos)
x, y = divmod(pos, W)
if xy in corner:
corner.remove(xy)
else:
corner.add(xy)
for dir in DIR4:
newpos = pos + dir
if world.mapdatanewpos == 35 and newpos not in visited: visit(newpos)
visit(start)
print(len(corner))
公式解説を見るともっとシンプルに書けることがわかる。
なければ足して、あれば取る、というのは要するに「処理が行われた回数が奇数回か？」ということと同値
それが知りたいだけなら、足し算の順序は入れ替えても同じなので隣接順に処理する必要はない
これでAC
code: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.mapdatapos == 35: print(sum(v % 2 for v in cornerCount.values()))
https://gyazo.com/09e4ac9d774ae0eabc238dcfc4bf3380
自己辺や多重辺があることに注意が必要
多重辺は一番短いものだけ残しておく# (2)
辺 edges[i][j]で持ってるので多重辺を持つの面倒だったから
各点からダイクストラ法で他の点への距離を求める(dist) # (3) edges[i][i]とdist[i][j] + dist[j][i]$ (i \neq j)の中で最小のものを見つければ良い
# (1)について
辺に重みのあるグラフは普段はdefaultdict(dict)で扱ってる
のだけど、今回# (4)でアクセスする時に値が存在するかどうかチェックするのめんどいなと思った
ので、値が存在しない時INFになるようにした
普段からこれでいいな
code: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
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, edgesii) # (4) else:
x = min(x, distij + distji) if x == INF:
print(-1)
else:
print(x)
https://gyazo.com/f96883d47e47026ec6ee1ce02b352d83
値はソートされていると考えて一般性を失わない
小さい例を考える
値が二つの時、A2がA1の倍数なら1通り、違うなら2通り
リアルタイムのメモを見るとここからすぐ「A1より小さいgcd(Ai, Aj)の個数を調べれば良い」と結論してるけど、なんでそうなったんだっけ…
gcdは取る順番によらないから引数は集合として考えてよくて、Aの部分集合のgcdがA1より小さくなった時にはそれを解にする手順が存在する
問題はこれをどうやって効率よく計算するかで、素朴な2^Nは当然無理なので悩ましい
4TLE
code: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
約数の数が多いテストケースで落ちるようになる
code: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
if reduce(gcd, targets) == d:
ret += 1
print(ret)
約数列挙のタイミングでgcdまで計算すればAC
code: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):
ret = 1
for d in sorted(gcds):
if d == minA:
break
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
https://gyazo.com/fb7188f57e2178ce53cc7aa47100082c
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 \}であることに気付くのが問題変形の第一歩だった
https://gyazo.com/3172c85b33db4ea6fc80c45aafa00a5e
まずは誤差を考えずに素朴に書いてみる
二次関数の解の公式
これでサンプルは全部通る
code: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) 円の中心がちょうど整数である場合に、その頂点がダブルカウントされてしまわないように注意が必要
code:python
def main():
from math import floor, ceil, sqrt
fX, fY, fR = map(float, input().split())
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)