###### tags: `Algo` <style> /* basic design */ .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6, .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p { text-align: left; line-height: 1.8; letter-spacing: normal; text-shadow: none; word-wrap: break-word; } .reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6 {font-weight: bold;} .reveal section img {background:none; border:none; box-shadow:none; max-width: 95%; max-height: 95%;} .reveal blockquote {width: 90%; padding: 0.5vw 3.0vw;} .reveal code {line-height: 1.2;} .reveal p, .reveal li {padding: 0vw; margin: 0vw;} .reveal .box {margin: -0.5vw 1.5vw 2.0vw -1.5vw; padding: 0.5vw 1.5vw 0.5vw 1.5vw; background: #EEE; border-radius: 1.5vw;} /* blockquote design */ .reveal blockquote { width: 90%; padding: 0.5vw 0 0.5vw 6.0vw; font-style: italic; background: #f5f5f5; } .reveal blockquote:before{ position: absolute; top: 0.1vw; left: 1vw; content: "\f10d"; font-family: FontAwesome; color: #2980b9; font-size: 3.0vw; } /* font size */ .reveal h1 {font-size: 5.0vw;} .reveal h2 {font-size: 4.0vw;} .reveal h3 {font-size: 2.8vw;} .reveal h4 {font-size: 2.6vw;} .reveal h5 {font-size: 2.4vw;} .reveal h6 {font-size: 2.2vw;} .reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {font-size: 2.2vw;} .reveal code {font-size: 1.6vw;} /* new color */ .red {color: #EE6557;} .blue {color: #16A6B6;} /* split slide */ #right {left: -18.33%; text-align: left; float: left; width: 50%; z-index: -10;} #left {left: 31.25%; text-align: left; float: left; width: 50%; z-index: -10;} </style> <style> /* specific design */ .reveal h1 { margin: 0% -100%; padding: 2% 100% 4% 100%; } .reveal h2 { text-align: center; margin: -5% -50% 2% -50%; padding: 4% 10% 1% 10%; } </style> # 2019/11/16 --- ## 原出處 - [KUPC2017](https://atcoder.jp/contests/kupc2017), [official site](http://www.kupc.jp/#/2017/) - A: Credits - B: Camphor Tree - C: Best Password - D: Sanmoku - E: Treasure Hunt - G: encode/decode 2017 - H: Make a potion - [KEYENCE Programming Contest 2019](https://atcoder.jp/contests/keyence2019) - E: Connecting Cities - 新北市資訊學科能力競賽 - Tree Coloring --- ## A - Credits Greedy: 從學分大的課開始選 --- ## B - Camphor Tree  給 S,T，問 S 到 T 是不是往上的一條路 ---  觀察: 每往下一個點編號剛好/2，所以把 T 一直 /2 看可不可以變成 S 就好 --- ## C - Best Password 給整數 A 和字串 S，找出一個 hash 一樣的字串，讓長度越短越好，長度一樣的話字典序越大越好。hash: $$A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]$$ --- ### 想法1 把 S 的 hash 算出來，那麼答案的字母應該是把 hash 值寫成 A 進位同餘 - ans[1] ≡ hash / A % A (mod A) - ans[2] ≡ hash / A / A % A (mod A) - ans[3] ≡ hash / A / A / A % A (mod A) - ... ```python hash = get_hash() / A while hash: c = hash % A while c+A<=26: c+= A # 得到最前面字母是 c hash = (hash-c)//A # 繼續求後面 ``` --- ### 想法2 - 也可以從第一個字元開始，每次把最前面字母+A，後面的字母-1 - 實作上有點像大數的進/退位 --- ## D - Sanmoku 問題: 在 $n \times n$ 的格子上填正整數，讓各個方向連續三格數字種類數至少有兩種。 - 要怎麼讓最大填的數字最小? - 在最小的情況，有幾種填法? --- 觀察: <table> <tr><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td></tr> <tr><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td></tr> <tr><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td></tr> <tr><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td></tr> <tr><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td></tr> <tr><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td></tr> <tr><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td></tr> <tr><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td></tr> </table> - 最大的數字小於等於 2 - n大一點的情況這樣填就好 - 填法好像只有幾種?? --- 填法真的很少所以可以爆搜。做法: 從左上到右下枚舉 1 or 2，每次往前面檢查有沒有衝突，有的話就剪枝掉 <table> <tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>o</td><td>.</td><td>o</td><td>.</td><td>o</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>.</td><td>o</td><td>o</td><td>o</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>o</td><td>o</td><td>?</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> <tr><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td><td>.</td></tr> </table> --- <table> <tr><th>n</th><th>最小值</th><th>狀態數</th></tr> <tr><td>1</td><td>1</td><td>1</td></tr> <tr><td>2</td><td>1</td><td>1</td></tr> <tr><td>3</td><td>2</td><td>32</td></tr> <tr><td>4</td><td>2</td><td>18</td></tr> <tr><td>5+</td><td>2</td><td>8</td></tr> </table> --- ## E - Treasure Hunt 每個寶箱有相對應的價值，每個鑰匙能開兩個寶箱其中之一。問要怎麼開始得到的總價值最多? --- 把寶箱看成點，鑰匙看成邊。考慮每個連通塊，如果是樹的話: <center> <img src='https://i.imgur.com/zcimCFH.png'></img> </center> --- 假設每條邊都往下指的情況，只有根的寶箱沒選到（邊指的方向 = 開哪個寶箱）。 <center> <img src='https://i.imgur.com/t6SPBwd.png'></img> </center> --- 性質: 給你一棵樹，可以選任意點當根。 => 只有根節點的寶箱開不了 => 不開的寶箱是哪一個可以自己決定 <center> <img src='https://i.imgur.com/icHWKnk.png'></img> </center> --- 不是樹的 case: 所有寶箱都開得到 理由: 一定有一個點在環上(非樹邊)，那就讓那個點當根結點其他點照樹邊開就好了。 --- 結論，對於每個連通塊: - 如果是一棵樹: 除了價值最小的寶箱都可以開 - 不是樹: 所有寶箱都可以開 對每個連通塊: - 判斷是不是樹 - 求出寶箱價值總和以及價值最小的寶箱 就好了 --- ## F - encode/decode 2017(1) 要你輸出一張圖，把一個整數 x encode 在裡面。條件: - 剛好有 100 個點 - 某些邊沒辦法輸出，不能輸出的邊剛好是一棵樹 - 不可以有自環或者重邊 --- <center> <img src="https://i.imgur.com/SCOuyxx.png"></img> </center> --- <center> <img src="https://i.imgur.com/sV1VJUM.png"></img> </center> --- - encode: 輸出一張 x 條邊的圖 - decode: 輸出邊數 AC --- ## G - encode/decode 2017(2) 同上，$x \le 10^{18}$ --- 第一個想法: 要怎麼壓一個 60 個 bit 的整數? 可不可以做一條長度 60 的 path，想個辦法把每個 bit 表示出來? --- 例子: 下面的圖是二進位的 1010，有分叉=1，沒分叉=0 <center> <img src="https://i.imgur.com/C7C1RdD.png"></img> </center> 問題點: 進到 decode phase 的時候編號會被打亂，要怎麼知道這個是 0101 還是 1010?? --- 改進: 我們在起始點加一個觸角，這樣就可以分別起點和終點了! 判斷方法: 全圖只會有一個點度數 >= 4 <center> <img src="https://i.imgur.com/Z8vLcHw.png"></img> </center> --- 分析 - 60個 bit 各一個點 - 每個如果bit是 1 的話要再加 1 個點，最多 60 - 另外 3 個點當觸角 （´-\`）.｡oO (當每個 bit 都是 1 的時候最多會要 123 個點) --- 改進: 舉例來說，當 1 太多的時候我們可以記錄一個符號，把 1 的 bit 和 0 的 bit 反過來紀錄 例子: 如果 p1 p2 相連的話代表求出來的 1/0 要反過來 判斷方法: 有沒有存在一個點數 = 2 的聯通塊 <center> <img src="https://i.imgur.com/YhIGTyU.png"></img> </center> --- decode 算法: - 找一個 degree>=4 的點當作起點 - 從起點找一條長度 60 的路徑，還原 60 個 bit - 再找圖上有沒有點數=2的聯通塊，有的話把上面 bit 反過來 分析2: - 60個 bit 各一個點 - min(#bit=0, #bit=1) <= 30 - 另外 3 個點當觸角 - 另外 2 個點紀錄有沒有相反 95個點 --- 其他: - 要怎麼樣求出一條長度 60 又根原本 T 不重複邊? - 可以 random 找 - 或者可以利用樹是二分圖的性質好好做(二分圖中，同樣顏色的點互不相聯 = 可以隨意加邊) - 其他解法不少，但大部分都非常難寫 --- ### 解法X - encode: 輸出一張0條邊的圖，把 X output 到 `/tmp/foo` - decode: 把 `/tmp/foo` 的數字輸出出來 Atcoder可以過，但是 domjudge 不能用。domjudge 好強 --- ### 值得一提的事情 ```bash "$MYDIR/conv1" < "$TESTIN" > "_in1" "$@" < "_in1" > "_out1" "$MYDIR/checker1" "$TESTIN" "_out1" "_out1" EXITCODE=$? if [ "$EXITCODE" -ne 0 ]; then echo "WA1" > "$PROGOUT" echo "======" >> "$PROGOUT" cat "_out1" >> "$PROGOUT" exit 43 fi "$MYDIR/conv2" "$TESTIN" < "_out1" > "_in2" "$@" < "_in2" > "_out2" "$MYDIR/checker2" $TESTIN "_out2" "_out2" EXITCODE=$? if [ "$EXITCODE" -ne 0 ]; then echo "WA2" > "$PROGOUT" echo "======" >> "$PROGOUT" cat "_out2" >> "$PROGOUT" exit 43 fi echo "AC" > "$PROGOUT" exit 0 ``` - 每一份 output 都有一個專屬的 checker - 每一份 input 也都有一個專屬的 converter - 為什麼第一份 input 也要 convert? --- ### judge的公平性 - 當參加者輸出同樣的東西時，理論上 judge 結果要是一樣的。 - 可是當要轉成 decode 測資的時候有隨機編號，有可能會造成某次傳 AC 某次 WA?? - 為了避免這樣的情況，其實重新編號的過程並不能是隨機決定的 - 或者說: 對於同一筆 input 以及同一筆 encode output，轉成的 decode input 必須是一樣的 為了避免這樣的情況發生，在每筆測資的後面會偷放一個 random seed。要重邊號的時候會按照這個 seed 去亂數。例如下面是裁判真正看到的 input: ``` 100 99 99 95 (中間省略) 22 30 317942985495155176 <= X 的值 56638772004192693 <= random seed ``` --- ### I. Tree Coloring(1) 給一個 n 層的樹，問 R,G,B 各有幾個(n <= 30) <center> <img src="https://i.imgur.com/H9NuQE9.jpg"></img> </center> --- 第 i 層 = $2^{i-1}$ 個節點 - R的個數: $2^{i-1}/3 + ((2^{i-1}\%3) \ge 1)$ - G的個數: $2^{i-1}/3 + ((2^{i-1}\%3) \ge 2)$ - B的個數: $2^{i-1}/3$ 每一層加起來就好 --- ### J. Tree Coloring(2) 給一個 n 層的樹，問 R,G,B 各有幾個(n <= 1,000,000,000) <center> <img src="https://i.imgur.com/H9NuQE9.jpg"></img> </center> --- - 總節點數 = $2^0 + 2^1 + ... 2^{n-1} = 2^n - 1$ - A = 節點數 mod3=1 的層數 = n/2 + n%2 - B = 節點數 mod3=2 的層數 = n/2 - 其餘 $2^n - 1 - A - 2B$ 個節點應該是均分在 R,G,B 三種顏色，所以除以 3 就好 - 要怎麼除以3? 模逆元! --- ## K - Connecting Cities(1) 最小生成樹直接做 --- ## H - Make a potion 見 [pdf](http://www.kupc.jp/static/media/H.ab00f1d5.pdf) p6,p7,p11 解釋: - f(i,j) = 第 i 種液體有沒有使用 j 體積以上，有的話=1，沒的話=0 - f(i,j-1) >= f(i,j) - 把所有 f(i,j) 當成點做一個最小割 - S集合 f(i,j) = 1，T集合 f(i,j) = 0 - f(i,j)點太多怎麼辦? 可以離散的求(對於液體i，只有最小、最大、以及每個和i有關的條件的體積有用而已) - 先假設正的效果全部拿到，減掉最小割=答案 - 加分加最多 = 扣分扣最少的技巧 --- ## L - Connecting Cities(2) 給 D,A，連接 i,j 的邊權是 $D|i-j| + A_i + A_j$。求這張圖的最小生成樹 --- ### 先輩知識1: MST性質 - 對於任意一個環，環上最大的邊一定不會是MST的邊(弱的環定理) - 如果有一棵生成樹T，加上任何一條未使用在T裡的邊。都能保證這條邊是環裡最大的話。則 T 是 MST(強的環定理) - 如果把一棵MST分成兩個連通塊 T1,T2。連接 T1,T2 的邊必須是兩聯通塊之間最小的 --- ### 先輩知識2: 線段樹 問題: 給你一個 i，要怎麼找出 j 使得 $D|i-j| + A_i + A_j$ 最小? - 分析1: - 當 $i \ge j$ 時，上式 = $Di + A_i - Dj + A_j$ - 當 $i \le j$ 時，上式 = $-Di + A_i + Dj + A_j$ - 假設 $v1[i]=Di+A_i$， $v2[i]=-Di+A_i$ - 對左邊的j，查詢 v2[j] 最小，邊權=v1[i]+v2[j] - 對右邊的j，查詢 v1[j] 最小，邊權=v2[i]+v1[j] - 可以用一棵線段樹來做 RMQ，每次查詢 O(log n) --- ### 做法1: 銀腦減邊法 - 性質: 假設 i 的 A_i 最大，則 i 只需要往左、右個連一條最小的邊就好 - 證明: 下一頁 演算法: 每次挑一個最大的 A_i，往左右個連一條最小的邊。接著把 Ai 刪掉，再找第次大的重複上面動作 只會加 2n 條邊而已，接著對這 2n 條邊做一次 kruskal 就好 --- ### 證明 - 假設 i 的右邊最小邊為連到 j，另外一條野生的非最小邊 k - dis(i,j) < dis(i,k): 我們假設的 - 接著只要證明 dis(j,k) < dis(i,k)，就能證明 (i,k) 是不需要的邊(因為是 i,j,k 形成環中最大的) - 若 i < j < k - $A_j + A_k < A_i + A_k$, 因為 $A_i$ 是假設 A 最大的點 - |j-k| < |i-k| (|i-k| = |i-j| + |j-k|) - 由上面兩個得證，dis(j,k) < dis(i,k) - 若 i < k < j - 把 dis(i,k) > dis(i,j) 展開，可得: $A_k + Dk > A_j + Dj$ => $A_k - A_j + Dk - Dj > 0$ - dis(i,k) - dis(k,j) 展開，可得 $A_k - A_j + Dk - Dj$ - 根據上面，得知 dis(i,k) - dis(k,j) > 0 --- ### 做法2: Borůvka's algorithm 算法: - 一開始假設各個點都是一個獨立聯通塊 - while(連通塊個數) > 1，重複以下動作 - 對於每個連通塊，找一條連到其他連通塊最小的邊 - 如果加上這條邊不會形成環，加他，else ignore --- 性質: - 為什麼他是對的? - 因為prim是對的，上面算法很像「平行一口氣做很多個prim」 - 複雜度? - while(連通塊個數) > 1 這個迴圈只會進 O(log n) 次 - 因為每進一次，連通塊個數至少減半 - 迴圈裡面 O(m)，所以複雜度 O(m log n) --- ### Borůvka 與這題的關係 前面的線段樹告訴我們，在 `while(連通塊個數)` 的迴圈裡，我們大概可以花個 O(n log n) 或者 O(n) 的時間找到每個連通塊向外連最小的邊 複雜度 O(n log^2 n) or O(n log n) --- ### 做法3: 樹分治 [link1(p165以後)](https://img.atcoder.jp/cf17-final/editorial.pdf) [link2(日文)](http://drken1215.hatenablog.com/entry/2019/01/15/081500) 想法和 Borůvka 差不多 --- ### 做法4: --- ### 為什麼會有這一題? 簡答: 教育意義重大，可以看出很多最小生成樹的有趣性質。有興趣的話建議每個做法都寫一次，可以多了解很多事情 啟示錄，一般來講這種題目的性質: - 有 n^2 條邊，而且 n 很大 - 對於每個點，可以快速求出與他相連最小的邊 - 例如這題就是用線段樹處理 滿足上面條件的圖，應該(?)都可以用上面的幾種作法處理 --- ### 例題 - [Connecting Cities(keyence 2019)](https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e) - [Interval and MST(dowango 5th final)](https://atcoder.jp/contests/dwacon5th-final/tasks/dwacon5th_final_c) - [Tree MST(codefes 2017 final)](https://atcoder.jp/contests/cf17-final/tasks/cf17_final_j)