Блог пользователя sguu

Автор sguu, история, 8 лет назад, По-английски

Someone Please Explain D,E solution(English)?It's in Japanese

https://atcoder.jp/contests/aising2019

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится

My solution for D: It can be observed that the whole game consists of two phases: In the first phase Takahashi will take the greatest numbers, which Aoki will take some numbers around x. In the second phase the two will alternately take the greatest number. One should binary search on the position such where the transition between two phases happen. To check it one may need another binary search to count the numbers taken. After that the sum can be computed in O(1) if precalculated the partial sums and partial sum on even indices. The solution takes time.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

My solution for E: Let dpv, j, 0 denote the minimum sum of Ai in the connected component of v if we cut j edges in the subtree of v, and the connected component of v only consists of batteries. And dpv, j, 1 denote pretty much the same thing, but allows the connected component of v consists of computers. The DP should be calculated in an ordinary manner, which may seem to have a complexity of O(N3), but is actually O(N2). There are many proofs given on this kind of problems, e.g., Barricades in Algorithmic Engagements 2007, which can be found in the book looking for a challenge