H - Cramming 解説
by
Lulusphere
Suppose we study \(K\) topics in some order.
When studying one topic, the time is reduced by \(B\) for each adjacent topic that has already been studied. Each such reduction corresponds to an edge between two studied vertices.
Since the topics form a tree, among any \(K\) selected vertices, there are at most \(K-1\) edges. Therefore, throughout the whole process, the total number of reductions is at most \(K-1\).
If \(A>B\), the total required time is at least
\[ KA-B(K-1)=A+(K-1)(A-B). \]
Also, every topic takes at least \(1\) unit of time. Combining these bounds, the minimum time for studying \(K\) topics is at least
\[ A+(K-1)\max(1,A-B). \]
This lower bound is achievable.
Choose an arbitrary vertex as the root, and list the vertices in BFS or DFS order. Then every vertex except the first one appears after its parent.
Therefore, the first topic takes \(A\) time, and every later topic can be studied in
\[ \max(1,A-B) \]
time, because its parent has already been studied.
Let
\[ C=\max(1,A-B). \]
If \(T<A\), then we cannot study any topic.
Otherwise, after studying the first topic, the remaining time is \(T-A\). Hence, the maximum number of topics we can study is
\[ K= 1+\min\left(N-1,\left\lfloor\frac{T-A}{C}\right\rfloor\right). \]
The minimum time required to study these \(K\) topics is
\[ M=A+(K-1)C. \]
To construct an actual order, output the first \(K\) vertices of any BFS or DFS order from an arbitrary root.
The time complexity is \({\cal O}(N)\).
投稿日時:
最終更新:
