We will solve the problems of the programming contest challenge book (commonly known as ant book) with python. We plan to update it little by little, including similar issues.
For the beginner's edition, I think you should refer to @ saba's article. https://qiita.com/saba/items/affc94740aff117d2ca9
p128 lower_bound
N = 5
A = [2, 3, 3, 5, 6]
K = 3
#Index of the leftmost Ai that is K or higher
print(bisect_left(A, K))
p129 cable master
N = 4
K = 11
L = [8.02, 7.43, 4.57, 5.39]
def f(target):
cnt = 0
for i in range(N):
cnt += math.floor(L[i] / target) #How many strings of length target can be taken from each string
if cnt >= K: #If you get more than K
return True
else:
return False
ng = 0
ok = 10 ** 9 + 1
for i in range(100):
mid = (ng + ok) / 2
if f(mid):
ng = mid
else:
ok = mid
print(math.floor(ok * 100) / 100) #Find up to two decimal places
p131 aggressive cows
N = 5
M = 3
X = [1, 2, 8, 4, 9]
X.sort()
def c(d):
last = 0 #Put the first hut
# M -Can the hut be placed at a distance of d or more from the current location once?
for _ in range(M - 1):
crt = last + 1 #Advance crt to find a place to put the next hut
while crt < N and X[crt] - X[last] < d:
crt += 1
if crt == N: #If you can't find a place to put the hut next
return False
last = crt #Put the next hut
return True # M -If you put a hut once
ok = -1
ng = 10 ** 9 + 1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if c(mid):
ok = mid
else:
ng = mid
print(ok)
N = 3
K = 2
W = [2, 5, 2]
V = [2, 3, 1]
def c2(x, w, v):
#A set of products selected to satisfy "the value per unit weight is x or more"
# S([w1, v1], [w2, v2]...[wk, vk])And. This time
# sum(v1, v2...vk) / sum(w1, w2...wk) >=From x
# sum(v1, v2...vk) - x * sum(w1, w2...wk) >= 0
# sum(v1 - x * w1, v2 - x * w2, ...vk - x * wk) >= 0
# v[i] - x * w[i]When k are taken in descending order, it should be 0 or more
cnt = 0
items = [v[i] - x * w[i] for i in range(N)]
items.sort(reverse = True)
for i in range(K):
cnt += items[i]
return cnt >= 0
ok = 0
ng = 10 ** 9 + 1
for i in range(100):
mid = (ng + ok) / 2
if c2(mid, W, V):
ok = mid
else:
ng = mid
print(ok)
p135 subsequence
N = 10
S = 15
A = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
right = 0
total = 0
ans = float('inf')
for left in range(N):
while right < N and total < S:
#Advance right until the condition is met total>=Censor when it becomes S
# left, right, total = 0
# total <Because it is S, A[0]Add to total and increase right by one
# left, right, total = 0, 1, 5
# ...
# left, right, total = 0, 4, 14
# total <Because it is S, A[4]Add to total(At this point total<(Become S) Increase right by one
# left, right, total = 0, 5, 24
# total >=Because it is S, A[5]Do not add
total += A[right]
right += 1
#If total<If right reaches the right end with S
if total < S:
continue
# left, right = 0,If 5, it is a closed section[0, 4]Sum becomes S or more
#→ Half-open section[0, 5)Sum becomes S or more
ans = min(ans, right - left)
if left == right:
right += 1
total -= A[left]
# print(left, right)
print(ans)
p137 Jessica's Reading Problem
P = 5
A = [1, 8, 8, 8, 1]
dict = {}
for i in A:
dict[i] = 0
l = 0
cnt = 0
ans = float('inf')
#Advance one right and sharpen the left as much as possible
for r in range(P):
#Add a new one
if dict[A[r]] == 0: #If a new element comes
cnt += 1
dict[A[r]] += 1
#Shave the left while including all the elements
while True:
#If there is only one element, it cannot be scraped
if dict[A[l]] == 1:
break
#If there are two or more elements, scrape
dict[A[l]] -= 1
l += 1
if cnt < len(dict.items()):
continue
ans = min(ans, r - l + 1)
print(ans)
p138 Face The Right Way
N = 7
S = 'BBFBFBB'
def judge(k):
imos = [0] * N
#Whether to turn over the first time
if S[0] == 'B':
imos[0] = 1
#If the cow is facing backwards from the front, turn it over
# k =If 4
# BBFBFBB
# [ ]
# [ ]
# [ ]
# [ ]
#Turn over up to 4 times
for i in range(1, N - k + 1):
if i < k:
rev = imos[i - 1]
else:
rev = imos[i - 1] - imos[i - k]
if (S[i] == 'B') ^ (rev % 2):
imos[i] += 1
imos[i] += imos[i - 1]
#Find out if the rest of the cows are facing forward
for i in range(N - k + 1, N):
if i < k:
rev = imos[N - k]
else:
rev = imos[N - k] - imos[i - k]
if (S[i] == 'B') ^ (rev % 2):
return float('inf')
return imos[N - k]
K = 0
M = float('inf')
for i in range(1, N + 1):
opt = judge(i)
if opt < M:
M = opt
K = i
print(K, M)
p141 Fliptile
M = 4
N = 4
maze = [
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
]
def changer(o, f):
for i in range(1, M):
for j in range(N):
#Examine the maze and flip one above
#If maze is black and flip is flipped an even number of times or maze is white and flip is flipped an odd number of times
if (maze[i - 1][j] == 1) ^ (f[i - 1][j] % 2):
o[i][j] += 1
f[i][j] += 1
f[i - 1][j] += 1
if j >= 1:
f[i][j - 1] += 1
if j < N - 1:
f[i][j + 1] += 1
if i < M - 1:
f[i + 1][j] += 1
return o, f
#Full search for the first line
#When the first line is decided, the second and subsequent lines are uniquely decided
#Full search for the first line:O(2 ** N)Fill in the second and subsequent lines:O(MN)Because it takes
#The total amount of calculation is O(MN(2 ** N))become
for bit in range(1 << N):
opt = [[0] * N for i in range(M)]
flip = [[0] * N for i in range(M)]
for i in range(N):
if bit & (1 << i):
opt[0][i] += 1
flip[0][i] += 1
if i >= 1:
flip[0][i - 1] += 1
if i < N - 1:
flip[0][i + 1] += 1
opt, flip = changer(opt, flip)
#Judgment for the last column
for j in range(N):
#If not
if (maze[M - 1][j] == 1) ^ (flip[M - 1][j] % 2):
break
else:
for i in opt:
print(*i)
p145 physics experiment
#Think of balls as slipping through like ants
N, H, R, T = 2, 10, 10, 100
g = 10
def judge(time):
if time < 0:
return H
t = math.sqrt(2 * H / 10)
k = int(time / t)
if k % 2 == 0:
d = time - k * t
return H - g * d * d / 2
else:
d = k * t + t - time
return H - g * d * d / 2
ans = []
for i in range(N):
#Drop the ball every second
ans.append(judge(T - i))
#You can think of the balls as slipping through each other
ans.sort()
for i in range(N):
#Note that R is centimeters but H is meters
print(ans[i] + (2 * R * i / 100))
p147 4 values whose sum is 0
#Binary search
def binary_search_loop(data, target):
imin = 0
imax = len(data) - 1
while imin <= imax:
imid = imin + (imax - imin) // 2
if target == data[imid]:
return imid
elif target < data[imid]:
imax = imid - 1
else:
imin = imid + 1
return False
N = 6
A = [-45, -41, -36, -36, 26, -32]
B = [22, -27, 53, 30, -38, -54]
C = [42, 56, -37, 75, -10, -6]
D = [-16, 30, 77, -46, 62, 45]
re_A = []
re_C = []
# Ai + Bj
for i in range(N):
for j in range(N):
re_A.append(A[i] + B[j])
re_A.sort()
# Ci + Dj
for i in range(N):
for j in range(N):
re_C.append(C[i] + D[j])
re_C.sort()
ans = 0
for i in re_A:
# ind1:Leftmost index among those with a total of 0 or more
# ind2:Leftmost index among those with a total of 1 or more
# ind1 ind2
# [...-2, -1, (0), 0, 0, (2), 2, 3]
ind1 = bisect_left(re_C, 0 - i)
ind2 = bisect_left(re_C, 0 - i + 1)
ans += ind2 - ind1
print(ans)
N = 4
w = [2, 1, 3, 2]
v = [3, 2, 4, 2]
W = 5
#Half full enumeration+Binary search
def re_list(weight, value):
fore_list = []
#First, combine all the ways
for bit in range(1 << len(weight)):
wei = 0
val = 0
for i in range(len(weight)):
if bit & (1 << i):
wei += weight[i]
val += value[i]
fore_list.append([wei, val])
fore_list.sort()
#List rebuild
#I'm erasing what I obviously don't need
# ABC032 D -See the explanation of the knapsack problem
alta_w = []
alta_v = []
now = -1
for i in fore_list:
if now < i[1]:
now = i[1]
alta_w.append(i[0])
alta_v.append(i[1])
return alta_w, alta_v
def half_knapsack(N, limit, weight, value):
#Half full enumeration
fore_w, fore_v = re_list(weight[:N // 2], value[:N // 2])
back_w, back_v = re_list(weight[N // 2:], value[N // 2:])
ans = 0
for b_w, b_v in zip(back_w, back_v):
if b_w > limit:
continue
opt = b_v
index = bisect_right(fore_w, limit - b_w)
if index > 0:
opt += fore_v[index - 1]
ans = max(ans, opt)
return ans
print(half_knapsack(N, W, w, v))
#Given x,Since the upper limit of y is small, it is not compressed at all in this input example.
W, H, N = 10, 10, 5
# (x1, y1)From(x2, y2)Draw a line
X1 = [i - 1 for i in [1, 1, 4, 9, 10]]
X2 = [i - 1 for i in [6, 10, 4, 9, 10]]
Y1 = [i - 1 for i in [4, 8, 1, 1, 6]]
Y2 = [i - 1 for i in [4, 8, 10, 5, 10]]
#Vertical
row = set()
r_index = {}
#side
col = set()
c_index = {}
#conversion
for x, y in zip(X1 + X2, Y1 + Y2):
#Which row is needed
row.add(y)
if y > 0:
row.add(y - 1)
if y < H - 1:
row.add(y + 1)
#Which column is needed
col.add(x)
if x > 0:
col.add(x - 1)
if x < W - 1:
col.add(x + 1)
#Which coordinates will be after compression
H = len(row)
row = sorted(list(row))
for i in range(H):
r_index[row[i]] = i
W = len(col)
col = sorted(list(col))
for i in range(W):
c_index[col[i]] = i
X1 = [c_index[i] for i in X1]
X2 = [c_index[i] for i in X2]
Y1 = [r_index[i] for i in Y1]
Y2 = [r_index[i] for i in Y2]
# print(X1, Y1, X2, Y2)
# X1: [0, 0, 3, 8, 9]
# Y1: [3, 7, 0, 0, 5]
# X2: [5, 9, 3, 8, 9]
# Y2: [3, 7, 9, 4, 9]
#Then solve normally
maze = [[0] * W for i in range(H)]
#Draw a line
for x1, y1, x2, y2 in zip(X1, Y1, X2, Y2):
#Vertical line
if x1 == x2:
if y1 > y2:
y1, y2 = y2, y1
for i in range(y1, y2 + 1):
maze[i][x1] = 1
#horizontal line
else:
if x1 > x2:
x1, x2 = x2, x1
for i in range(x1, x2 + 1):
maze[y1][i] = 1
#p35 lake counting
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def dfs(y, x):
maze[y][x] = 1
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == 0:
dfs(ny, nx)
ans = 0
for y in range(H):
for x in range(W):
if maze[y][x] == 0:
dfs(y, x)
ans += 1
print(ans)
Recommended Posts