[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 % |
- Display rate, ash does not include first-time participants
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)
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