Introduction

枚舉是算法的基礎，以最原始的方式，看過所有可能答案。
舉個例子，假設現在要將一些數字由小到大排序，
最原始的方法就是枚舉所有排列，長度 n 的數組就有 n! 種可能。
排列實在太多了，必須優化。

觀察性質

可是要怎麼優化呢？
首先，可以先觀察問題的基本性質。
在排序的問題中，可以確定第一個數是最小的，先把它放到前面。

5 1 4 2 3
1 5 4 2 3

把 1 放到前面後，好像沒轍了，因此必須繼續觀察。
很明顯，排序 5 後面的數字，整個數組就算排完了。

1 [5 4 2 3]

對 5 後面的數字做同樣的事，把 2 提出來，再解後面的數組，以此類推。

1 [5 4 2 3]
1 2 [5 4 3]
1 2 3 [5 4]
1 2 3 4 [5]
1 2 3 4 5

時間複雜度: O(n^2)

還能更快嗎？

除了觀察性質外，也可以借助其他力量，例如 merge sort 使用了 divide and conquer 的概念，heap sort 用到 heap。

倒退一步

有時遇到瓶頸只能倒退一步，重新審視或建構算法，例如 counting sort 和 radix sort 就是跟前面不太一樣的方法。

例題

AtCoder Beginner Contest 119

題意自己看。
觀察性質後發現每根竹子 l_i 最後只有幾個結局(?)，成為 A,B,C 的一部份或丟掉。
枚舉 l_i 的去向後，再計算跟目標 A,B,C 長度差距。
時間複雜度: O(4^n)

可以壓到 O(3^n)

Codeforces 1494B

題目中最麻煩的是角落會同時影響兩方向的黑格數量。
幸運的是，角落只有四個，枚舉它們是否塗黑即可輕鬆算出答案。

Codeforces 1646E

1 1 1 1 1
2 4 8 16 32
3 9 27 81 273
4 16 64 256 1024

表中可觀察重複的數字只會是某數的次方，
3^a 不可能等於 2^b，不同根互不影響，因此只需針對每個根算答案。

畫出下表繼續觀察（x 不是某數的次方）。

x x^2 x^3
x^2 x^4 x^6
x^3 x^6 x^9

表中 row a column b 的數字是 (x^a)^b=x^(ab)，
對於數字 x^(ab) 來說，如果上面有 x^(cd) 且 ab == cd && c < a，它就是重複的。
由此可算 x 在 (n,m) 的表裡有多少重複的數字，解出 x^n 的數量。

如果看不懂可以參考解答，或是直接問我。

其他題目

• Codeforces 1553E
• Codeforces 1651C
• Codeforces 1555D

明天應該會寫較複雜的枚舉和 dfs。