[B] AGC VP 記錄

AtCoder Grand Contest 049

AT_agc049_e [AGC049E] Increment Decrement

AtCoder Grand Contest 052

約 1h 切 A，之后都不會了。

A - Long Common Subsequence

先從左到右放 \(n\) 個 \(0\)，\(n\) 個 \(1\)。發現 \(S+S\) 這種形式，先匹配前 \(n\) 個 \(0\)，再匹配接著的 \(n\) 個 \(1\)，則最后一定會留出至少一個 \(0\)。證明：

1. 若 \(S_n=0\)，則 \((S+S)_{2n}=0\)。
2. 若 \(S_n=1\)，設在 \(S+S\) 的前一個 \(S\) 中用了 \(x\) 個 \(1\)，則最后 \(x\) 個 \(1\) 未被使用，倒數第 \(x\) 個 \(1\) 前面那位必定是 \(0\)，否則在前一半中會用 \(\geq x+1\) 個 \(1\)。

B - Tree Edges XOR

邊權轉點權。我們令邊權為兩點點權異或和，那么用距離（邊權異或和）作為點權很合適。

建一個虛點 \(u\) 連向任意一點 \(v\)，邊權為 \(0\)，這條邊受影響但不操作這條邊，設 \(f(w)=dis(u,w)\) 表示 \(u\to w\) 的邊權異或和（\(w\) 的點權），考察一次操作 \((x,y)\) 對 \(\forall w,dis(u,w)\) 的影響：發現僅僅交換了 \(dis(u,x),dis(u,y)\)！

考慮如何到達最終狀態。設 \(g(w)\) 表示 \(w\) 到 \(v\) 的邊權異或和，那么一個點權序列是最終狀態等價于：

由于 \(n\) 是奇數，可以把 \(n\) 條等式異或到一起，解出 \(f'(v)=\bigoplus_{1\leq w\leq n}f(w)\oplus\bigoplus_{1\leq w\leq n}g(w)\)（必要條件）。由于是交換，下一個必要條件為可重集 \(\{f(w)\mid w\in[1,n]\},\{g(w)\oplus f'(v)\mid w\in[1,n]\}\) 相同。\(g(v)=0\) 保證了充分性。

C - Nondivisible Prefix Sums

先找合法的充要條件。若總和為 \(P\) 的倍數則不合法，否則：

若出現了一堆 \(1\)，則需要使前綴和“跳過”\(P\) 的倍數，設序列中 \(\neq 1\) 的數為 \(B_1,\ldots,B_k\)，則要求 \(cnt_1\leq P-1+\sum_{i=1}^k(P-B_i)\)。

如何刻畫“出現很多”？考慮 \(1\) 為眾數時。若 \(1\) 不為眾數，設眾數為 \(x\)，則我們給序列中所有數都乘 \(x^{-1}\pmod P\)，\(\sum\equiv0\pmod P\Longleftarrow x^{-1}\cdot\sum\equiv0\pmod P\)（同余的可除性）。這樣就只用考慮眾數為 \(1\) 的情況。

猜測該條件充分，進行構造性證明（由于 \(1\) 是眾數，我們就大量使用 \(1\)）：

策略：設填了的數的最小眾數為 \(x\)，和為 \(s\)。若 \(s+x\not\equiv0\pmod P\)，則填 \(x\)，否則填任意 \(\neq x\) 的 \(y\)，再填 \(x\)。不會了，咕咕咕。

AtCoder Grand Contest 054（未打）

AT_agc054_d [AGC054D] (ox)

限制：將 ( 視作 \(+1\)、) 視作 \(-1\)，保證可重排為合法括號串，則 \(\sum=0\) 的限制已被滿足，現在只需滿足每個前綴和都 \(\geq0\)。相當于在放 )、x 之前前綴和 \(\geq1\)，對于 \(x\) 來說可以認為是被 () 包含。

同種字符相對順序不變，直接對 \(4\) 種字符的序列的歸并 DP，每個元素是其在原序列上的位置，則相鄰交換得到新序列的最小代價為逆序對數。但復雜度無法接受。

考慮分成若干部分，貪心地確定內部順序再歸并到一起。先只看括號形成的子序列，用最小步數使之合法，貪心策略是從左到右處理，在 ) 左邊無 ( 與之匹配時把右邊第一個 ( 交換到其左邊，最優性證明可以找下界再說明構造取到了下界：每個 ) 左邊缺的 ( 個數之和 \(\sum_{c_i=)}[s_i<0]|s_i|\)（需要和這個右括號交換 \(|s_i|\) 次），這樣一定能取到下界（每次交換使“勢能”\(-1\)）。之后要讓 () 包含每個 x，移動括號可以處理多個 x，一定不劣于移動 x，故 o 與 x 間不發生交換；且發現這個過程中不改變已經排好的括號序列。

于是可以歸并 (,) 調整后合法的括號序列和 o,x 形成的子序列，注意調整時忽視 o,x，(,) 的位置要寫調整前的位置。設 \(f_{i,j}\) 表示兩個序列分別用了前 \(i\) 個和前 \(j\) 個，預處理逆序對數來輔助轉移即可。

AT_agc054_e [AGC054E] ZigZag Break

先判定再計數。考慮一些特殊情況（充分條件），再說明必要性。

首先有 \(p_1<p_n,p_1>p_n\) 兩種情況，由于值域翻轉（\(p_i\leftarrow n-p_i+1\)）不改變刪除條件，后者的合法情況與值域翻轉后的合法情況構成雙射，那么只需統計 \(p_1<p_n\) 時 \(p_1=A,p_1=n-A+1\) 的合法情況之和即可。

考察最終狀態：剩下的兩個數一定是 \(p_1,p_n\)。先考慮簡單的策略：對 \((l,r)\ (p_l<p_r)\) 能刪就刪，那么剩下的子序列單調遞增；對稱地，若 \(p_l>p_r\) 則單調遞減。利用它來簡化構造，我們在中間搞一個“波折”，兩邊分別刪得單調，發現充分條件：\(\exists i\in[1,n-1],p_i\leq p_1<p_n\leq p_{i+1}\ (n\geq2)\)。

歸納證明必要性。\(n=2\) 時顯然充要。\(n\geq3\) 的合法狀態需要轉移到 \(n\) 更小的合法狀態，而更小的合法狀態存在合法的 \(i\)。若當前狀態無合法的 \(i\)，則合法的 \(i\) 一定由兩個數 \(l,r\) 刪除中間的所有數拼出來，那考慮中間刪的最后一個數 \(p_k\)，它一定 \(>p_r\) 或 \(<p_l\)，對兩種情況分別考慮 \(r\leftarrow k\) 與 \(l\leftarrow k\) 的子問題，最終一定會到 \(r=l+1\) 的情況，與當前狀態不存在合法的 \(i\) 相矛盾。

這個“存在”不好計數，正難則反，單步容斥為“不存在”，答案即為 \((n-1)!-f(A)-f(n-A+1)\)，\(f(x)\) 表示 \(p_1=x,p_1<p_n,\nexists i\in[1,n-1],p_i\leq p_1,p_{i+1}\geq p_n\)。先填 \([p_1+1,p_n-1]\)，再填 \([1,p_1]\)，最后填 \([p_n,n]\)。\(f(n)=f(n-1)=0\)，對于 \(x\in[1,n-2]\) 計算 \(f(x)\)：枚舉中間段的長度 \(k\)，則有 \(p_1=x,p_n=x+k+1\)，那么：

寫成組合數后，用組合數學基本功化簡即可。但我基本功不扎實嗚嗚嗚。

總結：這題無論是構造雙射還是找簡單策略都是在構造限制，方便我們尋找充分條件與證明必要性。

AtCoder Grand Contest 055（未打）

AT_agc055_b [AGC055B] ABC Supremacy

類似“奇數位反轉”的轉化：令 \(a_i\leftarrow(a_i-i)\bmod3\)，那么操作等價于將連續 \(3\) 個相同的字符另一種顏色。

由于操作可逆，判斷可達性只需將 \(S,T\) 操作至其所在連通塊的代表元。

手玩一下，發現進行操作不改變 原先沒有連成 \(3\) 點同色的點 的顏色，而是移動其位置，之后可能拼成新的連續三點同色。我們遇到連續三點同色就把它挪到最后（\(AAAX\to XXXX\to XAAA\)），并變成 \(AAA\)，這相當于刪除這個字符，用棧模擬操作直到不能繼續。稱這樣得到的串為“代表元”，發現代表元間互不可達，于是同一連通塊只能到達同一個代表元，保證了正確性。

AT_agc055_d [AGC055D] ABC Ultimatum

暑假 smb 學長講過，當時寫了筆記。

AT_agc055_e [AGC055E] Set Merging

外星人轉化說是，先咕了。

AT_agc055_f [AGC055F] Creative Splitting

先考慮 \(b\) 好的充要條件，倒序貪心將數一個個分配給子序列，限制單調從松到嚴（若正序，則子序列長度的限制會卡掉單調性），所以找到最嚴卻能放的子序列來放。

這個過程太抽象，考慮具象化。我們將 \(n\) 個子序列的長度畫成柱形圖，則限制每列的高度 \(\leq k\)，添加 \(b_i\) 時找到格子圖的從上往下第 \(b_i\) 行，找到這一行為空的柱子中，高度最小的那個，落到它的頂部。不妨對柱子從左到右從小到大排序，則相當于把一個方塊從第 \(b_i\) 行的最左邊開始往右移，直到被柱子或右邊界擋住，之后讓它落在它所停留的那一列。顯然好的 \(b\) 要保證 \(\forall i,b_i\in[1,k]\)，在此前提下，不存在 \(b_i\) 被第一列擋住就是 \(b\) 好的充要條件。

這個“撞”不好刻畫，在格子圖上有橫豎兩種視角，我們橫著看。共 \(k\) 行，每行長度 \(\in[0,n]\)，自上而下每一行長度單調不降、方塊往右堆，這個“撞”+“落”相當于給第 \(b_i\) 行添加 \(1\) 個方塊，再按行的長度重新排序。

先想沒有 \(b_{pos}=val\) 時怎么做。此時可以任意選擇 \(b_i\)（每次任選一行），所以排序是假的，一共 \(nk\) 個數就是要填滿，方案數即為 \({nk\choose n,n,\ldots,n}={(nk)!\over(n!)^k}\)。再推廣至 \(b_{pos}=val\) 時，發現 \(b_{[pos+1,nk]}\) 與 \(b_{[1,pos-1]}\) 都無視排序，只需得到 \(pos\) 這一步操作的是哪一行即可。假裝枚舉（固定）排序后行的長度 \(0\leq q_1\leq q_2\leq\ldots\leq q_k\leq n,\sum_{i=1}^kq_i=nk-pos,q_{val}<n\)。那么方案數就是先確定每個集合對應哪個值，再對 \(b_{[pos+1,nk]}\) 和 \(b_{[1,pos-1]}\) 的操作分別計數，三者獨立，相乘：

寫成階乘形式后，分子是 \(pos\) 和常數，而與 \(pos\) 相關的限制也只有 \(\sum_{i=1}^kq_i=nk-pos\)，故可以僅枚舉 \(val\) 來 DP。為計算第一個多項式系數，我們按數值從小到大一類類填 \(q_i\)（狀態里做個前綴和優化），轉移時枚舉當前數值填幾個，那么貢獻系數就可以計算了，而為了滿足限制還需要記錄共填了幾個 \(q_i\)、\(\sum q_i\)。于是狀態數為 \(O(n^2k^2)\)，一輪 DP 的時間復雜度為 \(O(n^2k^3)\)，而要枚舉每個 \(val\) 進行 DP，故 DP 的總時間復雜度為 \(O(n^2k^4)\)。計算答案的時間復雜度為 \(O(nk^2)\)，故總時間復雜度為 \(O(n^2k^4)\)（忽略階乘、階乘逆元、階乘逆元的冪的預處理）。

（我偷懶寫的快速冪，還寫在了最內層循環，多一只 \(\log\)。）

注意事項：

1. 階乘等要處理夠。
2. \(q_i\) 的范圍為 \([0,n]\) 而非 \([1,n]\)，DP 時不要搞錯了。

AtCoder Grand Contest 057

AtCoder Grand Contest 061