It's been a few months since I started programming, but I realized that I was overwhelmingly lacking in the knowledge needed to solve atcoder, so I decided to try solving the programming challenge book (commonly known as ant book). I'm also interested in data analysis such as kaggle, so I'll try to solve it with 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))
Sort a and sort them in ascending order. Since the same value cannot be obtained twice, j should be selected from i and above. Also, it is necessary to leave two values larger than i.
Ant (POJ No.1852)
L = 10
n = 3
x = [2,6,7]
#When finding max
ans = L-min(x)
#When seeking min
for i in range(n):
x[i] = min(x[i],L-x[i])
ans2 = max(x)
print("min =",ans2)
print("max =",ans)
Actually, you can see that there is no problem even if you think that the two ants passed each other and proceeded as they were. … (Omitted)… To find the maximum time, you need to find the maximum distance at the bridge.
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 #Left edge of search range
r = n #Right edge of search range
while (r - l >= 1) and exist==False: #End the process when the search range is exhausted
i = (l + r) // 2 #Give i a position in the middle of the data
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")
was difficult,, I searched for possible options by dividing the four selections into two and two. The two possible values at this time are the same. If you put the possible values in the list a, you can find a [i] == m-a [j]. From here, do a binary search to find the answer.
n = 4
a = [1,2,4,7]
k = 14
def dfs(i,s):
if i == n: #After deciding n pieces, return whether the sum sum so far is equal to k
#print(s)
return s == k
if dfs(i+1,s): #a[i]If you do not use
#print("not use", i)
return True
if dfs(i+1,s+a[i]): #a[i]When using
#print("use", i)
return True
#print("f",s)
return False #a[i]Returns false because it is not k regardless of whether it is used or not
if dfs(0,0):
print('Yes')
else:
print('No')
The problem of full search using depth-first search (dfs). I'm checking everything with and without a [i] to see if it's equal to k. It may be easier to understand if you remove the print that is a comment.
Lake Counting Input example) 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 is the smaller number of a / 500 and 500 yen. Then, pay the lesser amount of 500 yen and subtract from 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)
Be careful because there are some problems that cannot be solved by the greedy algorithm.
Best Cow Line
n = 6
s = "ACDBCB"
t = ""
a = 0
b = n-1
while a<=b: #Until the string runs out
left = False
i = 0
while a+i <= b: #Is it the same as while in terms of meaning?
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)
I was surprised to be able to compare the size of letters.
if "B">"A":
print("yes")
This will output yes.
Recommended Posts