読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #338 (Div. 2) B - Longtail Hedgehog

過去問再挑戦キャンペーン実施中。

問題

1からnまでの番号がつけられた点とm個の辺からなるグラフがある。重複辺・自己辺はない。

このグラフのいくつかの辺に色を塗ることでハリネズミを作る。ハリネズミは「尾」と「背骨」からなる。これらは以下のように定義される。

尾: 点の番号が単調増加となるような路

背骨: 尾の終点(尾に含まれ、番号が最も大きい点)に接続する辺

また、ハリネズミの「美しさ」は以下で定義される。

(美しさ) = (尾の長さ) * (背骨の本数)

ただし「尾の長さ」とは、尾に含まれる点の個数である。

与えられたグラフからハリネズミを作るとき、可能な最大の美しさを答えよ。

(※)上の定義によればある辺は尾の一部かつ背骨となることがあるが、これは許される。

制約

2 <= n <= 100000

1 <= m <= 200000

解法

求めるのは最大の美しさ、すなわち

max( (尾の長さ) * (背骨の本数) )

である。

背骨の本数は尾の終端eのみによって決まる。そこでeを固定して考えると、以下が成り立つ。

(尾の終端がeのときの最大の美しさ)

= (eを終端とする尾の最大の長さ) * (eに接続する辺の数)

つまり、各e(1<=e<=n)に対して、「終端をeとする尾の最大の長さ」と「eに接続する辺の数」がわかればよい。

後者は簡単に求まる。問題は前者だが、これは動的計画法を用いて計算する。

dp[i] = iを終端とする尾の最大の長さ

とすると、各dp[i]は以下の操作により求まる。

  1. 初期化: dp[i] = 1 for i =1..N
  2. dp[v] = max(dp[v], dp[u] + 1) (u < v, uはvに接続している)

このdpテーブルを作った後、各点iについてdp[i]*(iに接続する辺の本数)を計算し最大値を取ればよい。

from collections import defaultdict as ddict

n, m = map(int, input().split())
graph = ddict(set)
for i in range(m):
    u, v = map(int, input().split())
    graph[u].add(v)
    graph[v].add(u)
    
#max length of tail end at i=1..N (dp[0] is nonsense)
dp = [1] * (n + 1)

for u in graph:
    for v in graph[u]:
        if v > u:
            dp[v] = max(dp[u] + 1, dp[v])

mx = 0
for u in graph:
    mx = max(mx, dp[u] * len(graph[u]))

print(mx)

1ヶ月前本番で見たときは問題の意味すら分からなかったけど、今回は公式の解説を見ただけで実装できたので成長を感じる。