Ruby と Python で解く AtCoder ABC138 D 隣接リスト

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Ki
Difficulty: 923

今回のテーマ、隣接リスト

以前解きました Ruby と Python と networkx で解く AtCoder ABC168 D 隣接リスト の応用版といった問題です。

今回は、木の根から頂点へカウンターの値が送られますますので、カウンター用の配列を準備し、根から頂点へ探索を行うことによりカウンターの値の受け渡しを行います。

Ruby

ruby.rb

n, q = gets.split.map(&:to_i)
a = Array.new(n){[]}
n.pred.times do
    x, y = gets.split.map(&:to_i)
    a[x - 1] << y - 1
    a[y - 1] << x - 1
end
p = Array.new(n){0}
q.times do |i|
  x, y = gets.split.map(&:to_i)
  p[x - 1] += y
end
c = Array.new(n){0}
c[0] = 1
que = []
que << 0
while que.size > 0
  e = que.shift
  a[e].each do |i|
    next if c[i] > 0
    c[i] = 1
    p[i] += p[e]
    que << i
  end
end
puts p

index.rb

    p[i] += p[e]

ここでカウンターの値の受け渡しを行っています。

Python

python.py

from sys import stdin

def main():
    from collections import deque
    input = stdin.readline
    n, q = map(int, input().split())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = map(int, input().split())
        a[x - 1].append(y - 1)
        a[y - 1].append(x - 1)
    p = [0] * n
    for i in range(q):
        x, y = map(int, input().split())
        p[x - 1] += y
    c = [0] * n
    c[0] = 1
    que = deque([])
    que.append(0)
    while len(que) > 0:
        e = que.popleft()
        for i in a[e]:
            if c[i] > 0:
                continue
            c[i] = 1
            p[i] += p[e]
            que.append(i)
    for i in range(n):
        print(p[i])
main()

stdin.py

from sys import stdin
    input = stdin.readline

stdinを使用すると実行時間がかなり速くなります。

	Ruby	Python	Python (stdin)	PyPy	PyPy (stdin)
コード長 (Byte)	442	681	736	681	736
実行時間 (ms)	802	1734	1044	1959	864
メモリ (KB)	25468	53008	53040	105164	91852

まとめ

• ABC 138 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった