Typical ideas for coming up with solutions in competitive programming

Typical ideas for coming up with solutions in competitive programming | Algorithmic Logic

• There is quite a bit of overlap with what was being verbalized to put Power of Attribution on.

• Think in terms of input constraints - Small constraint problem - Constraints with N around 8 - Constraints with N around 10~20 - Constraints with N around 30~40 - Constraints with N around 50 O(N^4) OK - Constraints with N around 300~500 - Constraints with N around 1000

• Take it apart and think about it. - Notice the small constants.

  • Fix one variable
    • Fix the middle of three things
  • Half of the queue
  • divide into X and Y
  • Note the invariants of the operation.
  • focus on the even and odd
    • even and odd cases
  • independent of the order of operations
  • time reversal (physics)
  • Undoable operations
  • Cumulative product from left to right
  • Addition of isoperimetric sequences focuses on the difference
  • Composition of interval inversion is XOR
  • Grundy number
  • have an after-event
  • Binary search for k-th number
  • XOR is addition without carryover
  • XOR can be split by digit
  • 45 degree rotation
  • Minimize difference is median
  • Typical graphs for consideration
  • Tree is a two-part graph
  • Diameter of tree
  • Maximization with bisection search.
  • Greed from those with fewer options.
  • Bipartite graph of two-dimensional coordinates
  • Make the order a directed graph
  • Extreme values of convex functions are tristimulus searches
  • Shakudori method for monotonic increase
  • The equi-proportion sequence focuses on the remainder
  • N-decimal numbers focus on the remainder.
  • Bracketed rows are up and down

• Typical ideas for coming up with solutions in competitive programming to review the issues mentioned.

• keyence2020_d

• abc152_f

• agc026_c

• arc060_a

• JOI2008HO_C

• ABC034D

• ABC138E

• ABC023D

This page is auto-translated from /nishio/競技プログラミングで解法を思いつくための典型的な考え方 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.