這次是第二次參加 CodeChef Starters
我覺得還蠻有趣的
這次六題裡寫出了五題
排在 div2 的第二
這場比完就到六星 2302
似乎有些比較簡單比賽的就不能比了
https://i.imgur.com/6nOAwem.png
今天嘗試不用他那個慢的要死的線上IDE
改在本地寫+測試後再複製貼上
體驗整個就好很多
P1 CONCATPAL
https://www.codechef.com/problems/CONCATPAL
因為可以隨便排順序
所以只需要看各個字母的出現次數
能成功若且唯若長的和短的抵消後
每個字母出現次數 >= 0
且出現次數是奇數的字母數 <= 1
（可以當中心點）
P2 THREENUMBERS
https://www.codechef.com/problems/THREENUMBERS
目標是要讓三個數都一樣
把兩個數加一且另一數減一
其實就等價於把一個數減二
答案就是與最小值的距離總和除二
P3 KPAL
https://www.codechef.com/problems/KPAL
這題是 corner cases 題，分成
1. N = K (直接看 A 是不是回文)
2. N 是奇數 (一定成功)
3. N 是偶數，K 是奇數（一定成功）
4. N, K 都是偶數（看兩個半邊奇偶性是否一致）
P4 SORTXOR
https://www.codechef.com/problems/SORTXOR
從這題開始有挑戰一點
可以用三次 xor 交換兩個值
但如果只用到兩兩交換的話
會超出 3N/2 的限制（最多需要 3(N - 1) 次操作）
不過經過在紙上一陣亂試
會發現對於 permutation 的一個長度是 k 的 cycle
實際上只需要 k + 1 次操作
像是 (1 3 4) 這個 cycle
只需要作出
1: [1 3 4]
3: [1 3 4]
4: [1 3 4]
1: [1 3 4]
就可以直接排好位置
因為長度是 1 的 cycle 不用做事
所以最多就是 3/2 倍，剛好就是他的限制
記得把一開始的值轉成 ranking 形式的 permutation 即可
P5 SORTSTR
https://www.codechef.com/problems/SORTSTR
這題我蠻喜歡的，因為題目簡潔但最後的結果又出乎我意料
對於一個字串，如果相鄰的兩個字元的值也是相鄰的就可以交換
例如 aabbd 中的 ab 交界可以互換，但 bd 交界不行
要找出能形成的字典序最小的字串
假如某個字元是 k
一個很重要的觀察是這個位置不可能 >= k + 2 也不能 <= k - 2
例如想要變成 k - 2，首先必須變成 k - 1
但 (k, k-1) 交換後變成 (k-1, k) 後
就又變成需要把後面的 k 變成 k-2 才能讓前面的 k-1 變小
所以不可能達成
要字典序最小，可以 greedy 的讓第一個最小
假如第一個字元是 k
根據剛才的觀察，我們只有機會讓他變 k-1
所以只有不斷的進 k 或是 k-2 才有機會一路交換上來變成 k-1
維護一個 queue 就會變成像下面這樣只由 k 及 k-2 組成