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

** AtCoder Beginner Contest 184 **'s ** A, B, C problems ** 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

[ABC184 Summary](# abc184-Summary) [A problem "Determinant"](#a problem determinant) [B problem "Quizzes"](#b problem quizzes) [C problem "Super Ryuma"](#c problem super-ryuma)

ABC184 Summary

Total number of submissions: 7822

performance

Performance AC Score time Ranking(Within Rated)
200 AB---- 300 12 minutes 5984(5769)Rank
400 AB---- 300 6 minutes 4983(4768)Rank
600 AB---- 300 4 minutes 4132(3917)Rank
800 ABC--- 600 88 minutes 3271(3056)Rank
1000 ABC--- 600 37 minutes 2454(2240)Rank
1200 ABCD-- 1000 105 minutes 1767(1556)Rank
1400 ABC--F 1200 97 minutes 1229(1026)Rank
1600 ABCD-F 1600 66 minutes 832(636)Rank
1800 ABCDEF 2100 97 minutes 551(367)Rank
2000 ABCDEF 2100 73 minutes 352(195)Rank
2200 ABCDEF 2100 57 minutes 228(96)Rank
2400 ABCDEF 2100 45 minutes 130(44)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 3253 98.7 % 92.0 % 15.3 % 2.3 % 1.0 % 0.7 %
tea 1499 99.3 % 99.1 % 45.8 % 9.5 % 4.9 % 4.5 %
Green 1184 99.5 % 99.5 % 63.4 % 29.6 % 18.4 % 14.1 %
water 729 99.9 % 99.9 % 78.5 % 58.7 % 49.1 % 54.6 %
Blue 360 99.7 % 99.7 % 94.4 % 88.6 % 86.1 % 88.1 %
yellow 175 96.0 % 96.0 % 93.1 % 94.3 % 91.4 % 96.6 %
orange 31 96.8 % 96.8 % 96.8 % 96.8 % 96.8 % 96.8 %
Red 11 90.9 % 90.9 % 90.9 % 90.9 % 100.0 % 100.0 %

Brief commentary

A problem (7738 people AC) "Determinant"
Even if you don't know the determinant, you can do as you are told.
B problem (7439 people AC) "Quizzes"
It's OK if you simulate it obediently.
C problem (3137 people AC) "Super Ryuma"
I'm not sure, so it's a good idea to try how many moves you can reach each square in a small grid to find the rules. Writing on paper is troublesome and error-prone, so it's a good idea to create a program that outputs straightforward answers.
D problem (1561 AC) "increment of coins" [not explained in this article]
Probability DP.
E problem (1223 AC) "Third Avenue" [not explained in this article]
Breadth-first search is performed.
F problem (1209 AC) "Programming Contest" [not explained in this article]
I just do "half full enumeration" without any special effort.

Results of me (Unidayo) (reference)

screenshot.12.jpg

screenshot.32.jpg

A problem "Determinant"

** Problem page **: A --Determinant ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 98.7% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.3% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

Even if you don't know about the determinant, you can do it exactly as it is written.

code

A, B = map(int, input().split())
C, D = map(int, input().split())

print(A * D - B * C)

Problem B "Quizzes"

** Problem page **: B --Quizzes ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 92.0% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.1% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

Implementation

It's okay if you use the for loop obediently and implement it according to the problem statement. If you prioritize clarity without trying to write it in a cool way, you can reduce mistakes.

code

N, X = map(int, input().split())
S = input()

score = X

for char in S:
    if char == "o":
        score += 1
    else:
        if score > 0:
            score -= 1

print(score)

C problem "Super Ryuma"

** Problem page **: C --Super Ryuma ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 15.3% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 45.8% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 63.4%

Meaning of the problem

$ 1 $ There is a piece called "Super Ryoma" that allows you to move either of the following with your hands.

**-Move your favorite square diagonally (same as the corner of shogi. We will call it ** diagonal movement **) ** **-Turn up, down, left and right 3 times ("Manhattan distance" can move to a square within $ 3 $. We will call it ** Super Ryoma Movement **) **

Since the coordinates of the start and goal are given, please output how many hands "Super Ryoma" can finish.

Consideration

It seems that it doesn't make much sense. ** I'm not sure, so for the time being, I'd like to write a program that honestly calculates and outputs the number of movements to find the law. You can write it on paper, but it's easier and less error-prone to program it. ** (For reference, I spent $ 5 $ to write this code, and I had a lot of trouble writing it on paper during the contest.)

def change(a, b, p):
    for c in range(K):
        for d in range(K):
            if (a + b) == (c + d) or (a - b) == (c - d) or (abs(a - c) + abs(b - d)) <= 3:
                if grid[c][d] == -1:
                    grid[c][d] = p + 1


K = 41
grid = [[-1] * K for _ in range(K)]
grid[K // 2][K // 2] = 0

for i in range(10):
    for a in range(K):
        for b in range(K):
            if grid[a][b] == i:
                change(a, b, i)

for row in grid:
    print(*row)

Then the output will look like this.

1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1
2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2
2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2
2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2
2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2
3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3
2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2
3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3
2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2
3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3
2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 0 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2
3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3
2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2
3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3
2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2
3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3
2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2
2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2
2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2
2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2
1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1

** Apparently, I feel like I can move it with a maximum of $ 3 $, so let's think about why this happens. ** **

Suppose you have a black and white chess board and you start with a black square. ** Move diagonally $ 2 $ You can move to any black square on the chess board by hand. However, it is not possible to move to a white square just by moving diagonally. If the goal is a white square, you can move it to the black square right next to the goal by $ 2 $, and then move it by $ 1 $. This way, you can move to any square on the chess board for less than $ 3 $. ** For this reason, $ 2 $ and $ 3 $ are arranged like a chess board. (Official commentary also has a figure)

Now that we know that we only need to think about $ 3 $ hands, let's consider the conditional expressions that determine how many hands we will have.

When you get 0 hands

You don't need to move only when the start and goal are in the same place. Kindly, he puts a $ 0 $ hand case in the sample.

If you get one

You can move $ 1 $ by hand, of course, if you can move by $ 1 $. (?) $ 1 $ The conditions for a place where you can move by hand are written in the problem statement, so if you meet any of the $ 3 $, you can move by $ 1 $.

a+b = c+d a-b = c-d |a-c| + |b-d| \le{3}

If you have two hands

Is difficult. First of all, I remember that "Super Ryoma" can move $ 2 $.

**-Diagonal movement ** **-Super Ryoma Move **

The $ 2 $ hand movement method is a combination of the $ 2 $ types of movement methods. There are the following $ 3 $ patterns for combination.

**-Super Ryoma move $ 2 $ times ** **-Diagonal movement $ 2 $ times ** **-Diagonal movement $ 1 $ times and Super Ryoma movement $ 1 $ times **

Super Ryoma move 2 hands

Super Ryoma Move $ 1 $ You can move $ 1 $ squares up / down / left / right $ 3 $ times per hand. In other words, you can move the Super Ryoma $ 2 $ by hand up / down / left / right $ 6 $ times.

** Simply put, if the "Manhattan Distance" is less than $ 6 $, you can move it by $ 2 $. Therefore, the condition is as follows. ** **

|a-c|+|b-d|\le{6}

Diagonal movement 2 hands

You can move anywhere with the "square of the same color as the starting point" in the example of the chess board. Let's think a little more in detail to put it into the formula.

Move diagonally $ 1 $ By hand, the coordinates change as follows:

-$ x $ Coordinates are $ + k $, $ y $ Coordinates are $ + k $ (upper right) -$ x $ Coordinates are $ + k $, $ y $ Coordinates are $ -k $ (bottom right) -$ x $ Coordinates are $ -k $, $ y $ Coordinates are $ + k $ (upper left) -$ x $ Coordinates are $ -k $, $ y $ Coordinates are $ -k $ (bottom left)

Therefore, the sum of the changes in the $ x $ and $ y $ coordinates is $ + 2k $, $ 0 $, or $ -2k $. ** Notice that the sum of the changes is always even. This means that no matter how many times you move diagonally, the sum of the changes will never stop at an odd number of squares. (This concept is called parity / evenness) **

On the other hand, if the sum of the changes is an even number, you can reach it by hand, no matter how far it is.

|a-c| + |b-d|Is an even number (the remainder after dividing by 2 is 0)

--Diagonal movement $ 1 $ Hand and super Ryoma movement $ 1 $ Hand

Diagonal movement $ 1 $ The squares that can be moved by hand are the squares of $ a + b = c + d $ or $ a-b = c-d $. When transposed, $ (a + b)-(c + d) = 0 $ and $ (a-b)-(c-d) = 0 $.

You can move from a square that meets this condition to a square with a Manhattan distance of $ 3 $ or less by hand.

|(a+b)-(c+d)|\le{3} |(a-b)-(c-d)|\le{3}

When you get 3 hands

$ 0 $ ~ $ 2 $ If you can't move it by hand, it's $ 3 $. There is no need to judge.

Implementation

Write all the conditional expressions. It is easier to divide the judgment part into functions and return the moment the conditions are met.

Please note that the correct answer will not be obtained unless the judgment is made in the order of $ 0 $ hand, $ 1 $ hand, $ 2 $ hand, $ 3 $ hand from the one with the least number of steps.

code

def solve():
    #0 hands. If you don't look at the sample properly, you'll forget this pattern.
    if a == c and b == d:
        return 0

    #It's one move. Write according to the problem statement.
    if a + b == c + d:
        return 1
    if a - b == c - d:
        return 1
    if abs(a - c) + abs(b - d) <= 3:
        return 1

    #Two hands. Write as considered.
    if abs(a - c) + abs(b - d) <= 6:
        return 2
    if (abs(a - c) + abs(b - d)) % 2 == 0:
    # %Since the priority of is high, add the left side()If you do not enclose it in, it will be WA (1 loss)
        return 2
    if abs((a + b) - (c + d)) <= 3:
        return 2
    if abs((a - b) - (c - d)) <= 3:
        return 2

    #If you can't do it with 2 moves, you must have 3 moves.
    return 3


a, b = map(int, input().split())
c, d = map(int, input().split())

print(solve())

Recommended Posts