Advanced Competitive Programming

Presentation on theme: "Advanced Competitive Programming"— Presentation transcript:

1 Advanced Competitive Programming
國立成功大學ACM-ICPC程式競賽培訓隊 Department of Computer Science and Information Engineering National Cheng Kung University Tainan, Taiwan

2 Week 2 Basic Programing STL 和 Coding 小知識

3 Outline Coding 小知識 STL sort 題目賞析 Vector String STL 可以在型態中宣告 STL
CodeForces 1130 B CodeForces 1137 A

4 Coding 小知識 cin and cout long long int 陣列 輸入加速方式 如何讀取包含空白的資訊 memset
sizeof 想要在掌握高階技能，必定要先從熟練基礎工具，無論是實作或是發想時的實驗都會大量地使用。

5 cin and cout 有很好的型態支援度 速度比 scanf 和 printf 慢？
ios::sync_with_stdio(0) cin.tie(0)

6 cin and scanf and getline
讀取到空白停止(終止字元是空白) 如果遇到需要讀取空白的情況，用 getline 解決(可設定終止字元) 使用頻率少，但是必須知道它的存在。

7 long long 有比較大的數值處理能力 使用時機：處理 int 範圍的測試資料時，如果過程中會有 加法 與 乘法 的操作
大約是 -4e18 ~ 4e18 PS：4e18 這個表示法相當於科學記號中的 4x1018 PS：如果連 long long 都沒辦法處理，那就是 大數 這個又更麻煩了。 改進。

8 陣列 初始化：memset 靜態宣告 與之後介紹的 vector<any_type> 比較
建議陣列宣告根據題目給定的“Max N”宣告大小 如果是想要根據題目給定的 N 宣告大小的話，建議使用動態的 vector<any_type>

9 STL vector<any_type> Cplusplus.com 說明文件簡介 string STL 可以套在 STL 裡面
動態特性 Cplusplus.com 說明文件簡介 string STL 可以套在 STL 裡面 然而 STLSTL 又可以套在 STL 裡面 然而 STLSTLSTL 又可以套在 STL 裡面 然而 STLSTLSTLST L又可以套在 STL 裡面 然而 STLSTLSTLSTLSTL 又可以套在 STL 裡面

10 vector<any_type>
vector::operator[] vector::size() vector::resize() vector::assign() vector::push_back() 說明文件：

11 C plus plus 說明文件簡介 以 vector::push_back()為例
如果覺得文件量太大，可以先專注在定義、範例、複雜度，三個地方。

12 C plus plus 說明文件簡介

13 C plus plus 說明文件簡介

14 C plus plus 說明文件簡介

15 string vector<any_type> 擁有的自帶函數 string 也有，如： 還有很多針對字串的自帶函數，如：
string::push_back() string::assign() 還有很多針對字串的自帶函數，如： string::substr() string::operator+= 也可以把 string 轉型態成 char[] 的字串型態： string::c_str()

16 string 字典序 簡單理解 設想一本英語字典里的單詞，哪個在前哪個在後？

17 STL 可以套在 STL 裡面 vector<any_type>，的範例： vector<int>：整數vector
vector<long long int>：長整數vector vector< vector<int> >：整數vector的vector

18 自學清單 pair set map first, second sort insert
set::iterator 的 operator++ 的時間複雜度 把整個 set 依序顯示 map map::operator[] 的時間複雜度 iterator 的 operator++ 的時間複雜度 把整個 map 依序顯示

19 sort 將一堆元素由"給定規則"排成一順序 對於整數 預設是定義 是否小於 的規則 對於字串 預設是定義 是否字典序小於 的規則

20 sort 5, 6, 9, 8, 2 這五個元素由小到大排為 2, 5, 6, 8, 9 a, bc, ay, aa 這四個元素由字典順序排為 a, aa, ay, bc

21 回顧字典序 簡單理解 bool operator< (cont string& lhs, const string& rhs);
設想一本英語字典里的單詞，哪個在前哪個在後？ bool operator< (cont string& lhs, const string& rhs);

22 string 字典序

23 vector sort 使用練習 請各位打開 judge.cp.ccns.io 練習題目 a002 練習&下課 15min鐘後繼續上課。

24 sort 將一堆元素由"給定規則"排成一順序 對於 vector<int> 這種型態呢？ 對於 自定義struct 的型態呢？
對於 any_type 呢？

25 自定義 sort 參考 cplusplus 網站上 sort 的定義 可以在第三個欄位放入自定義小於

26 自定義 sort 那我們是不是可以對 any_type 定義小於 那我們是不是可以對 vector<int> 定義小於

27 題目賞析 – CodeForces 1130 B 現在有兩個人，小藍和小紅他們在位置1。
現在有一數列中有 2 個 1、2 個 2 …、2 個 N，亂序 他們要各自依序拜訪 1 ~ N 且被拜訪過的位置不能被另一個人拜訪 請問兩人最小移動步數和為？

28 題目賞析 – CodeForces 1130 B Input 3 Output 9

29 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：0 Output 9

30 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：2 Output 9

31 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：4 Output 9

32 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：4+1 Output 9

33 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：4+3 Output 9

34 題目賞析 – CodeForces 1130 B Input 3 累計移動步數：4+5 Output 9

35 題目賞析 – CodeForces 1130 B Input 4 4 1 3 3 1 2 2 4 Output 23 位置 拜訪次序 1 4
5 6 7 8 有沒有人有想法

36 題目賞析 – CodeForces 1130 B 分析： 為了避免靠位置小的人走到下個拜訪中位置大的，造 成步數的浪費
小紅都去拜訪 i 中位置小的那家 小藍都去拜訪 i 中位置小的那家 我想很多人都可以想到這裡。 有沒有==

37 題目賞析 – CodeForces 1130 B 怎麼實現這個想法？

38 題目賞析 – CodeForces 1130 B 每個點有位置跟拜訪次序 兩個特徵 位置 拜訪次序 1 4 2 3 5 6 7 8

39 題目賞析 – CodeForces 1130 B 位置 拜訪次序 2 1 5 6 7 3 4 8 每個點有位置跟拜訪次序兩個特徵
如果我們按照 拜訪次序 排序

40 題目賞析 – CodeForces 1130 B 位置 拜訪次序 2 1 5 6 7 3 4 8 第奇數個row是拜訪順序中位置小的 小紅
小藍

41 題目賞析 – CodeForces 1130 B 實現這個想法？ 位置 拜訪次序 2 1 5 6 7 3 4 8

42 感受一下 excel 操作 – 自定義排序 位置 拜訪次序 1 4 2 3 5 6 7 8 位置 拜訪次序 2 1 5 6 7 3 4 8

43 題解說明 等等會示範用 vector 套 vector<int> 來存取資料
但是這題可以使用 vector 套 pair 來存取資料比較方便 不用自定義 sort，因為 pair 有 是否小於 的定義，熟悉的同學可以更快速的實作算法

44 vector 套 vector<int> - 示範
宣告

45 vector 套 vector<int> - 示範
初始化 Hint 若要動態宣告大小，一定要先獲得 題目規定 的數值。

46 vector 套 vector<int> - 示範
完整讀取資料示範

47 題目賞析 – CodeForces 1130 B 開始模擬走路吧！ 以上這題全部所需要使用到的基本操作就教給各位了！ 有了這些技巧之後
Hint 走路的步數會大於 int 範圍 以上這題全部所需要使用到的基本操作就教給各位了！ 有了這些技巧之後 就可以試試看思考題目 更方便的快速實作腦袋中的思路

48 題目賞析 – CodeForces 1107 A 現在有 Q 筆問題 每筆問題中有一個 N 代表之後的數字 S 是幾位數
可以的話輸出可能的拆法

49 題目賞析 – CodeForces 1107 A Input 2 6 654321 33 Output YES 3 NO

50 題目賞析 – CodeForces 1107 A 貼心小提示： 可以使用 string 儲存 可以使用 str.substr() 輸出

51 練習&下課時間 Take a break!

52 Outline 演算法的效率 設計演算法的思考方法

53 演算法的效率

54 Big O 2 倍、3 倍、甚至 10 倍的常數倍優化不是競賽時考慮 的要點。 我們所設計的演算法必須根據輸入規模 N 而定。

55 Big O Big O 表示法 f(N) = O(g(N)) ⟺ ∃M, c > 0. ∀N > M. |f(N)| ≤ c⋅|g(N)| 意思是說在 N 足夠大的時候，已經存在正數 c 使 得 c⋅|g(N)| 大於等於 |f(N)|

56 Big O 例如估計的時間函數: f(x)=x2+x+1 在 x 很大的時候， 主要影響整個函數值的大小是平方項 這時我們可以說 f(x) = O(x2)

57 Big O 設輸入規模為 N，常見的複雜度有： O(1) ≤ O(logN) ≤ O(N) ≤ O(NlogN) ≤ O(Nk) ≤ O(kN) ≤ O(N!) ≤ O(NN) 其中 k 為常數 (不隨輸入規模成長)

58 競賽規範 記憶體空間的規範各競賽都不相同 通常得考慮: - 遞迴深度 使用的變數多寡 程式碼長度

59 競賽規範 而競賽都以秒為單位去做時間限制 - 例如 1 秒、 3 秒、10 秒

60 合理的複雜度 通常會直接考慮資料的規模與計算出來 的複雜度 有個傳統(?)的限制： 107

61 合理的複雜度 假設題目: 規模為 N 而你: 設計出的演算法複雜度為 O(N2 logN)

62 合理的複雜度 x = N2 logN 得落在 x ≤ 107 左右 這樣的複雜度才不容易超時 也就是說如果 N = 105 那就得重新設計演算法 因為此時 x = 1010 * log(105) 超大

63 常見思考方法

64 演算法的設計思維 枚舉 動態規劃 分治法 貪心法

65 最大連續和問題 考慮整數數列: a(1), a(2), …, a(N) 讓 a(L), a(L+1), …, a(R) 盡量大
其中 1 <= L <= R <= N 例如 -4, 2, 3, -1, 0, 4, -5, 6, -7 的最大連續和為 9 [2, 3, -1, 0, 4, -5, 6]

66 演算法的設計思維 枚舉 動態規劃 分治法 貪心法

67 枚舉 所謂枚舉， 就是數出部份給定的集合中元素。 應用在問題中 將每個 L 與 R 配對舉出來 接著for(int k = L; k <= R; k++) sum += A[k]; 就能找出最大的 sum

68 枚舉: 最大連續和問題 其時間複雜度為 O(N3) int best = A[1];
for (int L = 1; L <= N; L++) { for (int R = L; R <= N; R++) { int sum = 0; for (int k = L; k <= R; k++) sum += A[k]; best = max(best, sum); } 其時間複雜度為 O(N3)

69 演算法的設計思維 枚舉 動態規劃 分治法 貪心法

70 動態規劃: 最大連續和問題 for (int L = 1; L <= N; L++) { sum[L][L-1] = 0;
for (int R = L; R <= N; R++) { sum[L][R] = sum[L][R-1] + A[R]; best = max(best, sum[L][R]); } 時間複雜度為 O(N2)

71 動態規劃 sum[L][L-1] = 0; for (int R = L; R <= N; R++) sum[L][R] = sum[L][R-1] + A[R]; 從邊界遞推地紀錄所有問題的解，且一個項用到前 一項的最佳結果 這就是在計算前綴和

72 動態規劃 好處是將會重複使用到的解都保存下來了，就能省 下不少時間 不用像枚舉一樣重新計算 for(int k = L; k <= R; k++) sum += A[k];

73 演算法的設計思維 枚舉 動態規劃 分治法 貪心法

74 分治法 分治 (divide & conquer) 簡稱 D&C 將一個大的問題 分成幾個互相獨立的子問題 然後再將子問題分成子子問題
一直重複分割的動作直到最小問題 (邊界) 接著讓子問題合併求出父問題。

75 分治法: 最大連續和問題 將數列切一半 (分割) 左半的最大連續和為何 (子問題) 右半的最大連續和為何 (子問題)
包含”切開的分水嶺”的最大連續和 (子問題✩) 選出三者中最大值，就是整個數列的解 (合併)

76 P [a(1), a(2), a(3), a(4), a(5)] 假設 N = 5
分治法: 原大小的問題 P [a(1), a(2), a(3), a(4), a(5)] 假設 N = 5

77 分治法: 分割問題 [a(1), a(2), a(3), a(4), a(5)]

78 [a(1), a(2), a(3), a(4), a(5)] P [a(1), a(2)] P [a(3), a(4), a(5)]
分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] P [a(1), a(2)] P [a(3), a(4), a(5)]

79 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)]
分治法: 分割問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)]

80 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] P [a(1)] P [a(2)]

81 分治法: 最小子問題(邊界) [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] [a(1)] P [a(2)] Return a(1)

82 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] P [a(2)]

83 分治法: 最小子問題(邊界) [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] [a(2)] Return a(2)

84 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] R=P [a(2)]

85 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] R=P [a(2)] P […, a(1), a(2), …]

86 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] R=P [a(2)] maxSum […, a(1), a(2), …]

87 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] L=P [a(1)] R=P [a(2)] M=maxSum […, a(1), a(2), …]

88 分治法: 合併問題 (回傳解) [a(1), a(2), a(3), a(4), a(5)] [a(1), a(2)] P [a(3), a(4), a(5)] Return max(L, M, R)

89 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] P [a(3), a(4), a(5)]
分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] P [a(3), a(4), a(5)]

90 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)]
分治法: 分割問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)]

91 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] P [a(3)] P [a(4), a(5)]

92 分治法: 最小子問題 (邊界) [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] [a(3)] P [a(4), a(5)] Return a(3)

93 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] P [a(4), a(5)]

94 分治法: 合併問題 (回傳解) [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] [a(4), a(5)] Return max(L, M, R)

95 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] R=P [a(4), a(5)]

96 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] R=P [a(4), a(5)] P […, a(3), a(4), …]

97 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] R=P [a(4), a(5)] maxSum [… a(3), a(4), …]

98 分治法: 子子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] L=P [a(3)] R=P [a(4), a(5)] M=maxSum [… a(3), a(4), …]

99 分治法: 合併問題 (回傳解) [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] [a(3), a(4), a(5)] Return max(L, M, R)

100 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] R=P [a(3), a(4), a(5)]
分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] R=P [a(3), a(4), a(5)]

101 分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] R=P [a(3), a(4), a(5)] P […, a(2), a(3),…]

102 分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] R=P [a(3), a(4), a(5)] maxSum […, a(2), a(3),…]

103 分治法: 子問題 [a(1), a(2), a(3), a(4), a(5)] L=P [a(1), a(2)] R=P [a(3), a(4), a(5)] M=maxSum […, a(2), a(3),…]

104 [a(1), a(2), a(3), a(4), a(5)] Return max(L, M, R)
分治法: 合併問題 (回傳解) [a(1), a(2), a(3), a(4), a(5)] Return max(L, M, R)

105 分治法: 原問題 P [a(1), a(2), a(3), a(4), a(5)]

106 分治法: 原問題 G=P [a(1), a(2), a(3), a(4), a(5)] 得到原問題的解了

107 分治法: 複雜度 假設原問題大小為: N 考慮實際時間花費

108 分治法: 時間花費 原問題時間花費為: T(N) 分割問題後為: T(N/2) + T(N/2) maxSum: N

109 分治法: 時間花費 合併問題得 T(N) = 2*T(N/2) + N 並且最小子問題 T(1) = 1

110 分治法: 時間花費 T(N) = 21 * T(N/21) + 1 * N = 21 * ( 2 * T(N/22) + N/21 ) + 1 * N = 22 * T(N/22) + 2 * N = 22 * ( 2 * T(N/23) + N/22 ) + 2 * N = 23 * T(N/23) + 3 * N = 23 * ( 2 * T(N/24) + N/23 ) + 3 * N … = 2? * T(1) + ? * N 想想看“問號”為多少？ 解釋 (lgN)*N 的式子由來

111 分治法: 複雜度 ⇒ T(N) = 2lgN + NlgN ⇒ T(N) = O(NlgN)
T(N) = 2lgN * T(1) + (lgN) * N ∧ T(1) = 1 ⇒ T(N) = 2lgN + NlgN ⇒ T(N) = O(NlgN) 解釋 (lgN)*N 的式子由來

112 演算法的設計思維 枚舉 動態規劃 分治法 貪心法

113 貪心法 每次做一個在當下看起來最佳的決策 進而漸漸求出全局最佳解 貪心法是動態規劃的特例

114 貪心法: 最大連續和問題 int best = A[1], sum = 0; for (int R = 1; R <= N; R++) { sum = max(A[R], sum + A[R]); best = max(best, sum); } 複雜度為 O(N) 解釋 (lgN)*N 的式子由來

115 更優的複雜度? 枚舉、動態規劃、分治法、貪心法 這些思考方式能讓我們想出怎樣設計演算法 但可不能只滿足於此，要不斷的思考是否還存在別 的演算法 解釋 (lgN)*N 的式子由來

116 Questions?