All you have to do is set the position of one of the people associated with the information to 0 and check if there is a contradiction in DFS. Note that it is not always a group.
from sys import stdin
N, M = map(int, stdin.readline().split())
links = [[] for _ in range(N + 1)]
for _ in range(M):
L, R, D = map(int, stdin.readline().split())
links[L].append((R, D))
links[R].append((L, -D))
t = [None] * (N + 1)
for i in range(1, N + 1):
if t[i] is not None:
continue
t[i] = 0
s = [i]
while s:
j = s.pop()
for k, l in links[j]:
if t[k] is None:
t[k] = t[j] + l
s.append(k)
else:
if t[k] != t[j] + l:
print('No')
exit()
print('Yes')
Weighted Union Find Can be solved with a tree.
from sys import setrecursionlimit, stdin
def find(parent, diff_weight, i):
t = parent[i]
if t < 0:
return i
t = find(parent, diff_weight, t)
diff_weight[i] += diff_weight[parent[i]]
parent[i] = t
return t
def weight(parent, diff_weight, i):
find(parent, diff_weight, i)
return diff_weight[i]
def unite(parent, diff_weight, i, j, d):
d -= weight(parent, diff_weight, j)
d += weight(parent, diff_weight, i)
i = find(parent, diff_weight, i)
j = find(parent, diff_weight, j)
if i == j:
return
diff_weight[j] = d
parent[i] += parent[j]
parent[j] = i
setrecursionlimit(10 ** 6)
N, M = map(int, stdin.readline().split())
LRD = [tuple(map(int, stdin.readline().split())) for _ in range(M)]
parent = [-1] * (N + 1)
diff_weight = [0] * (N + 1)
for L, R, D in LRD:
i = find(parent, diff_weight, L)
j = find(parent, diff_weight, R)
if i != j:
unite(parent, diff_weight, L, R, D)
else:
if weight(parent, diff_weight, L) + D != weight(parent, diff_weight, R):
print('No')
exit()
print('Yes')
No matter how many operations you do, the total does not change, so the only candidate answer is a divisor of the total. After that, you can make it a multiple of that divisor with K operations, but sort the remainder divided by that divisor. If you do, the one that should be subtracted comes to the front, and the one that should be added comes to the back, so if you count in order from the front and back, you can calculate the minimum number of operations required.
def make_divisor_list(n):
result = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
result.append(i)
result.append(n // i)
return result
def calc_min_ops(r, d):
i, j = 0, len(r)
while i < j and r[i] == 0:
i += 1
i -= 1
a, b = 0, 0
while j - i != 1:
if a <= b:
i += 1
a += r[i]
else:
j -= 1
b += d - r[j]
return a
N, K, *A = map(int, open(0).read().split())
c = sum(A)
divisors = make_divisor_list(c)
divisors.sort(reverse=True)
r = [None] * N
for d in divisors:
for i in range(N):
r[i] = A[i] % d
r.sort()
if calc_min_ops(r, d) <= K:
print(d)
break
It may be at least ceil (max (h) / b) or less, but it is too late to calculate the difference between A and B in order from the one with the largest physical strength (confirmed using heapq). When I was told that, it was a wonder that I could solve it in an instant, but I couldn't think of it at all.
from bisect import bisect_right
N, A, B, *h = map(int, open(0).read().split())
h.sort()
d = A - B
ng = (h[-1] + (A - 1)) // A - 1
ok = (h[-1] + (B - 1)) // B
while ok - ng > 1:
m = (ok + ng) // 2
b = B * m
if m >= sum((h[i] - b + (d - 1)) // d for i in range(bisect_right(h, b), N)):
ok = m
else:
ng = m
print(ok)
I thought that knapsack = DP and thought in that direction, but I can not think of it at all. In the first place, N ≤ 100 and w1 ≤ wi ≤ w1 + 3, so even if I search all (100/4 + 1) 4 </ strong It had to be sup> ≒ 4.6 × 10 5 </ sup>, and it was okay to do a full search.
from sys import stdin
from itertools import accumulate
readline = stdin.readline
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
w, v = map(int, input().split())
vs[w - w1].append(v)
for i in range(4):
vs[i].sort(reverse=True)
vs[i] = [0] + list(accumulate(vs[i]))
result = 0
for i in range(len(vs[0])):
a = W - w1 * i
if a < 0:
break
for j in range(len(vs[1])):
b = a - (w1 + 1) * j
if b < 0:
break
for k in range(len(vs[2])):
c = b - (w1 + 2) * k
if c < 0:
break
t = vs[0][i] + vs[1][j] + vs[2][k]
for l in range(len(vs[3])):
d = c - (w1 + 3) * l
if d < 0:
break
result = max(result, t + vs[3][l])
print(result)
In short, AGC, ACG, GAC, A? GC, AG? C are useless, so you only need to hold the last 3 characters at most. 4 3 </ sup> -3 types, roughly from there Since it is derived four times, the amount of calculation is roughly 250 × 100 = 2.5 × 10 4 </ sup>, which is within the margin range. That is why it was solved by DP.
def is_ok(s):
if s[1:] in ['AGC', 'ACG', 'GAC']:
return False
if s[0] == 'A' and s[2:] == 'GC':
return False
if s[:2] == 'AG' and s[3] == 'C':
return False
return True
m = 1000000007
N = int(input())
d = {}
for i in 'ACGT':
for j in 'ACGT':
for k in 'ACGT':
d[i + j + k] = 1
for k in ['AGC', 'ACG', 'GAC']:
del d[k]
for i in range(N - 3):
t = {}
for k in d:
for i in 'ACGT':
s = k + i
if is_ok(s):
t.setdefault(s[1:], 0)
t[s[1:]] += d[k]
t[s[1:]] %= m
d = t
print(sum(d.values()) % m)
I thought it would be easy if there was no absolute value. Then I wondered if I should find the maximum values of plus and minus respectively. That's 2 3 </ sup> times, if there is no absolute value Since it is the same as doing, there is no problem in terms of computational complexity. I was not sure that it would be the maximum value, but it seems that it was an idea because it was AC.
from itertools import product
from sys import stdin
readline = stdin.readline
N, M = map(int, readline().split())
xyz = [tuple(map(int, readline().split())) for _ in range(N)]
result = 0
for s in product([1, -1], repeat=3):
xyz.sort(reverse=True, key=lambda e: s[0] * e[0] + s[1] * e[1] + s[2] * e[2])
cx, cy, cz = 0, 0, 0
for x, y, z in xyz[:M]:
cx += x
cy += y
cz += z
result = max(result, abs(cx) + abs(cy) + abs(cz))
print(result)
Recommended Posts