Daily AtCoder # 52 in Python

Introduction

Last time Today, I will solve 3 AGC-A questions.

** Thoughts ** I understood the idea, but I couldn't implement it. Let $ a $ be a list of $ [0] * (n + 1) $. I wasn't able to implement it because I was trying to handle both'<' and'>' together. N is also about $ 5 * 10 ^ 5 $, so $ O (2N) (complexity ignoring coefficients) $ will pass. First, process from'<'. If $ s [i] =='<' $, then $ a [i + 1] $ becomes $ a [i] + 1 $. Next, we will process'>', but some ingenuity is required. '>' Must be calculated from the back because of the inequality sign. So, multiply range (n) by reversed. If $ s [i] =='>' $, take $ a [i] = max (a [i + 1] + 1, a [i]) $. Finally, take $ sum (a) $.

s = list(input())
n = len(s)

a = [0] * (n+1)
for i in range(n):
    if s[i] == '<':
        a[i+1] = a[i]+1
for i in reversed(range(n)):
    if s[i] == '>':
        a[i] = max(a[i+1]+1,a[i])
print(sum(a))

AGC015-A

** Thoughts ** Since $ N = 10 ^ 9 $, $ O (N) $ will not pass. $ n = 1 $ → 1 if $ a = b $, 0 if $ a \ neq b $. Also, it is 0 when $ a $> $ b $ and 1 when $ a $ = $ b $. Consider the other cases. The minimum sum is not when $ a * n $. This is because the maximum value does not reach $ b $ when all are $ a $. Therefore, it becomes $ a (n-1) + b $. Similarly, the maximum sum is $ b (n-1) + a $. You can make everything from $ a (n-1) + b $ to $ b (n-1) + a $. Therefore, the number of sums is $ b (n-1) + a- {a (n-1) + b} + 1 $. If you calculate this, you can transform it into $ (b-a) (n-2) + 1 $. It can be calculated without transforming the formula, but it was transformed because it should be clean.

n, a, b = map(int,input().split())

if n == 1:
    if a == b:
        print(1)
    else:
        print(0)
elif a >= b:
    if a == b:
        print(1)
    else:
        print(0)
else:
    ans = (b-a)*(n-2)+1
    print(ans)

AGC006-A

** Thoughts ** Since $ N $ is small enough, look for $ N $ in order in either slice of $ s or t $ to find the maximum value it contains in the other.

n = int(input())
s = input()
t = input()

c = 0
for i in range(n):
    d = t[:i]
    if d in s:
        c = i
if s == t: #You can write earlier and skip the for process
    print(n)
else:
    print(2*n-c)

Summary

Why does AGC-A have a difficult impression? It will be brown at this week's ABC. See you again, good night.