Cela fait quelques mois que j'ai commencé à programmer, mais j'ai réalisé que je manquais massivement des connaissances nécessaires pour résoudre atcoder, alors j'ai décidé d'essayer de résoudre le livre des défis de programmation (communément appelé Arimoto). Je suis également intéressé par l'analyse de données comme kaggle, donc je vais essayer de le résoudre avec python.
n = 4
a = {4,5,10,20}
a = sorted(list(a))
ans = []
for i in range(n-2):
for j in range(i+1,n-1):
for k in range(j+1,n):
if a[k] < a[i]+a[j]:
ans.append([a[i],a[j],a[k]])
if ans==[]:
print(0)
else:
ans2 = []
for i in range(len(ans)):
ans2.append(sum(ans[i]))
print(max(ans2))
Triez un et organisez-les par ordre croissant. Comme la même valeur ne peut pas être obtenue deux fois, j doit être sélectionné parmi i et au-dessus. De plus, il est nécessaire de laisser deux valeurs supérieures à i.
Ant (POJ No.1852)
L = 10
n = 3
x = [2,6,7]
#Lors de la recherche de max
ans = L-min(x)
#Lors de la recherche de min
for i in range(n):
x[i] = min(x[i],L-x[i])
ans2 = max(x)
print("min =",ans2)
print("max =",ans)
En fait, vous pouvez voir qu'il n'y a pas de problème même si vous pensez que les deux fourmis se sont croisées et ont procédé comme elles étaient. … (Omis)… Pour trouver le temps maximum, vous devez trouver la valeur maximum de la distance au pont.
n = 3
m = 9
k= set([1,3,5])
a = set([])
for i in k:
for j in k:
a.add(i+j)
a = list(a)
#print(a)
n = len(a)
exist = False
for i in range(len(a)):
for j in range(len(a)):
l = 0 #Bord gauche de la plage de recherche
r = n #Bord droit de la plage de recherche
while (r - l >= 1) and exist==False: #Terminez le processus lorsque la plage de recherche est épuisée
i = (l + r) // 2 #Donne i la position médiane des données
if a[i] == m-a[j]:
exist = True
break
elif a[i] < m-a[j]:
l = i + 1
else:
r = i
if exist== True:
print("Yes")
else:
print("No")
a été difficile,, J'ai cherché des options possibles en divisant les quatre sélections en deux et deux. Les deux valeurs possibles à ce moment sont les mêmes. Si vous mettez les valeurs possibles dans la liste a, vous pouvez trouver a [i] == m-a [j]. À partir de là, faites une dichotomie pour trouver la réponse.
n = 4
a = [1,2,4,7]
k = 14
def dfs(i,s):
if i == n: #Après avoir décidé de n pièces, retournez si la somme somme jusqu'à présent est égale à k
#print(s)
return s == k
if dfs(i+1,s): #a[i]Si vous n'utilisez pas
#print("not use", i)
return True
if dfs(i+1,s+a[i]): #a[i]Lors de l'utilisation
#print("use", i)
return True
#print("f",s)
return False #a[i]Renvoie false car ce n'est pas k, qu'il soit utilisé ou non
if dfs(0,0):
print('Yes')
else:
print('No')
Problème de recherche complète en utilisant la recherche prioritaire en profondeur (dfs). Je vérifie tout avec et sans [i] pour voir s'il est égal à k. Il peut être plus facile à comprendre si vous supprimez l'impression qui est un commentaire.
Lake Counting Exemple d'entrée) N=10 M=12 w........ww. .www.....www ....ww...ww. .........ww. .........w.. ..w......w.. .w.w.....ww. w.w.w.....w. .w.w......w. ..w.......w.
def dfs(x,y):
field[x][y] = "."
for dx in range(-1,2):
for dy in range(-1,2):
nx = x+dx
ny = y+dy
if 0<=nx<n and 0<=ny<m and field[nx][ny]=="W":
dfs(nx,ny)
n, m = 10, 12
field = [['W', '.', '.', '.', '.', '.', '.', '.', '.', 'W', 'W', '.'],
['.', 'W', 'W', 'W', '.', '.', '.', '.', '.', 'W', 'W', 'W'],
['.', '.', '.', '.', 'W', 'W', '.', '.', '.', 'W', 'W', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', 'W', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', 'W', '.', '.'],
['.', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.', '.'],
['.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', 'W', '.'],
['W', '.', 'W', '.', 'W', '.', '.', '.', '.', '.', 'W', '.'],
['.', 'W', '.', 'W', '.', '.', '.', '.', '.', '.', 'W', '.'],
['.', '.', 'W', '.', '.', '.', '.', '.', '.', '.', 'W', '.']]
res = 0
for i in range(n):
for j in range(m):
if field[i][j] == "W":
dfs(i, j)
res += 1
print(res)
from collections import deque
INF = float("inf")
def bfs():
d = [[INF]*m for i in range(n)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(n):
for j in range(m):
if maze[i][j] == "S":
sx=i
sy=j
if maze[i][j]=="G":
gx=i
gy=j
que = deque([])
que.append((sx,sy))
d[sx][sy] = 0
while len(que)>0:
p = que.popleft()
if p[0]==gx and p[1]==gy:
break
for i in range(4):
nx = p[0]+dx[i]
ny = p[1]+dy[i]
if 0<=nx<n and 0<=ny<m and maze[nx][ny]!="#" and d[nx][ny]==INF:
que.append((nx,ny))
d[nx][ny]= d[p[0]][p[1]]+1
return d[gx][gy]
n = 10
m = 10
maze = [
['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
]
print(bfs())
c = [3,2,1,3,0,2]
a = 620
v = [1,5,10,50,100,500]
for i in range(1,7):
t = min(a//v[-i],c[-i])
a = a - (t*v[-i])
ans = ans+t
print(ans)
t est le plus petit nombre de a / 500 et 500 yens. Ensuite, payez le montant le moins élevé de 500 yens et soustrayez de a.
from operator import itemgetter
n = 5
s = [1,2,4,6,8]
t = [3,5,7,9,10]
st = sorted([(s[i], t[i]) for i in range(n)], key=itemgetter(1))
#print(st)
ans = 0
last = 0
for i in range(n):
if last < st[i][0]:
ans += 1
last = st[i][1]
print(ans)
Soyez prudent car certains problèmes ne peuvent pas être résolus par la méthode gourmande.
Best Cow Line
n = 6
s = "ACDBCB"
t = ""
a = 0
b = n-1
while a<=b: #Jusqu'à ce que la chaîne s'épuise
left = False
i = 0
while a+i <= b: #Est-ce sémantiquement le même que while?
if s[a+i] < s[b-i]:
left = True
break
elif s[a + i] > s[b - i]:
left = False
break
i = i+1
if left:
t = t+s[a]
a = a+1
else:
t = t+s[b]
b = b-1
print(t)
J'ai été surpris de pouvoir comparer la taille des lettres.
if "B">"A":
print("yes")
Cela affichera oui.
Recommended Posts