[PYTHON] AtCoder Beginner Contest 103 Review of past questions

Time required

Impressions

Since the problems that I am good at finish so quickly, I want to be able to solve problems that I am not good at (I think) such as counting. Also, I want to do my best tonight with the intention of dying AGC for the first time in 5 months. Every time AGC is increasing the rate by more than 100, I will do my best to succeed this time as well.

Problem A

A I got the impression that the problem was rather difficult. If you decide the number in the middle, the solution will be decided in one way, so you can output the smallest solution that can be obtained from the number in the middle (three ways).

answerA.py

a,b,c=map(int,input().split())
print(min(abs(b-a)+abs(a-c),abs(b-c)+abs(c-a),abs(a-b)+abs(b-c)))

B problem

All you have to do is write out all the possible patterns. String manipulation in Python is convenient!

answerB.py

s,t=input(),input()
for i in range(len(s)):
    if s[i:]+s[:i]==t:
        print("Yes")
        break
else:
    print("No")

C problem

The formula became too simple and I became anxious. The largest remainder after dividing $ m $ for an element $ a_i $ in the sequence is $ a_i-1 $, which is considered for all the elements in the sequence $ a $. The solution is $ -n $ from the sum.

Also, like the answer, $ m = a_1 \ times a_2 \ times… \ times a_n-1 $ can be used to achieve such $ m $.

answerC.py

n=int(input())
a=list(map(int,input().split()))
print(sum(a)-n)

D problem

First of all, I looked at the first sample and experimented. Then, if there is at least one bridge between the ** $ a_i $ th and $ b_i $ th islands **, the request $ i $ can be met.

If you think simply here, I thought that it would be better to go from the bridge that can meet many requests in order. However, I felt that it would be difficult in terms of the amount of calculation, as there might be patterns that would be missing.

Therefore, I thought about counting greedily from the end. If you can reach this idea, you can use the idea of interval scheduling. That is, ** a bridge is created at the right end of the first section based on the order from the section where the right end of the section is on the leftmost side, and if that bridge is included in the next section, the next section is further investigated and the bridge is examined. If the bridge is not included in the next section, you can fulfill all your requests with the minimum number of bridges by making another bridge and then investigating the next section.

Also, if there are continuous sections that can be represented on a number line, it is very important to ** sort and think based on the order **, so I think you should keep in mind (self-advised). In addition, after sorting, it can be reduced to various patterns such as DP, greedy method (including interval scheduling), BIT, seg tree, scale method, potato method, graph, and so on.

Furthermore, in order to arrive at the correct idea, it is difficult to ** somehow select an algorithm **, so I think it is important to be conscious of ** verbalizing it firmly **.

answerD.py

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
ab.sort(key=lambda x:x[1])
ans=[[ab[0][1]-1,ab[0][1]]]
ab.pop(0)
for i in range(m-1):
    if ans[-1][0]>=ab[i][0]:
        continue
    else:
        ans.append([ab[i][1]-1,ab[i][1]])
print(len(ans))