ABC036 - popleの日記

問題元　→　

abc036.contest.atcoder.jp

A - お茶

概要

1箱にA本の商品が入っている．B本手に入れるには何箱買えば良いか出力しろ．

解法

剰余が0でなければ+1すれば良い．

A, B = list(map(int, input().split()))
print(B // A + min(1, B % A))

B - 回転

概要

N * Nの文字列を時計回りに90度回転させて出力しろ．

解法

zipとunpackingを使うことで行列を転置させることができる．これを列について反転させる（？）ことで求める「時計回りに90度」となる．

回転を考慮した重複の除去を行う時なんかに使う．

N = int(input())
S = [input() for _ in range(N)]
print(*["".join(s[::-1]) for s in zip(*S)], sep="\n")

C - 座圧

概要

1次元の配列に対して座標圧縮を行い，圧縮後の配列の値を出力しろ．

解法

正しくマッピングすれば，大小関係も守られる．

リーダブルコードだかに似た問題があった気がする．（圧縮じゃなくてuniqueだけだったかも？）方法は色々あると思うけど，自分としてはこのコードがベストかなぁ？

N = int(input())
a = [int(input()) for i in range(N)]
dic = dict(zip(sorted(set(a)), range(N)))
print(*list(map(lambda x: dic[x], a)), sep="\n")

D - 塗り絵

概要

N個のノードがあり，N-1個の辺があり連結である．ノードは黒色か白色で塗ることができる．ただし，辺の両端がどちらも黒色であってはならない．何通りの塗り方があるか出力しろ．

解法

要するに木．解は膨大なものになり愚直な方法では間に合わない．

こういった問題は動的計画法が有効な場合が多い．という訳で，DAGを構成するために逆算していく．

あるノードを新たにくっつけた時に答えがどう変化するかを考える．単純に2倍になるだろうか？もちろんそうはいかない．くっ付ける先のノード（隣接するノード）全てが必ず白色となる場合を除き，いずれかが黒色である場合を考慮しなければならない．逆に言えば隣接するノード以降は考えなくても良いし，この二つの状況だけを考えれば良い．

答えのために持つべき情報も，DAGも見えた．あとはコードに落とすだけ．

解説を見ると，この手のDPを木DPというらしい．「tree dp tutorial」でググったら良さげなサイトが見つかった

codeforces.com

そのうち やる．

MOD = 10 ** 9 + 7
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
q = [0]
top = 0
visited = [False] * N
visited[0] = True
while top < len(q):
    node = q[top]
    top += 1
    for n in edges[node]:
        if visited[n]:
            continue
        visited[n] = True
        q.append(n)
white = [1] * N
both = [1] * N  
for node in reversed(q):    
    both[node] = (both[node] + white[node]) % MOD
    for par in edges[node]:
        white[par] = (white[par] * both[node]) % MOD
        both[par] = (both[par] * white[node]) % MOD
print(both[0])