PAST4M
from 第四回 アルゴリズム実技検定
考えたこと
実際に塗るのではなく、最も新しい影響するクエリを見つける問題？
クエリは10^5、頂点は10^5
どうやって見つけるのか
公式解説
改めて考えたこと
塗りの情報をどうやって保持するか？
各頂点ごとに色を持つのでいいか
1回のクエリで塗られる個数は、高さが平均logNだから対数オーダーだが、当然偏った木で最悪線形オーダーにするテストケースがあるだろう
時間軸を反転することで、一度塗ったところを再度塗らないでスキップしたい
それができるためには？
塗りの下端の頂点が「既に塗られてる上端」を持てば良い
なっている最中に「既に塗られている頂点」に出逢ったら、塗られてる上端を取得する
塗られてる上端が、今塗ろうとしてる範囲の上端より上なら、そこで終了
下なら塗られてる上端の親から塗りを再開
塗られてる上端を持つのは下端だけではダメ
次のクエリが塗られてる範囲の途中から始まるかもしれないから
上端はどうやってわかる？
塗ろうとしてる上端を見て、それが塗られてるならその上端を得れば良い
自然言語ではこんな感じでできそうな雰囲気だから、後はコードできちんと示す
実装
頂点だと勘違いしてたけど辺だな
与えられた辺の順序で答えるべきところを、頂点の順序で答えていた
AC:
pythondef solve(N, Q, edges, QS, ordered_edges):
from collections import defaultdict
color = [0] * N
uplink = [None] * N
root = 0
# graph to tree
children, parents = graph_to_tree(N, edges, root)
# ready lca
construct(N, children, root, parents)
def paint(start, end, c):
cur = start
while cur != end:
if color[cur] == 0:
color[cur] = c
uplink[cur] = end
cur = parents[cur]
else:
if query(uplink[cur], end) != end:
# uplink if avobe end
return
cur = uplink[cur]
for a, b, c in reversed(QS):
a -= 1
b -= 1
lca = query(a, b)
paint(a, lca, c)
paint(b, lca, c)
for frm, to in ordered_edges:
if parents[frm] == to:
print(color[frm])
else:
print(color[to])頂点と辺の取り違え関連でこういうミスをしていた
uplinkで「過去に塗られた時のend」までジャンプした後、さらにparentに進んでる
頂点ぬりなら正しいのだが、辺ぬりなので正しくない
pythondef paint(start, end, c):
cur = start
while cur != end:
if color[cur] == 0:
color[cur] = c
uplink[cur] = end
else:
if query(uplink[cur], end) != end:
# uplink if avobe end
return
cur = uplink[cur]
if cur == end: return
cur = parents[cur]Related Pages
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152_f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]