アルゴリズム忘備録

競技プログラミングとかデータ分析とか

2019-01-28から1日間の記事一覧

NIKKEI Programming Contest 2019 D - Restore the Tree

atcoder.jp トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。 問題文で追加されているという辺は必ず子へのショートカットとな…

NIKKEI Programming Contest 2019 E - Weights on Vertices and Edges

atcoder.jp 日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。 「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここま…