AtCoderBeginnerContest173復習＆まとめ（前半）

AtCoder ABC173

2020-07-05(日)に行われたAtCoderBeginnerContest173の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　Payment

問題文
お店で$N$円の商品を買います。
$1000$円札のみを使って支払いを行う時、お釣りはいくらになりますか？
ただし、必要最小限の枚数の$1000$円札で支払いを行うものとします。

$N$円の下三桁を使うことでお釣りの計算ができると思ったので，$N$を$1000$で割った余りを計算しました．
余りを$1000$から引き算すれば出したい出力を得ることができますが，$1000 × x$円の場合，本来お釣りが$0$円ですが余りが$0$となるため出力が"1000"になってしまうので，自分はif文で条件分岐しました．
考察の解法では，条件分岐しないで計算する方法が書いてあってなるほどなと思いました．

abc173a.py

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

B問題　Judge Status Summary

問題文
高橋君は、プログラミングコンテスト AXC002 に参加しており、問題 A にコードを提出しました。
この問題には$N$個のテストケースがあります。
各テストケース$i(1 \leq i \leq N)$について、ジャッジ結果を表す文字列$S_i$が与えられるので、ジャッジ結果が"AC", "WA", "TLE", "RE"であったものの個数をそれぞれ求めてください。
出力形式は、出力欄を参照してください。

愚直に入力を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"]))

公式の解説のpythonのコードみたいに書けるようになりたいです．

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問題　H and V

問題文
$H$行$W$列に並ぶマスからなるマス目があります。上から$i$行目、左から$j$列目$(1 \leq i \leq H,1 \leq j \leq W)$のマスの色は文字$c_{i,j}$として与えられ、$c_{i,j}$が"."のとき白、"#"のとき黒です。
次の操作を行うことを考えます。
　・行を何行か選び($0$行でもよい)、列を何列か選ぶ($0$列でもよい)。そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。
正の整数$K$が与えられます。操作後に黒いマスがちょうど$K$個残るような行と列の選び方は何通りでしょうか。ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

全探索するしかと思い，再帰関数使って解きましたが，実装に時間がかかってしまいました．

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)

前半はここまでとなります．
最近は公式の解説がとても丁寧に記述してあったので，詳しい解法はそちらを参考にしてもらえたらと思います．
前半の最後まで読んでいただきありがとうございました．

後半はDEF問題の解説となります．
後半に続く．