ABC173 復習
A - Payment
少し考える必要があるか・・?
答えは必ず1000より小さい数になり、かつ支払いに使用できるのが1000の倍数円なので、1000の剰余を使用すれば良さそう。
回答は以下。
n = int(input()) if n % 1000 == 0: print(0) else: print(1000 - (n % 1000))
B - Judge Status Summary
この問題はディクショナリ(JavaなどではMapとも呼ばれます)を使うとすんなり解けます。
この問題に限らず、ある値がいくつかるか?を求めたい場合はディクショナリを使用すると簡潔な解法になることが多いように思えます。
今回の例では、pythonの標準モジュールであるdefaultdict
を使用すると良いでしょう。
from collections import defaultdict n = int(input()) ans = defaultdict(int) for i in range(n): ans[input()] += 1 print('AC x ' + str(ans['AC'])) print('WA x ' + str(ans['WA'])) print('TLE x ' + str(ans['TLE'])) print('RE x ' + str(ans['RE']))
C - H and V
一言で言うと、2重bit全探索です。
bit全探索については、こちらの記事でまとめましたが、今回の問題の場合、各行を選ぶ/選ばないと、各列をそれぞれ選ぶ/選ばないという選択肢を全て網羅できれば答えが定まりますので、bit全探索がうってつけです。
ただし、bit全探索を使う場合は制約に注意しましょう。今回はH,W共に最大でも6でしたので、計算量も十分耐えられます。
import copy H, W, K = map(int, input().split()) board = [list(input()) for i in range(H)] ans = 0 for i in range(2 ** H): row_colored_board = copy.deepcopy(board) for ii in range(H): if (i >> ii) & 1: row_colored_board[ii] = list('*' * W) for j in range(2 ** W): cnt = 0 col_colored_board = copy.deepcopy(row_colored_board) for jj in range(W): if (j >> jj) & 1: for k in range(H): col_colored_board[k][jj] = '*' for l in range(H): for m in range(W): if col_colored_board[l][m] == '#': cnt += 1 if cnt == K: ans += 1 print(ans)
D問題についてはまた後日・・。