2019-01-28から1日間の記事一覧
atcoder.jp トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。 問題文で追加されているという辺は必ず子へのショートカットとな…
atcoder.jp 日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。 「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここま…