[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!

** A, B, C problems ** of ** AtCoder Beginner Contest 186 ** will be explained as carefully as possible with ** Python3 **.

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 you have more time left for later problems.

If you have any questions or suggestions, please leave a comment or Twitter. Twitter: u2dayo

table of contents

ABC186 Summary Problem A "Brick" Problem B "Blocks on Grid" C problem "Unlucky 7"

Promotion: I made an app called "AtCoderFacts"

I made an app called "AtCoderFacts". You can see the "correct answer rate for each rate" and "performance guideline" that we always do in this article.

That's all for now, but we plan to add more features in the future. Please use it.

ABC186 Summary

Total number of submissions: 6238

performance

Performance AC Score time Ranking(Within Rated)
200 ABC--- 600 77 minutes 4897(4676)Rank
400 ABC--- 600 21 minutes 4123(3902)Rank
600 ABCD-- 1000 99 minutes 3454(3233)Rank
800 ABCD-- 1000 54 minutes 2745(2524)Rank
1000 ABCD-- 1000 31 minutes 2076(1855)Rank
1200 ABCD-- 1000 18 minutes 1510(1290)Rank
1400 ABCD-- 1000 7 minutes 1067(850)Rank
1600 ABCDE- 1500 62 minutes 733(525)Rank
1800 ABCDE- 1500 29 minutes 499(300)Rank
2000 ABCDEF 2100 100 minutes 326(157)Rank
2200 ABCDEF 2100 76 minutes 207(75)Rank
2400 ABCDEF 2100 63 minutes 123(34)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 2343 99.2 % 88.2 % 60.0 % 29.6 % 0.7 % 0.0 %
tea 1252 99.7 % 99.4 % 93.1 % 69.1 % 4.5 % 0.4 %
Green 1023 99.7 % 99.7 % 97.7 % 87.9 % 16.1 % 2.1 %
water 643 99.7 % 99.8 % 99.5 % 97.7 % 46.0 % 12.0 %
Blue 312 100.0 % 100.0 % 100.0 % 99.4 % 72.1 % 55.8 %
yellow 167 99.4 % 99.4 % 99.4 % 98.8 % 92.8 % 84.4 %
orange 39 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 94.9 %
Red 17 100.0 % 100.0 % 100.0 % 100.0 % 94.1 % 100.0 %

Brief commentary

A problem (6188 people AC) "Brick"
You can use
`//` to divide and truncate the remainder.
B problem (5812 people AC) "Blocks on Grid"
You can adjust to the smallest number. It is easy to implement by subtracting $ (minimum value) \ times {H} \ times {W} $ from the sum of blocks.
C problem (4936 people AC) "Unlucky 7"
$ N $ is at most $ 100,000 $, so you can do a full search. In other words, in the for loop, if the if statement determines whether both the $ 10 $ and $ 8 $ base strings of $ i $ contain `'7'`, and if OK, add $ 1 $ to the answer. Is good. If you want a $ 8 $ base string in Python, just write `format (i,'o')`.
D problem (3727 AC) "Sum of difference" [not explained in this article]
If you calculate normally, it will be $ O (N ^ 2) $, so it will not be in time. Let's sort and calculate nicely.
E problem (979 people AC) "Throne" [not explained in this article]
First, divide $ S, K, N $ by the greatest common divisor of $ 3 $. Then you can solve $ S + Kx ≡ 0 \; (mod N) $ to find $ x $. If $ K ^ {-1} $ is the inverse element of $ K $ in $ mod N $, then $ x ≡ -SK ^ {-1} (mod N) $. $ K ^ {-1} $ can be calculated by `pow (K, N-2, N)` if $ N $ is a prime number, but this method cannot be used if it is not a prime number. If it is not a prime number, it can be obtained by using an algorithm called "Extended Euclidean algorithm". It's a pain to implement by yourself, so if you write `pow (K, -1, N)` in Python 3.8, it will do it for you. (Not possible with PyPy) If there is no solution, an error will occur, so if an error occurs in the try-except statement, you can do `print (-1)`.
F problem (475 people AC) "Rook on Grid" [not explained in this article]
Add the number of squares that can be moved in the pattern that moves down and then moves to the right, and the pattern that moves to the right and then moves down. Both patterns count the number of cells that can be moved in duplicate, so use the segment tree to find and subtract the number of duplicates for each row.

Results of me (Unidayo) (reference)

screenshot.87.jpg

I probably misread the F problem (X is vertical and Y is horizontal) to melt the time, but I managed to complete it.

Problem A "Brick"

** Problem page **: A --Brick ** <font color = # 808080> Gray Coder Correct Answer Rate **: 99.2% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 99.7% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.7%

Consideration

The answer is $ N $ divided by $ W $ and the remainder rounded down.

Implementation

You can use the // operator to calculate the number by dividing and truncating the remainder.

code

N, W = map(int, input().split())
print(N // W)

Problem B "Blocks on Grid"

** Problem page **: B --Blocks on Grid ** <font color = # 808080> Gray Coder Correct Answer Rate **: 88.2% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 99.4% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.7%

Consideration

** You can remove blocks from the square, but you cannot add them. ** Therefore, it is not possible to fit the whole number to a larger number than the square with the fewest blocks.

** Therefore, you can fit the whole to the square with the fewest blocks. ** It doesn't make sense to make it smaller than that, as it will only increase the number of operations.

Implementation

The most straightforward method is to have the information of the cells in a two-dimensional list, and in a double loop, find $ (number of blocks)-(minimum value) $ for each cell and add them together.

** But if you think about it, you can find the "sum of the number of blocks" first and subtract $ (minimum) \ times {H} \ times {W} $. This way you don't have to worry about implementing it.

code

H, W = map(int, input().split())

S = 0 #The sum of the number of blocks
A_min = 10000  #The initial value should be a number greater than 100.
for _ in range(H):
    A = [*map(int, input().split())]
    S += sum(A)
    A_min = min(A_min, min(A))  # A_update min

ans = S - A_min * (H * W)

print(ans)

C problem "Unlucky 7"

** Problem page **: C --Unlucky 7 ** <font color = # 808080> Gray Coder Correct Answer Rate **: 60.0% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 93.1% ** <font color = # 008000> Green Coder Correct Answer Rate **: 97.7%

Consideration

Since $ N $ is at most $ 100,000 $, you can ** full search ** in a for loop.

If the for loop does not contain $ 7 $ in both the $ 10 $ and $ 8 $ bases for each number, you can add $ 1 $ to the answer.

The problem is that you want the ** $ 8 $ decimal notation, but there is an easy way to do it. (Details are written in the implementation) **

Implementation

To determine if a number contains $ 7 $, you can convert that number to the string $ S $ and make it if '7' in S. The $ 10 $ decimal string of $ i $ is simply written as str (i).

The $ 8 $ decimal string of $ i $ can be written as format (i,'o') in one shot. You can use oct (i), but I think you should use format because an extra'0o' will stick to your head.

>>> format(8, 'o')
'10'

>>> oct(8)
'0o10'

code

N = int(input())

ans = 0
for i in range(1, N + 1):
    s_decimal = str(i)  #It is a character string
    s_octal = format(i, 'o')  #It is a character string in octal notation of i
    if not(('7' in s_decimal) or ('7' in s_octal)):
        ans += 1

print(ans)

Recommended Posts