atCoder 173 Python

Summary

A, B, D have been solved, but C has timed out when the solution is known. The first 4 completes have not been achieved.

problem

https://atcoder.jp/contests/abc173/tasks/abc173_a

A. Payment

Answer

import math
N = int(input())

m = math.ceil(N / 1000)
answer = m * 1000 - N
print(answer)

Just write.

B. Judge Status Summary

Answer

results = {'AC': 0, 'WA': 0, 'TLE': 0, 'RE': 0}
N = int(input())
for _ in range(N):
    result = input()
    results[result] += 1

for k, v in results.items():
    print(k, 'x', v)

Just write this too.

C. H and V

Answer

import itertools
import numpy as np

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

temp = []
for _ in range(H):
    C = list(input())
    A = [c.replace('.', '0') for c in C]
    A = [a.replace('#', '1') for a in A]
    A = list(map(lambda x: int(x), A))
    temp.append(A)

C = np.array(temp)

count = 0
l = [0, 1]
wide = itertools.product(l, repeat=W)
for w in wide:
    hight = itertools.product(l, repeat=H)
    for h in hight:
        copy_C = C.copy()
        for num, i in enumerate(w):
            if i == 1:
                copy_C[:, num-1] = 0
            for num2, j in enumerate(h):
                if j == 1:
                    copy_C[num2-1, :] = 0
        if copy_C.sum() == K:
            count += 1

print(count)

I couldn't solve it within the time limit. I quickly understood the idea, but I couldn't finish the implementation and the time was up. The next day I calmed down and it was solved. It's a little dirty code because the for loop is quadrupled.

In short, use numpy to convert '.' `` to 0``` and ```'#' to` `1``` Make it a matrix of 0,1. And if the matrix sum ()`` becomes ``K, the policy is to increase `` `count.

After all, painting in red is the same as painting in white (= setting the matrix element to 0), so it seems that it can be realized with a slice of numpy.

After that, for each row and column of H x W, consider two choices, paint in red (set the matrix element to 0) or not.

Since there is a choice between painting and not painting, set a flag with `` `0,1. It is itertools.product```` that generates this.

Summary

--First, convert to a numpy matrix of 0,1 --Flag ```itertools.product```` to paint and not paint in each row and column --When painting, convert to 0 with numpy slice --Increase count by 1 if total is equal to K

It is completed with. I wanted to solve it in time.

D. Chat in a Circle

Answer

import numpy as np

N = int(input())
A = list(map(int, input().split()))

A = sorted(A, reverse=True)
A = np.array(A)

if N % 2 == 0:
    #If even
    end = (N - 2) // 2
    answer = A[0] + (A[1:end+1] * 2).sum()
else:
    #If odd
    end = (N - 2) // 2
    answer = A[0] + (A[1:end+1] * 2).sum() + A[end+1]

print(answer)

It was easy for D. If you think about five concrete examples, you can see the law.

The policy is

――It is best to visit in descending order --In this case, the first number is used only once --The second and subsequent numbers should be used twice ――The fact that the second and subsequent numbers are used twice means that the last number used can be expected to be approximately `` `(N --2) / 2```. —— Dividing by 2 requires even and odd numbers. --No adjustment for even numbers, use only the last number once for odd numbers

The answer is to put this in the code.