プログラミング

[pythonでAtcoder] NOMURA プログラミングコンテスト 2020 解説

 

自分用の勉強記録もかねて、Atcoderの解説をしていきたいと思います。

今回は、ABC完答でした。A,Bは問題文の通りに実装すればよいかなというかんじでした。Cは少し悩みましたが、いろいろグラフを書いてたらきづきました。Dについては、かなり難しくて解答を読んでもまだ理解できていないので、分かっている所までメモ代わりに…

A~Dについて解説していきます。

僕もプログラミングについて絶賛学習中なので、間違えなどありましたら気軽にご連絡ください。

Contents
  1. A　Study Scheduling
  2. B　Postdocs
  3. C　Folia
  4. D　Urban Planning

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

Atcoder
RELATED POST