AtCoderBeginnerContest173 Review & Summary (First Half)

AtCoder ABC173 This is a summary of the problems of AtCoder Beginner Contest 173, which was held on 2020-07-05 (Sun), in order from problem A, taking into consideration the consideration. 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

Problem A Payment

Problem statement Buy a $ N $ yen item at the store. How much does it cost to change when paying using only $ 1000 $ yen bills? However, payment shall be made with the minimum required number of $ 1000 $ Yen bills.

I thought that I could calculate the change by using the last three digits of the $ N $ yen, so I calculated the remainder by dividing $ N $ by $ 1000 $. You can get the output you want by subtracting the remainder from $ 1000 $, but in the case of $ 1000 x x $ yen, the change is originally $ 0 $ yen, but the remainder is $ 0 $, so the output becomes "1000". Because it ends up, I made a conditional branch with the if statement. In the solution of the consideration, I thought that the method of calculation without conditional branching was written.

abc173a.py


n = int(input())
k = n % 1000
if k == 0:
    print(0)
else:
    print(1000 - k)

Problem B Judge Status Summary

Problem statement Mr. Takahashi participated in the programming contest AXC002 and submitted the code to question A. There are $ N $ test cases for this issue. For each test case $ i (1 \ leq i \ leq N) $, the string $ S_i $ representing the judge result is given, so the judge result is "AC", "WA", "TLE", "RE". Please find the number of those that were. For the output format, refer to the output column.

I honestly put the input into the dict.

abc173b.py


n = int(input())
key_dict = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
for i in range(n):
    key = input()
    key_dict[key] += 1
print("AC x " + str(key_dict["AC"]))
print("WA x " + str(key_dict["WA"]))
print("TLE x " + str(key_dict["TLE"]))
print("RE x " + str(key_dict["RE"]))

I want to be able to write like the python code in the official commentary.

abc173b.py


N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
    print('{0} x {1}'.format(v, s.count(v)))

C problem H and V

Problem statement There is a cell consisting of cells in the $ H $ row and $ W $ column. The color of the cell of $ i $ line from the top and $ j $ column from the left $ (1 \ leq i \ leq H, 1 \ leq j \ leq W) $ is given as the character $ c_ {i, j} $. When $ c_ {i, j} $ is ".", It is white, and when it is "#", it is black. Consider doing the following: -Select some rows (may be $ 0 $ rows) and some columns (may be $ 0 $ columns). Then, paint all the cells in the selected row and the cells in the selected column in red. A positive integer $ K $ is given. How many rows and columns can be selected so that just $ K $ of black cells remain after the operation? Here, the two choices are considered different when there are rows or columns that are chosen only in one.

I thought I had to do a full search, so I solved it using a recursive function, but it took a long time to implement.

abc173c.py


import numpy as np
def funk(matrix, n, k, no_list, h, w):
    if n == 0:
        mask = np.ones((h, w))
        for i in range(h):
            if no_list[i] == 1:
                mask[i,] = 0
        for j in range(w):
            if no_list[h+j] == 1:
                mask[:,j] = 0
        if np.sum(matrix * mask) == k:
            return 1
        else:
            return 0
    ans = 0
    ans += funk(matrix, n - 1, k, no_list + [1], h, w)
    ans += funk(matrix, n - 1, k, no_list + [0], h, w)
    return ans

ans = 0
h, w, k = map(int, input().split())
n = h + w
matrix = np.zeros((h, w))
for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == "#":
            matrix[i,j] = 1
        else:
            matrix[i,j] = 0
no_list = []
ans += funk(matrix, n, k, no_list, h, w)
print(ans)

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 DEF problem. Continued in the second half.

Recommended Posts

AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest173 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)
AtCoderBeginnerContest168 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)