Nous allons résoudre les problèmes du livre de défi du concours de programmation (communément appelé Arimoto) avec python. Nous prévoyons de le mettre à jour petit à petit, y compris des problèmes similaires.
Pour l'édition débutant, je pense que vous devriez vous référer à l'article de @ saba. https://qiita.com/saba/items/affc94740aff117d2ca9
p128 lower_bound
N = 5
A = [2, 3, 3, 5, 6]
K = 3
#Index du Ai le plus à gauche, K ou plus
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) #Combien de chaînes de longueur cible peuvent être extraites de chaque chaîne
if cnt >= K: #Si vous obtenez plus de 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) #Trouver jusqu'au 2ème chiffre
p131 aggressive cows
N = 5
M = 3
X = [1, 2, 8, 4, 9]
X.sort()
def c(d):
last = 0 #Mettez la première hutte
# M -Puis-je placer la cabane à un endroit plus éloigné qu'une fois de l'endroit actuel?
for _ in range(M - 1):
crt = last + 1 #Avancez crt pour trouver un endroit pour mettre la prochaine hutte
while crt < N and X[crt] - X[last] < d:
crt += 1
if crt == N: #Si vous ne trouvez pas d'endroit pour mettre la cabane à côté
return False
last = crt #Mettez la prochaine cabane
return True # M -Si vous mettez une cabane une fois
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):
#Un ensemble de produits sélectionnés pour satisfaire "la valeur par unité de poids est x ou plus"
# S([w1, v1], [w2, v2]...[wk, vk])Et. Cette fois
# sum(v1, v2...vk) / sum(w1, w2...wk) >=De 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]Lorsque k sont pris dans l'ordre décroissant, il doit être égal ou supérieur
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:
#Avancez à droite jusqu'à ce que la condition soit remplie au total>=Arrêtez quand ça devient S
# left, right, total = 0
# total <Parce que c'est S, A[0]Ajouter au total et augmenter de un
# left, right, total = 0, 1, 5
# ...
# left, right, total = 0, 4, 14
# total <Parce que c'est S, A[4]Ajouter au total(À ce point total<(Devenir S) Augmenter la droite de un
# left, right, total = 0, 5, 24
# total >=Parce que c'est S, A[5]Ne pas ajouter
total += A[right]
right += 1
#Si total<Si la droite atteint l'extrémité droite avec S
if total < S:
continue
# left, right = 0,5 est une section fermée[0, 4]Est S ou plus
#→ Section semi-ouverte[0, 5)Est S ou plus
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')
#Avancez d'une droite et affûtez la gauche autant que possible
for r in range(P):
#Ajouter un nouveau
if dict[A[r]] == 0: #Si un nouvel élément arrive
cnt += 1
dict[A[r]] += 1
#Raser la gauche en incluant tous les éléments
while True:
#S'il n'y a qu'un seul élément, il ne peut pas être gratté
if dict[A[l]] == 1:
break
#S'il y a deux éléments ou plus, grattez
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
#S'il faut retourner la première fois
if S[0] == 'B':
imos[0] = 1
#Si la vache est tournée vers l'arrière par rapport à l'avant, retournez-la
# k =Si 4
# BBFBFBB
# [ ]
# [ ]
# [ ]
# [ ]
#Retourner jusqu'à 4 fois
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]
#Découvrez si le reste des vaches est tourné vers l'avant
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):
#Examinez le labyrinthe et retournez-en un ci-dessus
#Si le labyrinthe est noir et que le flip est retourné un nombre pair de fois ou si le labyrinthe est blanc et que le flip est retourné un nombre impair de fois
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
#Recherche complète de la première ligne
#Lorsque la première ligne est décidée, la deuxième ligne et les suivantes sont décidées de manière unique
#Recherche complète de la première ligne:O(2 ** N)Remplissez la deuxième ligne et les suivantes:O(MN)Parce qu'il faut
#Le montant total du calcul est O(MN(2 ** N))devenir
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)
#Jugement sur la dernière colonne
for j in range(N):
#Si non
if (maze[M - 1][j] == 1) ^ (flip[M - 1][j] % 2):
break
else:
for i in opt:
print(*i)
p145 physics experiment
#Pensez aux balles comme glissant comme des fourmis
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):
#Lâche la balle toutes les secondes
ans.append(judge(T - i))
#Vous pouvez penser que les balles se glissent les unes dans les autres
ans.sort()
for i in range(N):
#Notez que R est des centimètres mais H est des mètres
print(ans[i] + (2 * R * i / 100))
p147 4 values whose sum is 0
#Recherche de bisection
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:Indice le plus à gauche parmi ceux avec un total de 0 ou plus
# ind2:Indice le plus à gauche parmi ceux avec un total de 1 ou plus
# 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
#Énumération à moitié complète+Recherche de bisection
def re_list(weight, value):
fore_list = []
#Tout d'abord, combinez toutes les façons
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()
#Reconstruction de la liste
#J'efface ce dont je n'ai évidemment pas besoin
# ABC032 D -Voir l'explication du problème du sac à dos
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):
#Énumération à moitié complète
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))
#Étant donné x,Puisque la limite supérieure de y est petite, elle n'est pas du tout compressée dans cet exemple d'entrée.
W, H, N = 10, 10, 5
# (x1, y1)De(x2, y2)Tracer une ligne
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]]
#Verticale
row = set()
r_index = {}
#côté
col = set()
c_index = {}
#conversion
for x, y in zip(X1 + X2, Y1 + Y2):
#Quelle ligne est nécessaire
row.add(y)
if y > 0:
row.add(y - 1)
if y < H - 1:
row.add(y + 1)
#Quelle colonne est nécessaire
col.add(x)
if x > 0:
col.add(x - 1)
if x < W - 1:
col.add(x + 1)
#Quelles coordonnées seront après 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]
#Puis résolvez normalement
maze = [[0] * W for i in range(H)]
#Tracer une ligne
for x1, y1, x2, y2 in zip(X1, Y1, X2, Y2):
#Ligne verticale
if x1 == x2:
if y1 > y2:
y1, y2 = y2, y1
for i in range(y1, y2 + 1):
maze[i][x1] = 1
#ligne horizontale
else:
if x1 > x2:
x1, x2 = x2, x1
for i in range(x1, x2 + 1):
maze[y1][i] = 1
#comptage des lacs p35
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