We will explain how to solve A, B, C problems of ** AtCoder Beginners Contest 158 ** with ** Python 3 ** as carefully as possible for beginners.
I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.
--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced ――It doesn't take long: The performance goes up and the time left for the D problem increases.
Date: 2020-03-07 (Sat) 21:00 ~ 2020-03-07 (Sat) 22:40 (100 minutes) A Number of people submitting questions: 7053
Performance | AC | time | Ranking | Guideline |
---|---|---|---|---|
400 | ABC- | 63 minutes | 4580th | Tea performance |
600 | ABC- | 23 minutes | 3766th | Brown rate at 8 times |
800 | ABCD | 90 minutes | 2911th place | Green performance |
(Reference) I: Performance 1144 ABCD-- 44:24 (1WA) 1644th </ font>
ABC158A 『Station and Bus』
** Problem page **: A --Station and Bus ** Difficulty **: ★ ☆☆☆☆ ** Point **: String operation
Even if I read only the problem statement, I don't know what to do. In such a case, it is good to see a concrete example with a sample for the time being.
There is a three-character string $ S $ with only
" A "
or" B "
. This is a string that represents the operating companies of the three stations in the city of AtCoder. For example, in the case of" ABA "
, station 1 and station 3 are operated by company A, and station 2 is operated by company B.The stations of different operating companies have different routes, so transportation is inconvenient. Therefore, I decided to operate a bus between the stations of company A and company B.
However, there is not always a combination of stations where buses actually operate. Specifically, if all three stations in the city are stations of the same company, there will be no set of stations operated by buses.
Determine if the bus actually runs.
You don't have to use your imagination to the above levels during the contest, but imagining and writing specific situations can help you understand.
If there are two types of $ S $, such as " ABA "
" ABB "
, " A "
and " B "
, then " Yes "
. If $ S $ has only one character, that is, " AAA "
or " BBB "
, then "No".
Since the number of characters is fixed at 3, it is easy to type " AAA "
and " BBB "
directly.
Be careful not to mistake " No "
and " Yes "
and reverse them. If you make sure that the sample passes each time before submitting it, you will inadvertently lose the WA.
s = input()
if s == "AAA" or s == "BBB":
print("No")
else:
print("Yes")
If the number of characters is not fixed, for example, 1 million characters and you can not type directly, it is good to make a character string with the following code.
s = input()
n = len(s) #s length n
a_only = "A" * n #A string followed by n characters
b_only = "B" * n #A string in which B continues for n characters
if s == a_only or s == b_only:
print("No")
else:
print("Yes")
Or you can use len (set (s))
. I won't explain it this time, but it's useful to remember.
s = input()
num = len(set(s)) #If you convert to set type, the duplication disappears, so you can see the number of types with len
if num == 1:
print("No")
else:
print("Yes")
ABC158B『Count Balls』
** Problem page **: B --Count Balls ** Difficulty **: ★★★★★ ** Point **: Integer (division quotient and remainder), computational complexity
It is the highest level of difficulty as a B problem.
The operation of 10 to the 100th power of the problem sentence, the maximum of the constraint is 10 to the 18th power, and an unimaginably huge number comes out. Humans cannot specifically imagine such a huge number. If you try, it will be confusing, so treat it mechanically and abstractly.
If you read the problem statement and think for a moment, you can see that the written 10 to the 100th power means "substantially infinite" and "large enough", and the number itself has no meaning.
Create an infinitely long row of balls by alternating $ Blue $ blue balls and $ Red $ red balls.
Specify $ N $ in the range of> 1 or more and 100 kyo (= 10,000 times 100 trillion) or less. How many blue balls out of $ N $ from the beginning of the row of balls?
Of course, you can get the answer by simulating the operation with a while loop. However, the problem is that $ N $ can be up to 100K. Even if you use a PC, the calculation will take years to decades without exaggeration, so you need to find it by another method.
What to do is to use "integer division" (division with the remainder that was done in the middle grade of elementary school) to calculate in one shot.
If you think of "the operation of adding $ Blue $ blue balls and $ Red $ red balls" as one set, you can calculate by division. Let's rephrase the operation a little.
Consider the operation of adding "a cylinder containing $ Blue $ blue balls and $ Red $ red balls" to a row one by one.
However, if the number of balls in the row exceeds $ N $ if you add them in the cylinder, we will remove the balls one by one from the cylinder and add them to the row. At this time, the blue ball comes out of the cylinder first.
Forget about the color of the balls, and find the $ Q $ number of cylinders containing $ (Blue + Red) $ balls and the $ R $ number of rose balls. Once you know this, you can easily calculate the number of blue balls.
"Number of cylinders $ Q $" and "Number of rose balls $ R $" means "total number of balls $ N $" and "number of balls per cylinder $ (Blue + Red) $" It is calculated by dividing by.
{N} \div {(Blue + Red)} =Q too R
The "total number of blue balls" you want to find is "total number of blue balls in the cylinder" + "number of blue balls of roses", so you can calculate and add each of them.
There are $ Blue $ blue balls in one cylinder. Therefore, there are $ Blue \ times Q $ blue balls in a $ Q $ book tube.
Only one tube can be opened, so of the $ R $ rose balls, the maximum number of blue balls is $ Blue $. In other words, it is basically $ R $, but if $ R $ exceeds $ Blue $ as shown in the image below, it should be $ Blue $.
In other words, the smaller of $ R $ and $ Blue $, $ min (Blue, R) $.
From the above, the number of balls required is $ {N} \ div {(Blue + Red)} = Q If you say R $ too much
Will be. Let's write this in the code.
n, blue, red = list(map(int, input().split()))
# n / (blue + red) = quot ... rem
quot = n // (blue + red) #Quotient
rem = n % (blue + red) #Remainder
ans = blue * quot + min(blue, rem)
print(ans)
For simple problems, you can name the variable a single letter "a", "b", or "x", but for complex problems it's better to have a name that tells you what the variable is.
I searched and wrote that the English word for quotient is "quotient". It's a waste of time to look up during the contest, so you can use romaji for "sho" or "amari".
ABC158C『Tax Increase』 ** Problem page **: C --Tax Increase ** Difficulty **: ★★ ☆☆☆ ** Point **: How to search all (brute force), handle loops, and truncate
It is a matter of consumption tax. I think it is easier than the B problem because it is easy to imagine concretely and it is not difficult to implement.
Since the upper limit of consumption tax is as small as 100 yen, it seems good to check it by full search (brute force). The specific range is that the consumption tax is 100 yen. The tax-excluded price is 1250 to 1262 yen for 8%, and 1000 to 1009 yen for 10%, so you can check 1 yen from 0 yen to 1009 yen. is.
You don't have to ask for this upper limit of 1009 yen. It is troublesome to ask for it and it causes mistakes, so it is easy and safe to check up to about 10,000 yen.
a, b = list(map(int, input().split()))
ans = -1 #If you can't find the answer-Set 1 to the initial value
#Check by increasing by 1 yen from 0 yen to 9999 yen
for price in range(10000):
#8 consumption tax%And 10%Calculate each
tax_a = int(price * 0.08)
tax_b = int(price * 0.1)
#When the condition is met, assign it to the answer and exit the loop
if tax_a == a and tax_b == b:
ans = price
break
#If the answer is found, the value at that time, if not found, the initial value-1 is displayed
print(ans)
I only need to find the minimum value, so I increase it by 1 yen and when I find it, I try to get out of the loop.
This time, I used int function of built-in function for truncation processing, but from math import floor You can also write
and use the math module floor function. The two behave differently for negative numbers, but they are not relevant for this issue.
Recommended Posts