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

スポンサーリンク

自分用の勉強記録もかねて、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

コメント

タイトルとURLをコピーしました