--Reduce is convolution --A type of higher-order function --A higher-order function is a function that takes a function as an argument (below is an example of a higher-order function).
map (execute a function on each iterator and return it on the iterator)filter (Iterator returns only those whose function execution result is True for each iterator)
--Used in the form of reduce (function, iterater, initializer (option))
--Execute function to the iterator in order and return the result――In the competition pro, sometimes the rounding of the digits makes it look correct as a code, but there are cases where it becomes WA (5 and 14. above).
--Rounding
There are cases where using round () is useless, so use (<num> * 2 + 1) // 2.
--Root
There are cases where using math.sqrt () is useless, so use <num> ** (decimal ("0.5 ")).
from Decimal import decimal is required.decimal is given as a character string (if it is given as a numerical value, a rounding error will occur at that point).--When searching for values from a sorted list, it is (often) better to do a binary search than a linear search.
--It can be used in the form of <idx> = bisect.bisect_left (<list>, <value>).
By using a binary search, the amount of calculation can be reduced from $ O (n) $ to $ O (\ log n) $ compared to a linear search.
AGC057 A Shik and Stone
--Time required: less than 10 minutes
--Point: At first, I thought I would use collections.counter, but if I just want to count the number of#, I felt thatcount ()of<list>is enough, so I changed it there. And implement
# AGC057 A Shik and Stone
h,w = map(int, input().split())
_list = []
for i in range(h):
_list += list(input())
if _list.count("#") == (h+w-1):
print("Possible")
else:
print("Impossible")
ABC070 C Multiple Clocks
--Time required: 11 minutes
--Point: I quickly realized that it was a problem to find LCM, so I googled how to implement LCM.
The time required to study reduce is not included in the required time.
# ABC070 C Multiple Clocks
from functools import reduce
from fractions import gcd #python3.Before 5
# from math import gcd #python3,5 or later
def lcm_base(x,y):
return (x*y)//gcd(x,y)
def multi_lcm(numbers):
return reduce(lcm_base, numbers)
n = int(input())
t_list = [int(input()) for i in range(n)]
print(multi_lcm(t_list))
ABC123 C Five Transportations --Time required:-minutes --Point: You can see it by writing an example on paper.
# ABC123 C Five Transportations
import math
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
_min = min([a,b,c,d,e])
_ans = math.ceil(n/_min)
print(_ans+4)
AGC008 A Simple Calculator Impressions ――It's easy to see, but there are surprisingly many patterns (maybe you can make it more beautiful). ――I got WA twice because I did a rough pattern division when either of them was 0.
# AGC008 A Simple Calculator
x, y = map(int, input().split())
_x = abs(x)
_y = abs(y)
if x > 0 and y > 0:
if x <= y:
print(y-x)
else:
print(x-y+2)
elif x * y < 0:
print(abs(_y-_x)+1)
elif x == 0:
if y >= 0:
print(y)
else:
print(_y+1)
elif y == 0:
if x > 0:
print(x+1)
else:
print(_x)
else:
if _x < _y:
print(_y-_x+2)
else:
print(_x-_y)
Impressions
--The problem itself is simple. There seemed to be no problem in calculating the amount of calculation for all the elements one by one, so there is no problem there either.
--Since there are cases where rounding cannot be done correctly with round (), rounding is done with (<num> * 2 + 1 // 2). (Why round () is not rounded correctly is omitted here)
#ARC059 C together
n = int(input())
a_list = [int(x) for x in input().split()]
ave = ((sum(a_list) / len(a_list)) * 2 + 1) // 2
ans = sum([(x-ave)**2 for x in a_list])
print(int(ans))
Impressions ――It's a moment when ʻitertools.groupby ()` comes up. --However, there seems to be no way to get the number of iterator elements, so it is necessary to use up the iterator like the program below.
#ABC047 C One-dimensional reversi
import itertools
s = itertools.groupby(list(input()))
ans = 0
for _ in s:
ans += 1
print(ans - 1)
ABC143 D Triangles
bisect).By using the second, the amount of calculation can be reduced from $ O (n ^ {3}) $ to $ O (n ^ {2} \ log n) $.
# ABC143 D Triangles TLE
n = int(input())
l_list = [int(x) for x in input().split()]
l_list.sort()
ans = 0
# (i < j < k) -> (_a < _b < _c)
for i in range(n-2):
_a = l_list[i]
for j in range(i+1,n-1):
_b = l_list[j]
_tmp = _a + _b
for k in range(j+1,n):
_c = l_list[k]
if _c < _tmp:
ans += 1
else:
break
print(ans)
# ABC143 D Triangles
import bisect
n = int(input())
l_list = [int(x) for x in input().split()]
l_list.sort()
ans = 0
for i in range(n-2):
_a = l_list[i]
for j in range(i+1,n-1):
_b = l_list[j]
_tmp = bisect.bisect_left(l_list, _a+_b)
if j < _tmp:
ans += _tmp - j - 1
print(ans)
--You can solve it immediately by using Counter ().
#ABC035 B drone
from collections import Counter
s = Counter(input())
t = int(input())
l = s["L"]
r = s["R"]
u = s["U"]
d = s["D"]
q = s["?"]
x = r-l
y = u-d
if t == 1:
print(abs(x) + abs(y) + q)
else:
_tmp = abs(x) + abs(y)
if _tmp >= q:
print(_tmp - q)
elif (_tmp - q) % 2 == 0:
print("0")
else:
print("1")
AGC011 A Airport Bus
bisect () (binary search), but it became TLE.
――Part 2
--Since there are many processes to get data from the beginning of the list, I tried using deque and it passed.Reaffirmed that if you want to get data from the top of the list, you should queue it.
# AGC011 A Airport Bus TLE
import bisect
n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]
t_list.sort()
ans = 0
while len(t_list) > 0:
_tmp = t_list[0] + k
_idx = bisect.bisect_right(t_list, _tmp)
if c <= _idx + 1:
t_list = t_list[c:]
else:
t_list = t_list[_idx:]
ans += 1
print(ans)
# AGC011 A Airport Bus
import bisect
from collections import deque
n, c, k = map(int, input().split())
t_list = [int(input()) for _ in range(n)]
t_list.sort()
t_list = deque(t_list)
ans = 0
while len(t_list) > 0:
_tmp = t_list.popleft() + k
_idx = bisect.bisect_right(t_list, _tmp)
if c-1 <= _idx:
for _ in range(c-1):
t_list.popleft()
else:
for _ in range(_idx-1):
t_list.popleft()
ans += 1
print(ans)
AGC002 B Box and Ball
# AGC002 B Box and Ball
n, m = map(int, input().split())
b_list = [0] * (n+1)
b_list[1] = 1
c_list = [1] * (n+1)
for i in range(m):
_x, _y = map(int, input().split())
c_list[_x] -= 1
c_list[_y] += 1
if b_list[_x] == 1:
b_list[_y] = 1
if c_list[_x] == 0:
b_list[_x] = 0
print(sum(b_list))
ABC078 C HSI
# ABC078 C HSI
n, m = map(int, input().split())
i = (1/2)**m
x = (100*(n-m) + 1900*m) / i
print(int(x))
#ARC054 A Moving walkway
l, x, y, s, d = map(int, input().split())
ans = float("Inf")
j = (d-s)%l
r = (s-d)%l
ans = min(ans,j/(y+x))
if y > x:
ans = min(ans,r/(y-x))
print(ans)
ABC065 C Reconciled?
# ABC065 C Reconciled?
import math
n, m = map(int, input().split())
A = 10**9 + 7
if abs(n-m) > 1:
print("0")
elif n == m:
print(((math.factorial(m)**2)*2)%A)
else:
print((math.factorial(m)*math.factorial(n))%A)
math.sqrt (), the digits may be rounded to NG.
――Part 2
--You can calculate correctly by using decimal.Decimal ().#Panasonic Programming Contest 2020 C Sqrt Inequality WA
import math
from decimal import Decimal
a, b, c = map(Decimal, input().split())
_a, _b, _c = map(math.sqrt, [a,b,c])
if _a + _b < _c:
print("Yes")
else:
print("No")
#Panasonic Programming Contest 2020 C Sqrt Inequality
from decimal import Decimal
a, b, c = map(int,input().split())
a, b, c = Decimal(a),Decimal(b),Decimal(c)
if a**Decimal("0.5") + b**Decimal("0.5") < c**Decimal("0.5"):
print('Yes')
else:
print('No')
Recommended Posts