Wir werden die Probleme des Programmierwettbewerbs Challenge Book (allgemein bekannt als Arimoto) mit Python lösen. Wir planen, es nach und nach zu aktualisieren, einschließlich ähnlicher Probleme.
Für die Anfängerausgabe sollten Sie sich auf den Artikel von @ saba beziehen. https://qiita.com/saba/items/affc94740aff117d2ca9
p128 lower_bound
N = 5
A = [2, 3, 3, 5, 6]
K = 3
#Index des Ai ganz links, der K oder höher ist
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) #Wie viele Zeichenfolgen mit dem Ziel Länge können aus jeder Zeichenfolge entnommen werden?
if cnt >= K: #Wenn Sie mehr als K bekommen
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) #Finden Sie bis zur 2. Ziffer
p131 aggressive cows
N = 5
M = 3
X = [1, 2, 8, 4, 9]
X.sort()
def c(d):
last = 0 #Stell die erste Hütte
# M -Kann ich die Hütte einmal an einem Ort platzieren, der mehr als d vom aktuellen Ort entfernt ist?
for _ in range(M - 1):
crt = last + 1 #Gehen Sie voran, um einen Platz für die nächste Hütte zu finden
while crt < N and X[crt] - X[last] < d:
crt += 1
if crt == N: #Wenn Sie keinen Platz finden, um die Hütte als nächstes zu platzieren
return False
last = crt #Stell die nächste Hütte
return True # M -Wenn Sie einmal eine Hütte setzen
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):
#Eine Reihe von Produkten, die ausgewählt wurden, um "Wert pro Gewichtseinheit ist x oder mehr" zu erfüllen
# S([w1, v1], [w2, v2]...[wk, vk])Und. In diesem Moment
# sum(v1, v2...vk) / sum(w1, w2...wk) >=Von 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]Wenn k in absteigender Reihenfolge genommen wird, sollte es 0 oder mehr sein
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:
#Vorwärts gehen, bis die Bedingung vollständig erfüllt ist>=Stoppen Sie, wenn es S wird
# left, right, total = 0
# total <Weil es S, A ist[0]Addiere zur Summe und erhöhe direkt um eins
# left, right, total = 0, 1, 5
# ...
# left, right, total = 0, 4, 14
# total <Weil es S, A ist[4]Zur Summe hinzufügen(Zu diesem Zeitpunkt insgesamt<(Werden Sie S) Erhöhen Sie sich um eins
# left, right, total = 0, 5, 24
# total >=Weil es S, A ist[5]Nicht hinzufügen
total += A[right]
right += 1
#Wenn insgesamt<Wenn rechts mit S das rechte Ende erreicht
if total < S:
continue
# left, right = 0,5 ist ein geschlossener Abschnitt[0, 4]Ist S oder mehr
#→ Halboffener Abschnitt[0, 5)Ist S oder mehr
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')
#Bewegen Sie eine nach rechts und schärfen Sie die linke so weit wie möglich
for r in range(P):
#Fügen Sie eine neue hinzu
if dict[A[r]] == 0: #Wenn ein neues Element kommt
cnt += 1
dict[A[r]] += 1
#Rasieren Sie die linke Seite, während Sie alle Elemente einbeziehen
while True:
#Wenn es nur ein Element gibt, kann es nicht abgekratzt werden
if dict[A[l]] == 1:
break
#Wenn zwei oder mehr Elemente vorhanden sind, kratzen Sie
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
#Ob beim ersten Mal umgedreht werden soll
if S[0] == 'B':
imos[0] = 1
#Wenn die Kuh von vorne nach hinten zeigt, drehen Sie sie um
# k =Wenn 4
# BBFBFBB
# [ ]
# [ ]
# [ ]
# [ ]
#Bis zu 4 mal umdrehen
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]
#Finden Sie heraus, ob der Rest der Kühe nach vorne zeigt
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):
#Untersuche das Labyrinth und drehe eines nach oben
#Wenn das Labyrinth schwarz ist und das Umdrehen gerade oder das Labyrinth weiß ist und das Umdrehen ungerade umgedreht wird
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
#Vollständige Suche nach der ersten Zeile
#Wenn die erste Zeile entschieden wird, werden die zweite und die nachfolgenden Zeilen eindeutig entschieden
#Vollständige Suche nach der ersten Zeile:O(2 ** N)Füllen Sie die zweite und die folgenden Zeilen aus:O(MN)Weil es dauert
#Der Gesamtbetrag der Berechnung beträgt O.(MN(2 ** N))werden
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)
#Urteil über die letzte Spalte
for j in range(N):
#Wenn nicht
if (maze[M - 1][j] == 1) ^ (flip[M - 1][j] % 2):
break
else:
for i in opt:
print(*i)
p145 physics experiment
#Stellen Sie sich Bälle so vor, als würden sie wie Ameisen durchrutschen
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):
#Lass den Ball jede Sekunde fallen
ans.append(judge(T - i))
#Sie können sich vorstellen, dass die Kugeln durcheinander rutschen
ans.sort()
for i in range(N):
#Beachten Sie, dass R Zentimeter ist, H jedoch Meter
print(ans[i] + (2 * R * i / 100))
p147 4 values whose sum is 0
#Halbierungssuche
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:Index ganz links unter denen mit insgesamt 0 oder mehr
# ind2:Index ganz links unter denen mit insgesamt 1 oder mehr
# 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
#Halb vollständige Aufzählung+Halbierungssuche
def re_list(weight, value):
fore_list = []
#Kombinieren Sie zunächst alle Möglichkeiten
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()
#Liste neu erstellen
#Ich lösche, was ich offensichtlich nicht brauche
# ABC032 D -Siehe die Erklärung des Rucksackproblems
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):
#Halb vollständige Aufzählung
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))
#Gegeben x,Da die Obergrenze von y klein ist, wird sie in diesem Eingabebeispiel überhaupt nicht komprimiert.
W, H, N = 10, 10, 5
# (x1, y1)Von(x2, y2)Zeichne eine Linie
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]]
#Vertikal
row = set()
r_index = {}
#Seite
col = set()
c_index = {}
#Umwandlung
for x, y in zip(X1 + X2, Y1 + Y2):
#Welche Zeile wird benötigt?
row.add(y)
if y > 0:
row.add(y - 1)
if y < H - 1:
row.add(y + 1)
#Welche Spalte wird benötigt?
col.add(x)
if x > 0:
col.add(x - 1)
if x < W - 1:
col.add(x + 1)
#Welche Koordinaten werden nach der Komprimierung angezeigt?
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]
#Dann normal lösen
maze = [[0] * W for i in range(H)]
#Zeichne eine Linie
for x1, y1, x2, y2 in zip(X1, Y1, X2, Y2):
#Vertikale Linie
if x1 == x2:
if y1 > y2:
y1, y2 = y2, y1
for i in range(y1, y2 + 1):
maze[i][x1] = 1
#horizontale Linie
else:
if x1 > x2:
x1, x2 = x2, x1
for i in range(x1, x2 + 1):
maze[y1][i] = 1
#p35 Seezählung
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