D - Practical Skill Test image

  • Thoughts.
    • The query is 10
    • The size of the board is 9,000
    • A linear order will not be enough to find the requested value from the board in time.
    • Even with constant order, if you have to do “10^5 times, increasing by 1 from 1 to 90000” as a nasty problem, you still won’t be able to do it in time.
    • I mean, the number is 90,000 and the query is 100,000, so we should expect a lot of overlap.
    • In other words, where costs add up, they should be cashed.
    • First, create an inverse mapping table from numbers to coordinates in linear order
    • Then, for each remainder divided by D, make a cumulative sum of the D books.
      • This would be of linear order if the inverse mapping table
    • If you prepare this far, one query will be of constant order.
  • Official Explanation OK

ABC089D


This page is auto-translated from /nishio/ABC089D 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.