# AtCoder Beginner Contest 415
Unofficial Editorial
~~為了減少製作成本~~，以下不會幫你翻譯題目，也不會有實作的 code (因為我覺得要自己想過然後用自己的方式實做出來比較好，不要直接抄)。
如果想看 code ，可以去 submission 找，應該有更多實作比我好看的。
尤其是線段樹，我線段樹寫得超級醜。

### A
(●'◡'●)
### B
( ≧ ∇ ≦ )
### C
:::spoiler 觀察 1
是不是長得很像 ||bitmask DP|| ?
:::
:::spoiler 實作
令 $dp[S]$ 表示有沒有辦法合成出狀態為 $S$ 的化學藥品，若 $S$ 本身就是危險的，那 $dp[S]$ 就是 `false`，否則就枚舉所有包含在 $S$ 裡面的化學藥品 $i$，如果存在任一個 $S \space xor \space (1<<i)$ 可以被合成出來，代表 $S$ 也可以被合成出來。
:::
:::spoiler 我討厭 DP
也可以用 BFS，若 $S$ 可以被合成出來，就把它丟到一個 `queue` 裡面；每次從 `queue` 裡面拿出一個狀態 $S$ ，再將 $S$ 加上某個不在 $S$ 裡面的藥品 $i$ (也就是把 $S \space and \space (1<<i)$ 丟進 `queue`)，重複這個動作。
這其實就是剛剛那個 DP 反著做而已嘛 ( ≧ ∇ ≦ )ﾉ
:::
:::spoiler 複雜度
$O(NlogN)$
$N$ 是藥品數量
:::
### D
:::spoiler 觀察 1
每兌換一次就可以拿到一個貼紙，所以兌換次數越多越好，因此手上的瓶子數量 ||越多越好||。
假設可以拿 $A_i$ 個瓶子換 $B_i$ 個瓶子，令 $D_i$ 為減少的瓶子數量，那麼要盡可能使用 $D_i$ 較小的兌換方法。
:::
:::spoiler 實作
用 `sort` 將所有兌換方法依照 $\left\{ D_i, \space A_i \right\}$ 由小到大排，就能盡可能使用 $D_i$ 最小的方法直到剩餘的瓶子比 $A_i$ 少。
:::
:::spoiler 複雜度
$O(MlogM)$
:::
### E
:::spoiler 觀察 1
若 Takahashi 在起點時有 $X$ 個錢不會死掉，那他有 $X+1$ 個錢也不會死掉。
若 Takahashi 在起點時有 $Y$ 個錢會死掉，那他有 $Y-1$ 個錢也會死掉。
因為有單調性 (在某個數量以前會死掉，之後都不會死掉)，可以 ||二分搜||。
:::
:::spoiler 觀察 2
要怎麼知道有 $X$ 個錢會不會死掉 ?
考慮 DP，令 $dp[i][j]$ 為 Takahashi 在 $(i, \space j)$ 時最多可以擁有多少錢，如果 $dp[n][m]<0$ 代表 Takahashi 會死掉。

:::spoiler how to 轉移
$dp[i][j]=a[i][j]+max( dp[i-1][j], \space dp[i][j-1] )$ 再扣掉該天的花費
記得判掉錢為負數的狀態
:::
:::spoiler 複雜度
$O(NMlogC)$
$C$ 是二分搜的範圍
:::
### F
:::spoiler 觀察 1
單點改值區間詢問...
可不可以演奏 ||線段樹||？
:::
:::spoiler 觀察 2
線段樹的節點要維護那些訊息？
首先可以用 `ans` 表示該節點範圍內的 max combo
再用 `head` 和 `tail` 表示該節點範圍內從最前面開始往後看最長的 combo 和從最後面開始往前看最長的 combo ，合併的時候就 ||如果左子樹最後一個字元和右子樹第一個字元一樣，就可以把左子樹的 `tail` 加上右子樹的 `head` 然後更新 `ans`||。
至於中間的 combo 都不用管它，因為它們在之前合併上來的時候已經被算過了，它們在合併時也不會對答案有更多貢獻。
可以參考下圖或下面的實作。
:::
:::spoiler 實作
注意線段樹是左閉右開，0-indexed

void comp( int idx, int ls, int rs, int mid ){
    st[idx].head=st[ls].head;
    if( st[ls].head==st[ls].r-st[ls].l && s[mid-1]==s[mid] ) st[idx].head+=st[rs].head;
    st[idx].tail=st[rs].tail;
    if( st[rs].tail==st[rs].r-st[rs].l && s[mid-1]==s[mid] ) st[idx].tail+=st[ls].tail;
    st[idx].ans=max( st[ls].ans, st[rs].ans );
    if( s[mid-1]==s[mid] ) st[idx].ans=max( st[idx].ans, st[ls].tail+st[rs].head );
}

:::
:::spoiler 複雜度
$O(NlogN)$
:::