AGC049

AtCoder Grand Contest 049 - AtCoder

Rate is +10 with 1 question AC in B. Keep the light blue for now.

A

• Thoughts.
  • having not the slightest idea
  • N=100 in a directed graph
  • Question for expected value. Expected value DP?
  • When everything is in pieces, you can have 2^100 different states.
  • Find and sum for each independent component?
• Official Explanation
  • 
  • The “number of operations” is the number of times this table is added horizontally - The number of times is the sum
  • add vertically instead of horizontally - Sum of f(x,y) per x is sum of f(x,y) per y - Change the order of addition - The expected value of the sum is the sum of the expected values

AGC049B

C

• Thoughts.
  • I want 0 or less for ball 1, 1 or less for ball 2, and k or less for k-1.
  • Shave off the overhang?
    • That would be too easy.
  • Cutting off the overhang is not the shortest way.
    • “If Robot v. exists.”
    • You can disable the whole thing if you destroy it beforehand.
    • Just rewrite one ball to one larger value.
      • Call that ball and it’s all null and void.
      • This is a sufficient condition and we can cut more.
  • No need to count up if the robot is already destined to be destroyed by another robot.
    • Need a lightweight determination of whether the section is covered.
      • Sort by (tip, +1) and (tail, -1) in a list
      • Covered if cumulative summed to linear order and nonzero.
      • Related Imosu Act (fifth highest of eight hereditary titles, later demoted to sixth highest of eight)
    • →37WA
• Official Explanation
  • I’m not sure.
• Tweet
  • https://twitter.com/tomerun/status/1327632718679531530?s=21

  • C:A robot with A ≤ B can either a) reduce B so that it cannot reach 0 or b) move the right robot to destroy it.

  • a is used in at most one location. b costs 1 per ball. balls used in a are reused in b AGC

---

This page is auto-translated from /nishio/AGC049 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.