2019 ISSC 部分題目講評
===
###### tags: `ISSC 2019` `Programming Contest`

FGH三題的[資料在此可下載](https://drive.google.com/open?id=1y8vvNBQ-LxB5pKhpeg55caQJ_zOxIp6E)，內含測試資料與範例程式，主要由盛宇航同學協助完成這次的命題，而也感謝呂爾軒同學協助檢驗題目。

## Problem F: Fortune

先重點觀察：如果 Frank 已經在某些城市開了 F-store ，則不管之前開店的順序，接下來最好的作法都是一樣的，我們可以把已經開店的城市作為標記來描述子問題，而要解的子問題則是接下來能賺到多少瘋狂消費者的錢。要解的子問題總數量頂多就是所有城市的子集合，共 $2^n$ 個。而第一個開店的城市總共有 $n$ 個可選，因此只要檢查其中 $n$ 個子問題的答案即可。

針對一個子問題，如果已經所有的城市都開店了，那麼就賺不到瘋狂消費者的錢了，此時子問題答案為0。反之，可以賺到的錢會是嘗試過所有可以開店的位置，以「開完該間店馬上可以賺到的錢加上未來可以賺到的錢」之中最大的為最佳策略，據此算出子問題的答案。

利用 Bit set 的概念搭配 Dynamic programming 來實現 $O(n2^n)$ 的實作複雜度。

private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}

fun DP(n: Int, ans: IntArray, adj: IntArray, state: Int): Int {
    if (ans[state] >= 0) return ans[state]
    val cand = (0..(n-1)).filter{(state and (1 shl it))!=0}
                         .map{adj[it]}
                         .reduce{x, y -> x or y} and state.inv()
    var ret = (0..(n-1)).filter{0 != ((1 shl it) and cand)}
                        .map{DP(n, ans, adj, state or (1 shl it))}
                        .max() ?: 0
    ans[state] = ret + java.lang.Integer.bitCount(cand)
    return ans[state]
}

fun main() {
    val n = nextInt()
    val adj = IntArray(n)
    (2..n).forEach {
        val (u,v) = nextInts().map{it-1}
        adj[u] = adj[u] or (1 shl v)
        adj[v] = adj[v] or (1 shl u)
    }
    var ans = IntArray(1 shl n){-1}
    for (v in 0..(n-1)) DP(n, ans, adj, (1 shl v)) 
    println("${(0..(n-1)).map{ans[1 shl it]}.max()}")
}

### Problem G: Grid Park

令 $L$ 為題目中正方形區域的邊長。本題可以透過 Prefix sums 來解 Range sums，達到 $O(L^3)$ 的時間複雜度，而透過 Fast Fourier Transform (快速傅立葉轉換) 可以做到 $O(L^2\log L)$，但在題目輸入資料的規模與時間限制上並不會比較快。
(細節有空再補)

### Problem H: Herbal Tea

依據輸入資料建立一張左右各有 $n$ 個點的二分圖：如客人 $i$ 喜歡 $p_i$ 跟 $q_i$ ，則把左邊的 $p_i$ 與右邊的 $q_i$ 建一條邊，還有右邊的 $p_i$ 與左邊的 $q_i$ 建一條邊。對這張圖做 Maximum matching 最大匹配，把結果除以二就是本題答案。複雜度：$O(m\sqrt{n})$ (使用 Hopcroft-Karp 時)。
(細節有空再補)