自分用の勉強記録もかねて、Atcoderの解説をしていきたいと思います。
今回は、ABC完答でした。A,Bは問題文の通りに実装すればよいかなというかんじでした。Cは少し悩みましたが、いろいろグラフを書いてたらきづきました。Dについては、かなり難しくて解答を読んでもまだ理解できていないので、分かっている所までメモ代わりに…
A~Dについて解説していきます。
僕もプログラミングについて絶賛学習中なので、間違えなどありましたら気軽にご連絡ください。
A Study Scheduling
問題はこちら。
h1,m1,h2,m2,k = map(int,input().split())
time = (h2*60 + m2) - (h1*60 + m1) -k
print(time)題意の通りに書いていけばできる！
B Postdocs
問題はこちら。
t = input()
print(t.replace('?','D'))結局全部Dに置き換えればいいというよくわからん問題。
C Folia
問題はこちら。
n = int(input())
A = list(map(int,input().split()))
H = [0]*(n+1)
s = sum(A)
flag= True
if n==0:
if A[0] ==1:
print(1)
else:
print(-1)
else:
if A[0]>= 1:
print(-1)
flag = False
else:
H[0] =1
i = 1
while i <=n:
if A[i] > H[i-1]*2:
print(-1)
flag =False
break
else:
if s >=2*(H[i-1]-A[i-1]):
H[i] = 2*(H[i-1]-A[i-1])
else:
H[i] = s
s -= A[i]
i +=1
if flag:
print(sum(H))いろいろグラフを書いていると、二つの制限があることを満たしながらグラフの根から作っていけばいいとわかる。
制限①2分木なので、深さが1増えると頂点は2倍以下。
制限②根付き木の葉の数が決まっているので、枝を分けすぎてはいけない。
※コードのハイライトした部分が制限である。
D Urban Planning
問題はこちら。
解説を読んでもわかりそうでわからない…
とりあえずわかっている所をメモとして…
①連結成分ごとにわける →Union-Find（素集合データ構造）つかう
②閉路があると、道を1本減らせる
…
※dp = 動的計画法
参考：
・公式PDF、Youtube
・http://umineko-sephi.hatenablog.com/entry/2020/05/31/123000
・https://atcoder.jp/contests/nomura2020/submissions/13746238
コメント