Review of atcoder ABC158, up to question E (Python)

3/14 Corrected based on the comment. Thank you very much.

Competitive Pro A complete beginner has started participating in Atcoder, so I will write an article for studying. Click here for the contests you participated in. [AtCoder Beginner Contest 158] (https://atcoder.jp/contests/abc158)

The language will be Python. The purpose is a review, so it is not the solution I actually came up with. I'm writing by looking at explanations and other answers. A - Station and Bus Is a character string given as station information, and does it include two types of stations, company A and company B? Is the problem.

In the actual submission, I honestly turned the string for to see if it contained a different station. In this case, only three strings are given, so you can simply compare them.

s = input()
if s[0] == s[1] or s[1] == s[2]: print('No')
else: print('Yes')

B - Count Balls If you put a fixed number of blue and red balls, how many blues are included by a specific point? Is the problem.

When I tried to turn this with for honestly, the calculation time was over. At this point I finally realize that it's not such a game. I submitted it with a much dirty code than below.

N, A, B = map(int, input().split())
out = N // (A + B) * A
rem = min(N % (A + B), A)
print(out + rem)

I thought after seeing the explanation that the remainder calculation is convenient when finding the remaining number.

C - Tax Increase Is there a unit price of A yen with the reduced tax rate applied and B yen without it? Is the problem.

In order to narrow down the calculation range, first set the minimum and maximum values that satisfy the condition of A, and then check whether the condition of B is satisfied in that range. Specifying this range was awkward, and although I was at the math level, I was confused and messed up.

import math
A, B = map(int, input().split())
minV = math.ceil(A / 0.08)
maxV = (A + 1) // 0.08
for i in range(minV, maxV):
    if int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

However, in this problem, the setting of a narrow range of $ 1 \ leq A, B \ leq 100 $ is clearly stated from the beginning, so it seems that it was good to search from 1 obediently. Since the amount of calculation is O (n), it is much better than clogging up with unnecessary things.

A, B = map(int, input().split())
maxV = 1010 #Any value higher than this will never satisfy condition B.
for i in range(1, maxV):
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

D - String Formation It is a problem of changing the character string according to the given command.

I wrote the following in a straightforward manner. I submitted such an answer and the calculation time was over.

s = input()
n = int(input())
for i in range(n):
    Q = input().split()
    if Q[0] == '1':
        s = s[::-1]
    else:
        if Q[1] == '1':
            s = Q[2] + s
        else:
            s = s + Q[2]
print(s)

According to the explanation, it seems that it takes time for each operation to invert the character string. Instead of actually flipping it, you should keep information about whether it is flipping or not. Also, since it takes time to add to the beginning of the array, it seems necessary to add to the end of the array.

That's why I added a variable isReverse that indicates "whether it is inverted". Added the variable top that stores the information at the beginning so that it will always be the "process to add to the end" of the character string.

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)

You can now do it in time.

E - Divisible Substring

The question is how many intervals are divisible by $ p $ in a given sequence.

This is what I submitted. I checked all the permutations and the amount of calculation of $ O (n ^ 2) $, of course, the time was over.

n, p = map(int,input().split())
s = input()
count = 0
for i in range(n):
    for j in range(1, n - i + 1):
        num = int(s[i: i + j])
        if num % p == 0:
            count += 1
print(count)

This seems to require mathematical techniques. It was hard to just read the commentary, so I watched the commentary video.

First, number the given character string from the right.

D = [d_N, d_{N - 1}, \cdots, d_1, d_0]

The value obtained by multiplying each value by $ 10 ^ i $ is the value you actually want to handle.

D' = [d_N\times 10^N, d_{N - 1}\times 10^{N- 1}, \cdots, d_1\times 10, d_0]

Consider the remainder of dividing $ p $ for each number of digits. However, "when dividing by 2" and "when dividing by 5" are excluded because they interfere with the multiplier of 10. Therefore, we will classify the cases. (i) For $ p \ neq 2, 5 $

M = [(d_N\times 10^N)\% p, (d_{N - 1}\times 10^{N- 1})\% p, \cdots, (d_1\times 10)\% p, (d_0)\% p]

Let's express the obtained remainder term as $ m_i . $ M = [m_N, m_{N - 1}, \cdots, m_1, m_0]$$ The sum of the numbers from 0 to the i-th digit $ V_i $ is $ V_i = \sum^i_{k = 0} d_i \times 10^i $ It can be found by. The remainder $ s_i $ obtained by dividing that number by p is $ s_i = (\sum^i_{k = 0} m_i) \% p $ It can be found by. Let's write this in a sequence. $ S = [s_N, s_{N - 1}, \cdots, s_1, s_0]$ If you cut out the interval where this $ s_i $ matches, it will be a value that can be divided by $ p $. So you just have to count the number of combinations. Also, since the digits that satisfy $ s_i = 0 $ are divisible as they are, the number is also counted.

(ii) If $ p = 2, 5 $

The number divisible by 2 and the number divisible by 5 can be determined by looking only at the last digit. It can be obtained by summing all possible combinations (n ways if the number is the nth digit from the left) when the number that satisfies the condition is set to the 1st digit.

However, in order to make this even faster, the distributive law of modulo calculation

ab \mod c = (a \mod c)(b\mod c)\mod c

We also use to calculate the remainder for $ 10 ^ i $. I didn't notice this (or rather, I didn't know the law of modulo calculation), and even while looking at other people's answer examples, TLE occurred frequently.



n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

For the time being, I will conclude the article so far. If I have time, I would like to add question F as well.