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 Outline 賽後檢討 Graph (基本資料結構) map, set and priority_queue DFS & BFS

3 賽後檢討 常用手法以及容易忽略的細項

4 Outline 解題建議步驟 Coding 的注意事項 自我修練的方法

5 Outline 解題建議步驟 Coding 的注意事項 自我修練的方法

6 演算法競賽跟數學競賽很像 以第一次比賽的 z004 傷害 作為例子 把題目描述看過 簡單的看過 Input & Output 格式說明 對著 Sample 自己手動模擬一次 接著注意看各種條件限制 思考演算法的實現(通常先考慮正確性再想效率)

7 Outline 解題建議步驟 Coding 的注意事項 自我修練的方法

8 測資範圍 陣列開大一點點 假設測資大小為 1 ~ 2*105 int const maxn = 2e5 + 10; int a[maxn];

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

10 getline cin.ignore(); while (getline(cin, str)) {
if (str.empty()) break; : . }

11 Outline 解題建議步驟 Coding 的注意事項 自我修練的方法

12 讀書 算法競賽入門經典（第2版） 挑戰程序設計競賽（第2版） 資訊之芽 建中資訊科培訓講義

13 看題解 每打完一場比賽就去看別人怎麼寫的 不管該題自己是否已經解出來，別人的想法都值 得學習 有時候可以為別人挑毛病，有效率的減少自己出 錯率 有時別人比你更勝一籌，用更優雅的方法實作了 演算法

14 看題解 不會的題目，不建議先直接看解答，最好先想 過一遍，束手無策才去看解答 因為從無到有想法的誕生過程很重要，這些幾 乎是別人很難教給你的

15 討論 對於某個領域，大致可以分成強者以及弱者 而面對這兩類人， 強者:把問題清晰地描述出來，請教他 弱者:把解答清晰地描述出來，教會他 事物能清晰表達 ⇒ 看出對於事物的掌握度 ⇒ 能很快的實現演算法

16 Questions?

17 Data Structures

18 Outline Graph Tree Disjoint sets

19 Graph 圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構。

20 Graph 點 (vertex)： 組成圖的最基本的元素 邊 (edge)： 點與點的關係
有向圖 (directed graph)： 邊帶有方向性 無向圖 (undirected graph)： 每條邊都是雙向的 ->沒有方向性

21 Graph 道路 (walk)： 點邊相間的序列， e.g. v0e1v1e2v2...envn 路徑 (path)： 點不重複的道路
環 (cycle)： 路徑的起點與終點連接後形成環 走訪/遍歷 (traversal/search)： 走完全部的點或邊

22 該怎麼表示一張圖呢

23 Graph 鄰接矩陣 用一個二維陣列 g[i][j] 來表示從 i 點到 j 點的距離 通常會有一個特殊的值來表示無法到達的情況
例如 INT_MAX or -1

24 Graph 鄰接表 常用 vector 表示一張圖 vector<int> e[N]; int from, to;
while (cin >> from >> to) { e[from].push_back(to); } e[i] 代表 i 能夠走到的點的陣列

25 Tree Tree 是一個有向無環連通圖 節點 (node)： 一般樹上的點 父 (parent)： 節點能反向拜訪的第一個節點
子 (child)： 節點能正向拜訪的第一個節點 根 (root)： 沒有父節點的節點 葉 (leaf)： 沒有子節點的節點

26 Tree 每個點都是節點 根 G的父 B的子 葉 葉 葉 葉 葉 葉

27 Tree 祖先 (ancestor)： 節點能反向拜訪的所有節點 孫子 (descendant)： 節點能正向拜訪的所有節點
深度 (depth)： 節點的深度為從根到該節點所經過 的邊數 森林 (forest)： 一個集合包含所有不相交的 Tree 每個非根節點只有一個父節點

28 Tree

29 Tree

30 Tree G的Depth為2

31 Tree G的祖先

32 Tree G的孫子

33 Disjoint sets 有點像是把人分組 不同組不會有相同的元素 (不能分身) 要對組別或是人做大量的操作

34 Disjoint sets 操作 將新的人加入組別 將兩個組合併 查詢一個組別的人數 查詢某人屬於哪一組 從某個組刪除一個人 (較難)

35 Disjoint sets 實作方式 為了能夠快速完成操作，採用以下的方式表達 Disjoint sets 以一棵樹來表達一個組

36 Disjoint sets Initialization
for (v = 1;v <= N; v++) group[v] = v

37 Disjoint sets Find 假設有元素 1 ~ 5，其中 1,2 一組，3,4,5 一組 group[] [1] [2] [3]
[4] [5] 1 3 4 group[]

38 Disjoint sets Find int Find(int v) { if (v == group[v]) return v; return group[v] = Find(group[v]); }

39 Disjoint sets Find [1] [2] [3] [4] [5] 1 3 group[]

40 Disjoint sets Union void Union(int u, int v) { group[Find(u)] = Find(v); }

41 Disjoint sets Union 範例 UVa OJ 879 Circuit Net

42 Questions?

43 map, set and priority_queue
好用的 Standard Template Library 第三彈

44 map, set and priority_queue 共同特色
依照給定的規則儲存。

45 map 考慮下列情況： 從名字查詢年齡，需要怎麼規劃 儲存與查詢的方法？
用整數索引找資料 int a[5] = {3, 7, 2, 7, 5}; cout << a[3]; //7 cout << a[1]; //7 cout << a[0]; //3 考慮下列情況： 從名字查詢年齡，需要怎麼規劃 儲存與查詢的方法？

46 map 在 array 中： 資料型態 可以自由定義 索引 卻只能是整數 索引 資料型態
用整數索引找資料 int a[5] = {3, 7, 2, 7, 5}; 在 array 中： 資料型態 可以自由定義 索引 卻只能是整數 索引 資料型態

47 map 索引 資料型態 map<char,string> mymap; mymap['a']="an element";
mymap['b']="another element"; mymap['c']=mymap['b']; cout << mymap['b']; //another element cout << mymap['a']; //an element map<char,string> mymap; 索引 資料型態

48 map 好用的代價 新增與取值的操作為O(logN) 新增與取值的操作為O(1) mymap['b']="apple";
cout << mymap['b’]; 新增與取值的操作為O(logN) a[0]=18; cout << a[0]; 新增與取值的操作為O(1)

49 map 遍歷 map<char,int> mymap; mymap['b'] = 100, mymap['a'] = 200, mymap['c'] = 300; for (auto it = mymap.begin(); it != mymap.end(); it++) cout << it->first << " => " << it->second << endl; Output: a => 200 b => 100 c => 300

50 常見的 map member function
map::size map::clear

51 題目賞析 － CodeForces 1133D 第一行有一個整數N，代表之後兩行各有N個整數 5

52 題目賞析 － CodeForces 1133D 第二、三行有N個整數，是 A1 ～ AN 以及 B1 ～ BN 5 1 2 3 4 5

53 題目賞析 － CodeForces 1133D 請問選出實數 D 做一個操作後形成新的數列 C Ai x D + Bi = Ci

54 題目賞析 － CodeForces 1133D Input 5 1 2 3 4 5 2 4 7 11 3 Output 2 D 選擇 -2
1 2 3 Output 2 D 選擇-1/13

55 題目賞析 － CodeForces 1133D 列出 Ai x Di + Bi = 0 的數列 D 看哪一個 Di 重複最多次
為了避免浮點數誤差我們使用分數 這個分數在數列 D 中出現的次數 索引 資料型態

56 題目賞析 － CodeForces 1133D 這題有兩個難點： 找出 Greatest Common Divisor 使分子分母互質
當有 0 出現的case

57 set 考慮下列情況： 在一篇文章中計算使用了哪些不同的字。

58 set 遍歷 int myints[] = {75,23,65,42,13,75,65}; set<int> myset(myints,myints+7); for (auto it = myset.begin(); it != myset.end(); it++) std::cout << ' ' << *it; Output:

59 set 特性 {2, 4, 4, 4, 4, 6} and {2, 4, 6} 是一樣的集合

60 常見的 set member function
新增元素 set::insert 元素存在查詢 set::count 元素刪除 set::find, set::erase 搭配使用

61 set 刪除 int myints[] = {75,23,65,42,13,75,65}; set<int> myset(myints,myints+7); myset.erase(myset.find(65)); for (auto it = myset.begin(); it != myset.end(); it++) std::cout << ' ' << *it; Output:

62 priority_queue 類似 queue 的元素使用方式 類似 set 的元素順序性

63 priority_queue priority_queue<int> mypq; mypq.push(30); mypq.push(100); mypq.push(25); mypq.push(40); while (!mypq.empty()) { int now = mypq.top(); mypq.pop(); cout << ' ' << now; } Output:

64 常見的 priority_queue member function
priority_queue::push priority_queue::pop priority_queue::top priority_queue::empty

65 練習題 a005: Good Cake Defender a006: Zero Quantity Maximization

66 參考解答 a006:

67 Questions?

68 Outline 深度優先搜尋 (Depth-First Search) 廣度優先搜尋 (Breadth-First Search)

69 q a 前提 o c k 給定圖 y p w t z g x e h f n s l i j

70 q a 目的 o c k 搜他 y p w t z g x e h f n s l i j

71 通常 沒有想像中的美好 可能你的起點被限制的很嚴苛 離目標有一大段距離 寸步難行，要考慮很多條件 有些點可能是陷阱， 不能使用轉移水晶

72 深度優先搜尋

73 DFS 深度優先搜尋 (Depth-First Search) 簡稱 DFS

74 DFS 的點遍歷順序 為每拜訪一個未曾拜訪節點 (拜訪中) 就往其一鄰點拜訪過去 當拜訪完此節點，返回到父節點 *節點: DFS 遍歷完會產生一顆樹 *某節點拜訪完: 其子孫節點都拜訪完

75 DFS 實作 void dfs(int u, int dep) { // dep := depth for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; dfs(v, dep+1); }

76 DFS 實作 (非遞迴) stack<int> S; // 此處少記錄一個 dep S.push(root); // root 代表走訪此圖的起點 vis[root] = true; while (!S.empty()) { int u = S.top(); S.pop(); for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; S.push(v); }

77 a 給定一個連通圖 o c k p z g h f l i j

78 整理一下 a c p k o f g h i l z j

79 DFS 的點遍歷順序 1 2 5 B C 3 4 6 8 9 A 7

80 第一個拜訪的為根 藍色為未曾拜訪 1 c p k o f g h i l z j

81 拜訪鄰點 黃色為拜訪中 1 2 p k o f g h i l z j

82 拜訪鄰點 1 2 p k o 3 g h i l z j

83 拜訪鄰點 1 2 p k o 3 4 h i l z j

84 拜訪完 1 2 p k o 3 4 h i l z j

85 拜訪完 紫色為拜訪完 1 2 p k o 3 4 h i l z j

86 拜訪完 1 2 p k o 3 4 h i l z j

87 拜訪鄰點 1 2 5 k o 3 4 h i l z j

88 拜訪鄰點 1 2 5 k o 3 4 6 i l z j

89 拜訪鄰點 1 2 5 k o 3 4 6 i l z 7

90 拜訪完 1 2 5 k o 3 4 6 i l z 7

91 拜訪鄰點 1 2 5 k o 3 4 6 8 l z 7

92 拜訪完 1 2 5 k o 3 4 6 8 l z 7

93 拜訪完 1 2 5 k o 3 4 6 8 l z 7

94 拜訪鄰點 1 2 5 k o 3 4 6 8 9 z 7

95 拜訪完 1 2 5 k o 3 4 6 8 9 z 7

96 拜訪鄰點 1 2 5 k o 3 4 6 8 9 A 7

97 拜訪完 1 2 5 k o 3 4 6 8 9 A 7

98 拜訪鄰點 1 2 5 B o 3 4 6 8 9 A 7

99 拜訪完 1 2 5 B o 3 4 6 8 9 A 7

100 拜訪完 1 2 5 B o 3 4 6 8 9 A 7

101 拜訪鄰點 1 2 5 B C 3 4 6 8 9 A 7

102 拜訪完 1 2 5 B C 3 4 6 8 9 A 7

103 根拜訪完 1 2 5 B C 3 4 6 8 9 A 7

104 此樹稱為 DFS 樹 1 2 5 B C 3 4 6 8 9 A 7

105 此樹稱為 DFS 樹 整理一下 (去紅邊) 1 2 5 C 3 6 9 A B 4 7 8

106 Uva 572 Oil Deposits GeoSurvComp 石油公司負責探勘某塊地底下的石油含 量，這塊地是矩行的，並且為了探勘的方便被切割為許 多小塊。 他們使用儀器對每個小塊去探勘。含有石油的小塊稱為 一個 pocket。假如兩個 pocket 相連，則這兩個 pocket 屬於同一個 oil deposit 你的任務就是要找出這塊地包含幾個不同的 oil deposit

107 Uva 572 Oil Deposits 輸入: 1 1 * 輸出: 0

108 Uva 572 Oil Deposits 輸入: 3 5 輸出: 1

109 Uva 572 Oil Deposits 輸入: 1 8 輸出: 2

110 Uva 572 Oil Deposits 輸入: 輸出: 2

111 Uva 572 Oil Deposits int count = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (plot[i][j] == { dfs(i, j); count++; }

112 Uva 572 Oil Deposits void dfs(int r, int c) { if (plot[r][c] == '*') return; plot[r][c] = ‘*’; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) if ( r+dr >= 0 && r+dr < m && c+dc >= 0 && c+dc < n) dfs(r+dr, c+dc); }

113 廣度優先搜尋

114 BFS 廣度優先搜尋 (Breadth-First Search) 簡稱 BFS a c p k o f g h i l z j

115 BFS 的點遍歷順序 為每拜訪一個未曾拜訪節點 (拜訪中) 就往所有鄰點拜訪過去 當拜訪完此節點，回第一個拜訪中鄰點 *節點: BFS 遍歷完會產生一顆樹 *某節點拜訪完: 其鄰點都拜訪中

116 BFS 程式碼 queue<int> Q; Q.push(root); //root 代表走訪此圖的起點 vis[root] = true; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; Q.push(v); }

117 BFS 的點遍歷順序 a c p k o f g h i l z j

118 BFS 的點遍歷順序 1 2 3 4 5 6 7 8 9 A B C

119 第一個拜訪的為根 藍色為未曾拜訪 1 c p k o f g h i l z j

120 拜訪所有鄰點 黃色為拜訪中 1 2 p k o f g h i l z j

121 拜訪所有鄰點 1 2 3 k o f g h i l z j

122 拜訪所有鄰點 1 2 3 4 o f g h i l z j

123 拜訪所有鄰點 1 2 3 4 5 f g h i l z j

124 根拜訪完 紫色為拜訪完 1 2 3 4 5 f g h i l z j

125 拜訪所有鄰點 1 2 3 4 5 6 g h i l z j

126 拜訪所有鄰點 1 2 3 4 5 6 7 h i l z j

127 拜訪完 1 2 3 4 5 6 7 h i l z j

128 拜訪所有鄰點 1 2 3 4 5 6 7 8 9 A B j

129 拜訪完 1 2 3 4 5 6 7 8 9 A B j

130 拜訪完 1 2 3 4 5 6 7 8 9 A B j

131 拜訪完 1 2 3 4 5 6 7 8 9 A B j

132 拜訪完 1 2 3 4 5 6 7 8 9 A B j

133 拜訪完 1 2 3 4 5 6 7 8 9 A B j

134 拜訪所有鄰點 1 2 3 4 5 6 7 8 9 A B C

135 拜訪完 1 2 3 4 5 6 7 8 9 A B C

136 拜訪完 1 2 3 4 5 6 7 8 9 A B C

137 拜訪完 1 2 3 4 5 6 7 8 9 A B C

138 拜訪完 1 2 3 4 5 6 7 8 9 A B C

139 拜訪完 1 2 3 4 5 6 7 8 9 A B C

140 BFS 樹 1 2 3 4 5 6 7 8 9 A B C

141 BFS 樹 1 2 3 4 5 6 7 8 9 A B C

142 Uva Fire! Joe 在一個迷宮工作，不幸的是，迷宮中有幾處發 生火災，Joe 想要逃離這個迷宮 Joe 和火每分鐘移動一格，可往東西南北四個方向 行走，但火每次向四個方向擴散一格 給定一個地圖，給出 Joe 逃離迷宮的最短時間

143 Uva Fire! 輸入: 4 4 #### #JF# #..# 輸出: 3

144 Uva Fire! 輸入: 3 3 ### #J. #.F 輸出: IMPOSSIBLE

145 Uva Fire! 第四週教材裡有題解

146 BFS 與 DFS 很相似

147 比較一下 各位可能會發現，兩者程式碼非常相似

148 DFS 程式碼 stack<int> S; S.push(root); //root 代表走訪此圖的起點 vis[root] = true; while (!S.empty()) { int u = S.top(); S.pop(); for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; S.push(v); }

149 BFS 程式碼 queue<int> Q; Q.push(root); //root 代表走訪此圖的起點 vis[root] = true; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto v: E[u]) { if (vis[v]) continue; vis[v] = true; Q.push(v); }

150 複雜度 因為每條邊都會走走看 所以複雜度為 O(E) 其中 E 為原圖的總邊數

151 Questions?