今回の学びは
・累積和は、下流への伝搬
・競プロではinput = sys.stdin.readline が10倍速い (その他のtipも)
今回は久しぶりの出場となりましたて
5分ほど遅刻してからの参加となりました。a, b問題の5分は致命的ではなかろうか
と思いつつも、解法が直ぐに思いついたので、問題が簡単だったのかな、で提出することにしました。そのままa, b, cはストレートに倒せました
しかしながらd問題でLTEとなりましたので、書き留めることにしました
解説動画をみると、これは基本だ！ということなので
是非とも今回でその基本を押さえておこう！という意気込みです
その基本とはズバリ
累積和
です
木じゃなくて配列で考えてみ！？
それをこの問題の場合は、木で考えるだけだす！
おぉ〜〜〜！
累積和
cumulative sum
累積和
覚えましょう
ちなみに最初のLTEの実装はこちらで、自己timespace analysisはO(n)です。いや違うな。なぜならO(n+n+q*n)こんな感じでO(q*n)としましょう。するとn, q もmaxが10**5とあるんで制限時間におさまりませんね。
最初の実装はこれ
class TreeNode:
def __init__(self):
self.val = 0
self.vertex = []
trees = []
def make_trees(n, A, B):
global trees
trees = []
for i in range(n):
trees.append(TreeNode())
for i in range(len(A)):
a = A[i]-1
b = B[i]-1
trees[a].vertex.append(b)
return trees
def dfs(node: TreeNode, x: int):
if node:
node.val += x
for i in node.vertex:
dfs(trees[i], x)
def sol(n, q, A, B, P, X):
make_trees(n, A, B)
for i in range(len(P)):
p = P[i]-1
x = X[i]
t = trees[p]
# dfs, give point x
dfs(t, x)
#
return " ".join([str(t.val) for t in trees])
#return n, q, A, B, P, X
do_submit = True
do_submit = False
def input_parse(input_str):
lines = [x.strip() for x in input_str.split("\n") if x.strip()]
parsed_lines = [list(map(str, line.split())) for line in lines]
print(parsed_lines)
n = int(parsed_lines[0][0])
q = int(parsed_lines[0][1])
A = []
B = []
P = []
X = []
for i in range(1, n-1+1):
a = int(parsed_lines[i][0])
b = int(parsed_lines[i][1])
A.append(a)
B.append(b)
for i in range(n, 1+n+q-1):
p = int(parsed_lines[i][0])
x = int(parsed_lines[i][1])
P.append(p)
X.append(x)
# S = parsed_lines[1][0]
# return n, k, S
return n, q, A, B, P, X
if not do_submit:
n, q, A, B, P, X = input_parse("""
4 3
1 2
2 3
2 4
2 10
1 100
3 1
""")
print(sol(n, q, A, B, P, X))
n, q, A, B, P, X = input_parse("""
6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10
""")
print(sol(n, q, A, B, P, X))
else:
# n = int(input().strip())
# q = int(input().strip())
n, q = list(map(int, input().split()))
A = []
B = []
P = []
X = []
for i in range(n-1):
a, b = list(map(int, input().split()))
# a = int(input().strip())
# b = int(input().strip())
A.append(a)
B.append(b)
for i in range(q):
p, x = list(map(int, input().split()))
# p = int(input().strip())
# x = int(input().strip())
P.append(p)
X.append(x)
print(sol(n, q, A, B, P, X))
これだと前述の通りO(n**2)でダメですね。
だから累積和ですね。賢い
この問題で累積和を使おうと思う判断ポイントはどこに持てたでしょうか？
頂点を根とする部分木に含まれるすべての頂点のカウンターの値に xをたす
これは 言い返せば
あるポイント（ノード）以降に値を足す
と言っています
動画でもあったように、配列で考えるととてもわかりやすいです。
配列 の三番目の要素以降すべてにxを足せ
抽象化すると
なんらかの一方方向性があるデータ構造、配列とか木（非サイクリック）で
特定のポイント以降になんらかの演算を繰り返す場合、それは先頭のポイントにだけ（つまりそこがリーダというか見本といいうか、それ以降のポイントも結局同じ演算が行われるわけだから、）に行えばいい。そして累積和とうテクニックで
先頭から下流へ値を伝搬していけば、
特定のポイント以降に同じ演算をするという行為の結果が得られます。
累積和は自分の言葉で言うと
下流への伝搬 と言えるでしょう
下流というのが方向性があることを意味しています、伝搬が累積という感じで持ち越して伝搬するという意味です
累積和というとパッとしない場合は下流への伝搬と訳しましょう
では変更点はこれだけです
@@ -31,7 +32,7 @@ def dfs(node: TreeNode, x: int):
if node:
node.val += x
for i in node.vertex:
- dfs(trees[i], x)
+ dfs(trees[i], node.val)
def sol(n, q, A, B, P, X):
@@ -41,7 +42,9 @@ def sol(n, q, A, B, P, X):
x = X[i]
t = trees[p]
# dfs, give point x
- dfs(t, x)
+ t.val += x
+ # accmulative run
+ dfs(trees[0], 0)
あれ
通らないです
二つの疑問が
１、atcoderでそもそも、エラーになったテストケースを自分で確認できないのか？
２、だいぶ自信があった提出だったが、なぜ通らなかったのか？
０、あと、これは全般に言えることでatcoderはいかに問題の入力をパースするかが時間節約の重要課題で、いつもこれに時間をめっちゃ使ってるし、手も脳みそも消費している気がするので、どうにかしたい。
１、atcoderでそもそも、エラーになったテストケースを自分で確認できないのか？
はい。https://atcoder.jp/posts/20
更新は早くないですが、一応ここにはあるみたいです。でも最新がないのであんまり意味なさげです。
探しましたが、結局そこにしかなさそうです。テストケースは公開してくれないようですね。これはleetcodeとは違い、さらに
これは、問題を解くのはむずかしい要素ですね。
２、だいぶ自信があった提出だったが、なぜ通らなかったのか？
はい。
いやー、一時間以上かけて他の解答もみて下のコード、特にrecurisve制限を引き上げるsysコード付け足してもダメだったぞ。。
import sys
sys.setrecursionlimit(1000000)
n, q = list(map(int, input().split()))
trees = [ [] for i in range(n) ]
for i in range(n-1):
a, b = list(map(int, input().split()))
trees[a-1].append(b-1)
trees[b-1].append(a-1)
values = [ 0 for i in range(n) ]
for i in range(q):
p, x = list(map(int, input().split()))
values[p-1] += x
#print(values)
def dfs2(i, parent):
for j in trees[i]:
if j == parent: continue
values[j] += values[i]
dfs2(j, i)
dfs2(0, -1)
print(*values)
ほぼもう、正解の解答例のこれとの差異はindexの取り方くらいだぞ。。。。
なぜかinput()がLTEの原因でした。以下のdiffのように、input = sys.stdin.readlineとするだけでLTEがなくなりました！
import sys -#input = sys.stdin.readline +input = sys.stdin.readline sys.setrecursionlimit(1000000)
なぜでしょうか。
この方はreadlineの方が10倍速いという実験結果が出たようです。いづれにせよreadlineと明示的に一行を読むと言った方が内部のc実装的にはやいのでしょう。
ということで
今回の大きな学びの一つとして競技プログラミングでは
input = sys.stdin.readline
を使いましょう
１０倍速いというのは、大げさではなく、私の場合input()の場合、何度やってもLTEでしたので、この違いは体感and 立証済みです。
はい、最後に
０、あと、これは全般に言えることでatcoderはいかに問題の入力をパースするかが時間節約の重要課題で、いつもこれに時間をめっちゃ使ってるし、手も脳みそも消費している気がするので、どうにかしたい。
ですが、やっぱりこれは、すクレーピングもいいけれど、パターンが決まって切るので定形文的に、覚えてしまうのが
一番速いんじゃないか、というのが自分の今の考えです。
最終的な実装は
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
trees = [ [] for i in range(n) ]
for i in range(n-1):
a, b = map(int, input().split())
trees[a-1].append(b-1)
trees[b-1].append(a-1)
values = [ 0 for i in range(n) ]
for i in range(q):
p, x = map(int, input().split())
values[p-1] += x
def dfs(i, parent):
for j in trees[i]:
if j == parent: continue
values[j] += values[i]
dfs(j, i)
dfs(0, -1)
print(*values)
で、驚いたことに、親を無視しても同じ結果だと頭で考える文には思うのですが、
通りませんでしょた。以下のコードです。trees[b-1].append(a-1)とする必要もないし、dfsで親を気にする必要もないというのが
私の考えですが、これは弾かれます。テストケースが公開されたら何故かみてみたいと思います。
と思ったら、動画をみかえして、どの親から来たかを覚えておく必要があるとうことは
親自身が辺に入っている入力があるとか、実は辺の指定は1 -> 2とういうながれではなく2 -> 1と表記できる
そうするとくるいそうじゃないでしょうか？
実際、答えが違ってくる入力を発見しました。こちらです。
この場合dfsしても上下関係がちょっとずれているので答えがちがってきます。ということで親を考慮するひつようがある
ということになります。
> python abc138d2.py ＃こっちが親考慮バージョン 3 2 2 1 3 1 1 2 2 6 2 8 2 > python abc138d2.py ＃こっちが親関係ないっしょバージョン 3 2 2 1 3 1 1 2 2 6 2 6 0
ということで最終実装は
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
trees = [ [] for i in range(n) ]
for i in range(n-1):
a, b = map(int, input().split())
trees[a-1].append(b-1)
values = [ 0 for i in range(n) ]
for i in range(q):
p, x = map(int, input().split())
values[p-1] += x
def dfs(i):
for j in trees[i]:
values[j] += values[i]
dfs(j)
dfs(0)
print(*values)
以上です