AtCoder C problem summary that can be solved in high school mathematics

This article is an article (16th day) of Yugen Club Advent Calendar 2019. ** Contains spoilers about solving the AtCoder Beginner Contest. ** Please be careful when reading.

You can become light blue with just the power of mathematics

This is fujioka_math, who participated 27 times in the summer. I wanted to add some fun to my life, so I started AtCoder, which people around me were doing. graph.png It turned light blue in about 5 months. (The image is as of 12/16. The account is fujioka_1115)

It turned light blue, but honestly I'm not familiar with the algorithm at all. It feels like I've reached the limit without solving the ABC E problem by quickly solving a problem that can be solved simply with the power of mathematics.

Push with math skills

ABC's C and D problems have some problems that can be solved even if the algorithm is not familiar. For example, something like this.

Show problem
ABC144 D - [Water Bottle](https://atcoder.jp/contests/abc144/tasks/abc144_d) ** [Summary of problem] ** A rectangular parallelepiped container with a bottom of $ a \ times a $ and a height of $ b $ contains $ x $ of water. When tilting a container (around one side of a square) without overflowing water, how many times can it be tilted?
Display sample answers
This is a completely math problem. Use arctan, the inverse function of tan. It is easy to divide the case by the size of $ x $ and $ \ frac {a ^ 2b} 2 $. Is arctan a university content? However, since the property of arctan is not used at all here and the inverse function itself is the content of Mathematics III, it is assumed to be high school mathematics.
import math
a,b,x=[int(s) for s in input().split()]
if x>a*a*b/2:
  h=2*(a*a*b-x)/(a*a)
  print(math.degrees(math.atan(h/a)))
else:
  k=2*x/(a*b)
  print(math.degrees(math.atan(b/k)))

This is a D problem but does not use an algorithm. This time, we will introduce problems that can be easily solved with such math skills, so even club members who are new to programming should try more and more.

Target problem

Language and precautions

C problem

ABC101 C - Minimization

Concept
If you don't overlook the problem statement "$ A_1, A_2, \ dots, A_n $ is a rearrangement of $ 1, 2, \ dots, N $", the whole number of intervals of $ K $ in length is enough. Can you cover it? I notice that it is a problem.
Sample answer
N,K=[int(s) for s in input().split()]
print((N+K-3)//(K-1))

The required number of intervals is $ \ left \ lceil \ dfrac {N-1} {K-1} \ right \ rceil $. Here, $ \ left \ lceil \ dfrac nm \ right \ rceil = \ left \ floorloor \ dfrac {n + m-1} n \ right \ rfloor $ is used and the ceiling function is not called. (I also learned this formula from the explanation of ABC.)

ABC105 C - Base -2 Number

Concept
It is a development of $ n $ radix learned in Mathematics I, so there is nothing to worry about. The remainder after division may be output in order.
Sample answer
N=int(input())
ls=[]
while True:
  ls.append(N%2)
  N=-(N//2)
  if N==0:
    break
print(*reversed(ls),sep="")

The hardest part of this problem was to output a list of numbers like [1,1,0,1] in reverse order like 1011, and then connect them. I've previously told you that you can easily connect and output lists with print (* ls, sep = ""). Then, in detail, I lost when $ N = 0 $.

ABC108 C - Triangular Relationship

Concept
Use the idea of the "integer" field of Math A. When $ K $ is odd, $ a + b, b + c, c + a $ are all multiples of $ K $, which means that $ a, b, c $ are all multiples of $ K $. Equivalent. When $ K $ is even, "$ a, b, c $ are all multiples of $ K $, or $ a, b, c $ are all multiples of $ \ frac K2 $ and not multiples of $ K $" Equivalent to. Therefore, in each case, the number of multiples should be checked, squared, and added.
Sample answer
N,K=[int(s) for s in input().split()]
if K%2==1:
  print((N//K)**3)
else:
  print((N//K)**3+((N//(K//2)-N//K)**3))

ABC109 C - Skip

Concept
The greatest common divisor of $ x_1-X, x_2-X, \ dots, x_n-X $ should be output. Python has a function gcd that finds the greatest common divisor, but AtCoder uses gcd in the fractions module instead of the math module because the Python version is 3.4. Note that this can return a negative value.
Sample answer
import fractions
N,X=[int(s) for s in input().split()]
ls=[int(s)-X for s in input().split()]
a=0
for e in ls:
  a=fractions.gcd(a,e)
print(abs(a))

ABC116 C - Grand Garden

Concept
I didn't know how to do it at first glance, but ...

It can be seen that the sum of (absolute values) of the height difference between the adjacent flowers and the ground at both ends is twice the number of times of watering required. zu2.png

More simply, just add the green part and you'll get the answer. This should be output.

Sample answer
N=int(input())
ls=[int(s) for s in input().split()]
ls.append(0)
a=0
for i in range(N):
  a+=max([0,ls[i]-ls[i+1]])
print(a)

ABC117 C - Streamline

Concept
If anything, the problem of asking if you can do basic operations on arrays. If $ X_1
  • Consider the difference sequence $ Y_n = X_ {n + 1} -X_n $
  • Remove the top $ N-1 $ pieces of $ Y_1, \ dots, Y_n $
  • Output the sum of the remaining ones.
  • Since it is an arithmetic progression, is it math B?

    Sample answer
    N,M=[int(s) for s in input().split()]
    if N>=M:
      print(0)
    else:
      ls=[int(s) for s in input().split()]
      ls.sort()
      d=[ls[i+1]-ls[i] for i in range(M-1)]
      d.sort()
      print(sum(d[:M-N]))
    

    The answer is automatically 0 for $ N \ ge M $. The d [: M-N] in the last line is the array d cut out in the middle (before M-N).

    ABC118 C - Monsters Battle Royale

    Concept
    Only outputs the greatest common divisor of $ A_1, A_2, \ dots, A_n $.
    Sample answer
    import fractions
    N=int(input())
    ls=[int(s) for s in input().split()]
    a=0
    for e in ls:
      a=fractions.gcd(a,e)
    print(a)
    

    ABC123 C - Five Transportations

    Concept
    The slowest of the five modes of transportation is the key. The rate-determining step in chemistry.

    If you ask for the time it takes to carry N people by the slowest means of transportation, that time + 4 minutes is the answer.

    Sample answer
    import math
    N = int(input())
    A = int(input())
    B = int(input())
    C = int(input())
    D = int(input())
    E = int(input())
    X = min([A,B,C,D,E])
    t=math.ceil(N/X)
    print(t+4)
    

    Or use $ \ left \ lceil \ dfrac NX \ right \ rceil = \ left \ floorloor \ dfrac {N + X-1} X \ right \ rfloor $

    N = int(input())
    ls = [int(input()) for i in range(5)]
    X = min(ls)
    print((N+X-1)//X+4)
    

    ABC126 C - Dice and Coin

    Concept
    Math A problem. No special notes. You can use log, but you can run a double for loop without using it.
    Sample answer
    import math
    N,K=[int(s) for s in input().split()]
    a=0
    for i in range(N):
      a+=2**(-max([0,math.ceil(math.log2(K/(i+1)))]))
    print(a/N)
    

    Alternatively, you can combine a for statement and a while statement (double loop) and write as follows. In my case, there are fewer simple mistakes when using this "smart" method.

    N,K=[int(s) for s in input().split()]
    a=0
    for i in range(N):
      x=i+1
      n=0
      while x<K:
        n+=1
        x*=2
      a+=2**(-n)
    print(a/N)
    

    ABC129 C - Typical Stairs

    Concept
    A famous problem in high school math. Those that use a recurrence formula. When the number of ways to go up to the $ n $ stage is $ b_n $
    b_{n}=  \begin{cases}
         b_{n-1}+b_{n-2} \quad (n\text{The steps are not broken})\\
         0\qquad (n\text{The steps are broken})
      \end{cases}
    

    Holds for $ n \ ge2 $. The method of implementing this recursion is actually difficult for beginners, so I was wondering whether to deal with it in this article, but I dealt with it because it is too high school mathematics.

    Sample answer
    I used what is called "memoization recursion".
    MOD=10**9+7
    N,M=[int(s) for s in input().split()]
    ls=[1 for _ in range(N+1)]
    for i in range(M):
      ls[int(input())]=0
    for n in range(2,N+1):
      if ls[n]!=0:
        ls[n]=(ls[n-1]+ls[n-2])%MOD
    print(ls[N])
    

    ABC130 C - Rectangle Cutting

    Concept
    I have nothing to say. Bisection is always possible, and if the point $ (x, y) $ is the intersection of the diagonal lines of the rectangle, multiple cuts are possible. In some cases, it should be dealt with in the "line symmetry, point symmetry" class of junior high school.
    Sample answer
    W,H,x,y = [int(s) for s in input().split()]
    if 2*x==W and 2*y==H :
      print(W*H/2,1)
    else:
      print(W*H/2,0)
    
    

    ABC131 C - Anti-Division

    Concept
    Completely high school math. The "set and logic" field of Mathematics A. "Total number"-"Number of multiples of $ C $"-"Number of multiples of $ D $" + "Number of common multiples of $ C, D $" may be output.

    The number of multiples of $ x $ that is greater than or equal to $ A $ and less than or equal to $ B $ is "the number of multiples of $ x $ that is less than $ B $"-"the multiple of $ x $ that is less than $ A-1 $". It is calculated by "number".

    By the way, the fractions module does not have a function lcm to find the least common multiple. Therefore, I tried to find the least common multiple with $ C \ times D \ div gcd (C, D) $. This is the content of the "integer" field of Math A.

    Sample answer
    import fractions
    A,B,C,D = [int(s) for s in input().split()]
    L=C*D//fractions.gcd(C,D)
    print(B-(A-1)
          -(B//C)+((A-1)//C)
          -(B//D)+((A-1)//D)
          +(B//L)-((A-1)//L))
    

    There is also a simpler C problem

    So far, the Difficulty displayed in At Coder Problems, that is, the median rate of correct answerers is 400 (brown) or more, and actually more There are many things that can be easily solved (equivalent to gray).

    You will end up learning algorithms

    D problem and above

    If you have more than D problem, the problem of "this part of high school mathematics!" Will decrease.

    Moreover, even if it is simplified by the power of mathematics, implementation often still requires knowledge of algorithms (being caught in the limitation of execution time), so "easy" problems such as 144D and 139D introduced at the beginning. The reality is that there are few.

    It's fun to study algorithms

    So, let's study the algorithm after all.

    It's fun to see the explanations of unsolvable problems with very vivid solutions and interesting algorithms (although I'm depressed right after reading). If you can enjoy this, you can enjoy the competition pro.

    Recommended Posts

    AtCoder C problem summary that can be solved in high school mathematics
    [High school mathematics + python] Logarithmic problem
    Python standard input summary that can be used in competition pro
    Atcoder Beginner Contest A, B Input summary Python that tends to be a problem
    Functions that can be used in for statements
    Building Sphinx that can be written in Markdown
    Summary of statistical data analysis methods using Python that can be used in business
    Basic algorithms that can be used in competition pros
    Python knowledge notes that can be used with AtCoder
    ANTs image registration that can be used in 5 minutes
    Non-linear simultaneous equations can be easily solved in Python.
    [Atcoder] [C ++] I made a test automation tool that can be used during the contest
    Format summary of formats that can be serialized with gensim
    Neural network to understand and implement in high school mathematics
    Goroutine (parallel control) that can be used in the field
    Text analysis that can be done in 5 minutes [Word Cloud]
    Goroutine that can be used in the field (errgroup.Group edition)
    AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
    Scripts that can be used when using bottle in Python
    SIR model that even junior high school students can understand
    Evaluation index that can be specified in GridSearchCV of sklearn
    AtCoder Beginner Contest # 002 C Problem
    AtCoder Regular Contest # 002 C Problem
    Make a Spinbox that can be displayed in Binary with Tkinter
    A timer (ticker) that can be used in the field (can be used anywhere)
    About character string handling that can be placed in JSON communication
    Make a Spinbox that can be displayed in HEX with Tkinter