alanhc-til

title: 競技程式路線圖 date: 2024-04-06 tags:

• competitive_programming
• roadmap updated: 2024-04-06 up:
• "[[競技程式]]"

• Competitive Programming Roadmap (target: [gray, blue])
  • Competitive programming roadmap here.

如何擅長？

• 想什麼？
  • 快速瞭解問題成標準問題
  • 簡化問題
• 如何思考
  • 分析敘述、數學方程式、觀察結果

如何練習？

Codeforces problemset ：適合有經驗，網路找不到答案 CSES 150: 標準問題 AtCoder problemset: 初學者友善

Competitive programming roadmap 

abc240_a - Edge Checker abc220_a - Find Muliple Time complex Python可以跑4秒，C可以2秒，大約10^8

2. Loops and arrays

• Time Complexity
  • $O(1)$: 數學解
  • $O(logn)$: Binary Search, Sorted set/map, priority queue per operation
  • $O(\sqrt{n})$: 質因數分解
  • $O(n)$: two pointer
  • $O(nlogn)$: Sorting(merge sort)
  • $O(n^2)$: Quick sort (worst case)
  • $O(n^k)$: iter subset of size k, e.g. iter all triplets $O(n^3)$
  • $O(2^n)$: iter all subsets
  • $O(n!)$: iter all permutations
• 透過下表看演算法會不會超過時間 abc204_b - Nuts abc205_b - Permutation Check abc206_c - Swappable abc220_c - Long Sequence abc196_c - Doubled abc194_c - Squared Error

Ref