AtCoder ABC128
概要
AtCoderの記録です。全部Pythonで頑張ります。
E,Fは解いてないです。
この記事の対象
本編
AtCoderとは
競技プログラミングコンテストを開催している会社です。 atcoder.jp
ABC128
今回は用事でコンテストに参加できない予定だったのですが、欲を出して参加した結果、大火傷をした回でした。前回上がった分が丸々なくなりました。悲しい。
解いていきます。
A Apple Pie
はい。
A,P = map(int,input().split()) print((A*3+P)//2)
B Guidebook
pythonは普通に.sort()を使えばいいです。S,P共に昇順ソートにするためPは-1をかけてリストに追加しました。
レストラン番号を出力すれば良いので、特に影響はありません。
N = int(input()) SP = [] for i in range(N): s,p = map(str,input().split()) SP.append([s,-int(p),i]) SP.sort() for i in range(N): print(SP[i][2]+1)
C Switches
設定がある程度複雑でしたが、Nが小さいので全探索でいけます。2進数を利用しました。
N,M = map(int,input().split()) s = [0 for i in range(N)] s_list = [] for i in range(M): x_in = list(map(int,input().split())) s = x_in[1:] s_list.append(s) p = list(map(int,input().split())) ok = 0 for i in range(2**N): s = format(i,'010b') s = s[-N:] s = [int(s[i]) for i in range(len(s))] for j in range(M): l = s_list[j] cnt = 0 for ll in l: if s[ll-1] == 1: cnt += 1 if cnt % 2 != p[j]: break if j == M-1: ok += 1 print(ok)
D equeue
取り出して戻してまた取り出して、とややこしい操作に思えますが、取り出したあとまとめて戻すという風に操作を並び替えても同じということに気づけばシンプルな問題になります。
ということで、戻す数を最大j個、取り出す数をK-j個として二重ループを回しました。取り出し方は左からi個、右からK-j-i個取ってくるようにしました。
ちなみにKの制約を1<=K<=Nだと勘違いしていて時間を溶かしました。
N,K = map(int,input().split()) V = list(map(int,input().split())) value = max_value = 0 for j in range(K//2+1): for i in range(K-j+1): if K-j >= N: value = V else: if i == K-j: value = V[:K-j] else: value = V[:i]+V[-(K-j-i):] value.sort() # print(i,j,value) jj = min(len(value)-1,j) if value[jj] <= 0: s = sum(value[jj:]) else: s = sum([i for i in value if i>0]) if s > max_value: max_value = s print(max_value)
まとめ
コンテスト開始時間に用事が間に合わないことがわかっていたので不参加の予定だったのですが、Dが解けそうな気がしたので出来心で参加してしまい、結果大火傷でした…。
いやー、茶色コーダーからグレーコーダーに戻ったことがある人間なんて僕ぐらいじゃないですかね。悲しい経験をしてしまいました。
次頑張ります。