atCoder 173 Python (A~D)

総括

A,B,Dは解けましたがCは解法が分かったところで時間切れです。
初の4完達成ならず。

問題

A. Payment

回答

import math
N = int(input())

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

書くだけ。

B. Judge Status Summary

回答

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)

これも書くだけ。

C. H and V

回答

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)

制限時間内に解けず。
考え方はすぐにわかったのですが実装にしきれず時間切れ。
翌日落ち着いてやったら解けました。
forループが4重となってしまいやや汚いコードですが。

要はnumpyで'.'を0、 '#'を1に変換して0,1の行列にします。そして、行列のsum()がKになればcountを増やすという方針です。

赤に塗るのは結局、白に塗る(=行列要素を0にする)と同じなので、numpyのスライスで実現できそうです。

あとは、H x Wの行と列それぞれについて、赤に塗る(行列要素を0にする)か塗らないかの2択を全通り考えます。

塗るか塗らないかの二択なので0,1でフラグを立てます。これを生成するのがitertools.product`です。

まとめると

• まずは0,1のnumpy行列に変換
• 行と列それぞれでitertools.product`で塗る塗らないのフラグを立てる
• 塗る場合はnumpyスライスで0に変換
• 合計してKに等しい場合はcountを1増やす

で完了です。
時間内に解きたかった。

D. Chat in a Circle

回答

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:
    # 偶数の場合
    end = (N - 2) // 2
    answer = A[0] + (A[1:end+1] * 2).sum()
else:
    # 奇数の場合
    end = (N - 2) // 2
    answer = A[0] + (A[1:end+1] * 2).sum() + A[end+1]

print(answer)

Dの割には簡単でした。
具体例を5つくらい考えてみると法則性が見えてきます。

方針は

• 大きい順に訪れるのが最適
• この場合1番最初の数字は1回しか使われない
• 2番目以降の数字は2回使われるはず
• 2番目以降の数字が2回使われるということは、最後に使われる数字はだいたい(N - 2) / 2と予想できます
• 2で割るということは偶数と奇数で場合分けが必要です
• 偶数の場合は調整なし、奇数の場合は最後の数字だけ1回使います

これをコードに落としたのが回答です。