ABC173に参加しました
Qiitaで記事を書く練習がてら考えたことなど書いていきます。著者の色は緑です。
ABC173A - Payment
まさかの1WA。
print(1000 - (N%1000)) だけではNが1000の倍数のとき出力が1000になってしまう。
ifで場合分けするかもう一回1000の剰余を取れば解決。A問題とはいえちょっと気を抜きすぎた。
開始2分でAC。
N = int(input())
if N%1000:
print(1000 - (N % 1000))
else:
print(0)
Nの上限が10000なので10000円札で払って小銭だけ見るのでもよい。
N = int(input())
print((10000 - N) % 1000)
ABC173B - Judge Status Summary
辞書作ってD.items()からループを回してカウント増やしていって出力。
変数入りの文字列出力なので変数部分を{ }で指示しておいて後ろからformatで代入する。
開始5分でAC。
N = int(input())
D = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
for i in range(N):
D[input()] += 1
for x, y in D.items():
print("{0} x {1}".format(x, y))
ABC173C - H and V
考えたこと
-
H, Wがそれぞれ6以下と小さいので全探索で行けそう。
-
塗りつぶす行と列のあり得る組み合わせを愚直に全部確かめ、各々のケースで全マスを確認して黒いところを数える。$O(2^{H+W} * HW)$で間に合う。
-
「塗りつぶす行と列」の組み合わせと「塗りつぶさない行と列」の組み合わせは完全に裏表の関係なので、ダイレクトに塗りつぶさないところを考えられる。
-
組み合わせの全列挙なのでbit全探索。桁数はH+Wにすれば1つの数字(case)に関してループを回すだけで状態を列挙できる。（2進法の下からH桁が行、残りW桁が列に関するフラグとして扱える）
-
各caseにおいて全マス確認して"#"ならカウントし、Kと等しいものをカウントする。
def main():
H, W, K = map(int, input().split())
grid = [input() for _ in range(H)]
n = H + W
ans = 0
for case in range(2**n):
cnt = 0
for i in range(H):
for j in range(W):
if (case >> i) & 1:
if (case >> j + H) & 1:
if grid[i][j] == "#":
cnt += 1
if cnt == K:
ans += 1
print(ans)
itertoolsのcombinationやらproductやらに目移りしてしまって時間がかかってしまった。
開始30分でAC。
ちなみに
itertools.product(range(2), repeat=H)
のようにすれば [0,0,...0] から [1,1,...1] までの$2^H$通りを列挙できるらしい。直積ってこう使うのね。
ABC173D - Chat in a Circle
考えたこと
- 既に輪になっている人数と同じ数に円周が分割され、各円弧が「そこに新しく人が入ったときに加算される心地よさ＝円弧の端点の小さいほう」を保持していると見ることができる。
- 先に小さい人が入ると最小値が下がってしまうので$A_i$を降順にソートして順番に輪に入れていく。
- ある円弧に新たに人が入るとそこに保持されていた値は消滅し、新たに入った値の円弧が2本増える。
- 今ある円弧の値の最大値をどんどこ貪欲で取ってきたいのでheapqが使えそう？
import heapq
def main():
N = int(input())
A = list(map(int, input().split()))
A = [a * (-1) for a in A] # Cに突っ込んで最大値を取りたいので先に負にしている
A.sort()
C = []
heapq.heapify(C)
ans = 0
for i, a in enumerate(A):
if i == 0:
heapq.heappush(C, a)
continue
ans -= heapq.heappop(C) # 最大値を取り出して答えに加算
heapq.heappush(C, a) # 入れた人の値を持つ領域が2個増える
heapq.heappush(C, a)
print(ans)
貪欲でいけそうと分かればheapqをいい感じに使うだけでなんとかなった。
（追記）そもそもソート済みで上から取って下につけてくだけなのでheapqである必要もなかった。大きい順に$A_1 + A_2 + A_2 + A_3 + A_3 +$...と$N-1$項ぶん足せばよい。
開始42分でAC。
Eはごちゃごちゃと書いてみたけどなんだか複雑な場合分けをしてしまいWA。
安定して5完できるくらいを目指したい。