[PYTHON] AtCoder Beginner Contest 090 Review of past questions

Time required

Impressions

The D problem was terrible. It was later than when I was solving it in December. I will review it firmly.

Problem A

Since it is diagonal, the row and column numbers are the same.

answerA1.py

s=[input()[i] for i in range(3)]
print("".join(s))

B problem

Judge whether it is a palindrome in order from A to B. You just have to judge one character at a time.

answerB.py

a,b=map(int,input().split())
ans=0
for i in range(a,b+1):
    s=str(i)
    l=len(s)
    for i in range(l//2):
        if s[i]!=s[l-1-i]:
            break
    else:
        ans+=1
print(ans)

C problem

** I misread the question sentence ** and thought that there were ** cards in all of the 9 squares **, but it was easy because I only had to ** exist **. It's spicy.

answerC.py

n,m=map(int,input().split())
if n==1 and m==1:
    print(1)
elif n==1:
    print(m-2)
elif m==1:
    print(n-2)
else:
    print((n-2)*(m-2))

D problem

The easiest way is to move both a and b, but it's O ($ n ^ 2 ) so it's too late. In this problem, it is clear from experiments that there is some relationship between the two numbers **, so it is only necessary to fix one and find the other with O (1). I thought it might be. Regarding which one to fix here, I found that if ** a is fixed, moving b will cause irregular movements **. Therefore, think of it as fixing b. First, considering the range of b, the remainder is k or more, so it is k + 1 ~ n. I will fix it in this range, but before that, I thought that ** it is hard to think that the remainder is k + 1 ~ n **, so I decided to draw it considering its complement. Therefore, consider that ** subtract the remainder of 0 ~ k-1 from the number of combinations of b of k + 1 ~ n and a of 1 ~ n ( (nk) \ times n $) **. Consider a ** where b is divided by k + 1 ~ n and the remainder is 0 ~ k-1. A generalized export of such ** a candidates ** would look like this:

Consider the number of candidates for a above. First of all, for l above, it is sufficient to consider how many b are below n, so it can be calculated by n // b. Furthermore, the number of numbers between l * b + 1 and n that have a remainder of 0 to k-1 is the smaller of n divided by b and k-1 (where k = When it is 0, k-1 becomes negative, so it is assumed to be larger than 0). The answer can be obtained by subtracting the above candidates for a ** and thinking about this by moving b.

Through this problem

Experiment and understand the behavior

Write it down and think about it when generalizing

I learned that.

answerD.py

n,k=map(int,input().split())
ans=n*(n-k)
for i in range(k+1,n+1):
    ans-=(k*(n//i))
    ans-=max(0,min(k-1,n%i))
print(ans)