2015年1月31日 星期六

Codeforces Round #289 (Div. 2) (pA ~ pC)

這場比賽同時也是俄羅斯某個營隊的資格賽,採 ICPC 制,就我看來 pC~pF 難度沒有太大差別。

Problem A --- Maximum in Table

題意:有一個 $n \times n$ 表格 $a$,第一行和第一列所有格子都是 $1$,而其它的格子都滿足 $a_{i,j} = a_{i-1,j} + a_{i,j-1}$ ,求此張表格內最大的數。

數據範圍:$1 \le n \le 10$

tag:[ dp ] [ 數學 ]


就是個希望所有人都 AC 的題目,由於 $n$ 很小,直接從左到又再從上到下 dp 就行了,你只要這麼做之後再從表格中找最大的數就可以 AC。

但你可以再進一步的推論出

1. 表格中最大的數一定在右下角 (why?)

2. 表格中每個數會對應到巴斯卡三角形的某一個數。(想想看 $a_{i,j}$ 會對應到 $C^?_?$?)

所以實際上題目變成 $n$ 若高達 $1,000,000$ 並求最大的數 mod $1,000,000,007$ 也是可解的。

Problem B --- Painting Pebbles

題意:有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 顆石子,你有 $k$ 種不同顏色的油漆,要把所有石子都塗上顏色,使得同一種顏色的石子個數在不同堆裡至多差 $1$。若有辦法塗就給出一種塗法。否則輸出 NO 即可。(可以有顏色在某堆個數為 $0$)

數據範圍:$1 \le n, t \le 100$,$1 \le a_i \le 100$

tag:[ greedy ]

乍看之下可能會不知道從何想起,這種時候我們就從簡單的 case 想起吧!怎樣叫做簡單的 case ?例如說,當只有一堆的時候,但在這題只有一堆的結論太顯然了 XD,所以我們從兩堆開始考慮。我們會發現,當兩堆的個數差不超過 $k$ 時總是可以構造出解 (how?),並且你可以推出不等式 $\sum_1^k{b_{1,c}} - \sum_1^k{b_{2,c}} \le k$,於是當 $n$ 為 $2$ 時我們會做了!

接著考慮有 $n$ 堆的情形,不難想像結論就是最大堆的個數和最小堆的個數不超過 $k$,至於怎麼構造呢~就留給大家自己想吧~
我的構造法:(以下反白) 設最小堆的石子個數為 $mi$,則每堆石子都先塗上 $mi$ 個第一種顏色,之後若某堆石子數還有 $s$ 顆石子尚未塗色,就分別塗上第 $1$ 至第 $s$ 種顏色。

Problem C --- Sum of Digits

題意:有一個數列 $a$ 含 $n$ 個數,且為嚴格遞增,已知第 $i$ 個數所有位數總和為 $b_i$,求最小的可能 $a_i$ 值。

數據範圍:$1 \le n \le 300$,$1 \le b_i \le 300$

tag: [greedy] [進位]

這題雖然是 pC,主要的 idea也不難,但我卻最後寫它,因為我覺得他很容易寫出 bug (事後看 scoreboard確實如此)。

首先會發現我們一直貪心的構造 $a_i$,構造的方法為令 $a_i$ 為大於 $a_{i-1}$ 且總合為 $b_i$ 的最小的數 (可以假設 $a_0 = 0$),如此一來一定能使 $a_n$是所有可能中最小的。

所以此問題可以藉由解 "求大於 $x$ 且位數和為 $y$ 的最小的數(問題1)" n 次得到。

若第一次接觸到這類問題可能會覺得並不簡單。我們先想想一個比較簡單的問題:

請求出位數和為 $y$ 的最小的正整數。

這應該不太困難,貪心地從位數低到高一直都填 $9$,直到總和快要超過 $y$ 時改成填 $y mod 9$。

會做這個問題後再回來解問題1,我們枚舉 $x$ 有變動的最高位數,有變動的最高位當然位置愈小愈好,接著我們再枚舉該位要變成哪個數字,例如說若該位是 '7' ,那就只能變成 '8' 或 '9'。枚舉完後,由於我們已經確定 $x$ 已經變大了,剩下的比較低的位數就貪心的填最小的數即可。但若就算全填 '9' 也無法使得總合為 $y$,則繼續枚舉下一個。

看到這裡或許你已經知道怎麼做了,但實作過程還是可能有很多大大小小 bug,請自己多家小心吧Orz

最後我想再考考大家一個問題:在這樣的數據範圍下,答案最多可能會有幾位呢~?
(我想有些人的 bug 是因為這樣產生的,翻了幾份 code 也確實有這樣的 bug)