Es ist ein paar Monate her, seit ich mit dem Programmieren angefangen habe, aber mir wurde klar, dass mir das Wissen, das zum Lösen von atcoder benötigt wird, überwiegend fehlte, und ich beschloss, das Programming Challenge Book (allgemein bekannt als Arimoto) zu lösen. Ich interessiere mich auch für Datenanalysen wie kaggle, also werde ich versuchen, sie mit Python zu lösen.
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))
Sortieren Sie a und ordnen Sie sie in aufsteigender Reihenfolge an. Der gleiche Wert kann nicht zweimal erhalten werden, wählen Sie also j aus i und höher. Es ist auch notwendig, zwei Werte größer als i zu lassen.
Ant (POJ No.1852)
L = 10
n = 3
x = [2,6,7]
#Bei der Suche nach max
ans = L-min(x)
#Bei der Suche min
for i in range(n):
x[i] = min(x[i],L-x[i])
ans2 = max(x)
print("min =",ans2)
print("max =",ans)
Eigentlich können Sie sehen, dass es kein Problem gibt, auch wenn Sie denken, dass die beiden Ameisen aneinander vorbeigegangen sind und so vorgegangen sind, wie sie waren. … (Ausgelassen)… Um die maximale Zeit zu ermitteln, müssen Sie die maximale Entfernung an der Brücke ermitteln.
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 #Linker Rand des Suchbereichs
r = n #Rechter Rand des Suchbereichs
while (r - l >= 1) and exist==False: #Beenden Sie den Vorgang, wenn der Suchbereich erschöpft ist
i = (l + r) // 2 #Geben Sie die mittlere Position der Daten an
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")
war schwierig,, Ich suchte nach möglichen Optionen, indem ich die vier Auswahlen in zwei und zwei teilte. Die zwei möglichen Werte zu diesem Zeitpunkt sind gleich. Wenn Sie die möglichen Werte in die Liste a aufnehmen, finden Sie a [i] == m-a [j]. Führen Sie von hier aus eine Zweiteilung durch, um die Antwort zu finden.
n = 4
a = [1,2,4,7]
k = 14
def dfs(i,s):
if i == n: #Geben Sie nach der Entscheidung für n Teile zurück, ob die bisherige Summensumme gleich k ist
#print(s)
return s == k
if dfs(i+1,s): #a[i]Wenn Sie nicht verwenden
#print("not use", i)
return True
if dfs(i+1,s+a[i]): #a[i]Beim Benutzen
#print("use", i)
return True
#print("f",s)
return False #a[i]Gibt false zurück, da es nicht k ist, unabhängig davon, ob es verwendet wird oder nicht
if dfs(0,0):
print('Yes')
else:
print('No')
Vollständiges Suchproblem mit Tiefenprioritätssuche (dfs). Ich überprüfe alles mit und ohne [i], um zu sehen, ob es gleich k ist. Es ist möglicherweise einfacher zu verstehen, wenn Sie den Ausdruck entfernen, der ein Kommentar ist.
Lake Counting Eingabebeispiel) 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 ist die kleinere Zahl von a / 500 und 500 Yen. Dann zahlen Sie den geringeren Betrag von 500 Yen und subtrahieren von 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)
Seien Sie vorsichtig, da es einige Probleme gibt, die mit der gierigen Methode nicht gelöst werden können.
Best Cow Line
n = 6
s = "ACDBCB"
t = ""
a = 0
b = n-1
while a<=b: #Bis die Saite ausgeht
left = False
i = 0
while a+i <= b: #Ist es semantisch dasselbe wie während?
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)
Ich war überrascht, die Größe der Buchstaben vergleichen zu können.
if "B">"A":
print("yes")
Dies wird ja ausgegeben.