AtCoderBeginnerContest178 Review & Summary (first half)

AtCoder ABC178 This is a summary of the AtCoder Beginner Contest 178 problems that took place on 2020-09-13 (Sun), starting with problem A and taking into account the considerations. The first half deals with problems up to ABC. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

A problem Not

Problem statement An integer $ x $ between $ 0 $ and $ 1 $ is given. Output $ 1 $ if $ x $ is $ 0 $, and output $ 0 $ if $ 1 $.

When I submitted it, I was afraid that there were multiple test cases, but it was'AC'. Is case02 ~ 09 also necessary?

abc178a.py


x = int(input())
print(1 - x)

Problem B Product Max

Problem statement Given the integers $ a, b, c, d $. What is the maximum value of $ x × y $ for integers $ x, y $ that satisfy $ a \ leq x \ leq b, c \ leq y \ leq d $?

If $ x and y $ can only have different codes, the maximum value is $ a × d $ or $ c × b $. If $ x and y $ have the same sign, the maximum value is $ a × c $ or $ b × d $.

abc178b.py


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

C problem Ubiquity

Problem statement How many integer sequences $ A_1, A_2,…, A_N $ of length $ N $ meet all of the following conditions? ・ $ 0 \ leq A_i \ leq 9 $ ・ There is $ i $ such that $ A_i = 0 $. ・ There is $ i $ such that $ A_i = 9 $. However, the answer can be very large, so print the remainder divided by $ 10 ^ 9 + 7 $.

It was a problem of the number A of the first grade of high school. Let $ B $ be the set of arrays with $ i $ such as $ A_i = 0 $, and $ C $ be the set of arrays with $ i $ such as $ A_i = 9 $.

\begin{align}
n(B \cap C) = n(B) + n(C) - n(B \cup C)
\end{align}

However, it is difficult to calculate as it is, so if you transform the formula,

\begin{align}
n(B \cap C) &= n(B) + n(C) - n(B \cup C) \\
&= n(U) - (n(\overline{B}) + n(\overline{C}) - n(\overline{B \cup C})) \\
&= n(U) - n(\overline{B}) - n(\overline{C}) + n(\overline{B} \cap \overline{C}) \\
\end{align}

Therefore, the calculation can be done easily. n(U) = 10^N n(\overline{B}) = 9^N n(\overline{C}) = 9^N n(\overline{B} \cap \overline{C}) = 8^N

abc178c.py


n = int(input())
mod = 10**9 + 7
print((10**n - 9**n + 8**n - 9**n) % mod)

This is the end of the first half. Recently, the official commentary has been described very carefully, so I hope you can refer to that for the detailed solution. Thank you for reading to the end of the first half.

The second half will explain the DE problem. Continued in the second half.

Recommended Posts

AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half
AtCoder Review of past questions (first half of 12 / 8,9)