話說幾經辛苦把這場的solution都看完再把題目都AC之後
發現這場真的遺憾 還記得只要我做到 C-Small 就能Advance了
而C-Small (甚至C-Large) 在看完solution後驚覺是很易的...是應該能做到的
這兒學習到一件事, 要正視自己一直以來其中一個思考的弱點..下面再說
至於B-Large 是絕對不可惜, 甚至我也是在昨天才勉強明白solution的方法
只能說我的Probability / Expected Value學得太差了...
總結來說, 這場比1B學得更多, Ad-hoc度雖然也很高, 但仍然是有學習的地方
即場時我AC了 整題的A跟B-Small, 其它都是事後再AC的
玩了3場的GCJ Round 1, 我認為心理跟策略上也是有改善的空間
Google Code Jam 2015 Round 1C
A: (Ad-hoc, Greedy)
這題是我唯一能整題過的題目...
就結果來說, 其實Small的思路跟Large的是完全一樣
但即場由於策略問題, 完全沒多加思考Large 就跑去看B跟C了...
弄得同一樣的Code, 卻過了一小時才交A-Large...
題目本身很易嗎? 也不算, 也不是難...是很伏
很明顯很容易想少一些Case的類型
題目是這樣的:
給了一個R*C的Grid, 你跟你弟弟要玩一個遊戲.
你弟弟會放一隻 1*x (打橫長x格) 的船在任意位置
你要做的就是猜船的位置, 並且把他打沉 (你看不到船的位置)
打沉的方法是: 把船的 x 格佔有位置都說出來
問題是你知道弟弟會出cheat, 他可以任意移動船的位置,
只要跟你所知道的情報沒有矛盾就可以了
例如: 你說了某一格的位置, 弟弟可以先把船移動, 然後跟你說"沒有中"
當然, 當某一格他說了沒有中 (或中了) 之後, 那一個的狀態就不能再改變了
不然就跟你所知的情報有矛盾了
問題問, 你先走, 在知道弟弟會盡可能地出cheat的情況下, 你最少要用多少步才能勝出?
Small Case是Large的引導版, 是只有一個Row的 (R*C, R = 1)
我是先把想法大概猜到了, 才開始做個簡單的證明的
思路大約是: 由於最少都要用X做答案, 每次弟弟出Cheat會把答案的次數增大1
所以盡量減少他可以出Cheat的次數...對這個是可以控制到的, 因為他不能與我所得的情報相矛盾
怎樣可以限制弟弟出Cheat的次數呢? 不難聯想到跟Greedy有點關係
"盡可能"選擇某些位置使他不能出很多次Cheat這樣
答案就是: 由左至右, 每次選第 x 格
如果弟弟說了"中"的話, 基本最多再選 x 次就完結了 (為什麼不是x - 1次是伏位, 下面再說)
但弟弟這樣說沒好處, 如果他還能出Cheat的話
但他要再出Cheat, 就只能把船向右移了 (如果本身是選中了的話)
那麼我就再一次選向右的第x格...如此類推
那麼弟弟已經走投無路, 所有左邊的位置都比我"封鎖"了
他被迫要說"中了"
那麼我們就限定了那一格是船的某一部分
但伏位是...很自然會以為那格是船的 "最右點"
但這未必是真的, 要是 C 本身不能被X整除, 那麼其實右邊還有空間再移動
只是不夠整架船移動 (再出Cheat)
所以要是你用x - 2 步把船的 x - 2格都猜中了
第 x - 1 步, 弟弟永遠都可以說你錯了, 他可以出最後一次Cheat把船向相反方向移動一格
浪費你多一步 所以要是 C本身不能被 X 整除的話, 答案還要另外 + 1
這基本就是Small的答案了
而Large呢, 首先發現, 每一Row都是獨立的, 可以分開來看
Greedy地選也完全沒問題
所以就把這個策略重複 R-1 次, 最後一個Row就當是Small一樣的做法就好了...
策略上...我應該先花幾花鐘想想Small是否能改一下就能交Large的...
這題根本不用花一小時再交...
#include<bits/stdc++.h>
#define LL long long
#define PI acos(-1)
#define x first
#define y second
#define PII pair<int,int>
#define F(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define feq(x,y) (fabs((x)-(y)) <= eps)
#define flt(x,y) ((x)+eps < (y))
#define fle(x,y) ((x)+eps <= (y))
#define fgt(x,y) ((x) > (y)+eps)
#define fge(x,y) ((x) >= (y)+eps)
using namespace std;
int T,n,r,c,w,ans;
int main(){
scanf("%d", &T);
for(int qwe=1; qwe<=T;qwe++){
scanf("%d%d%d", &r,&c,&w);
ans = (r-1)*(c/w);
ans += (c - w)/w + w + (c%w != 0);
printf("Case #%d: %d\n", qwe, ans);
}
return 0;
}
B: (String, Probability, Expected Value)
這題是這一Round最難的了 (如果考慮Large的話)
這題有我最苦手的Probability / Expected Value的問題...
幸好結果來說我有學到東西了...
題目有點複雜就不說了 直接說分析
Small是很簡單的Brute Force, 隨便寫Backtrack都可以
Large就需要數學技巧了...
首先題目有點賤
題目要找的是: Expected Number Of Banana Left
首先我來說一下我對Expected Number 的理解:
很白痴, 我只懂最簡單的definition: Weighted Average of Possible Result
也就是 E(X) = P(a)*v(a) + P(b) * v(v) + ...
where P() 跟 v() 是 probability 跟 Value of 所有Possible outcomes
where P() 跟 v() 是 probability 跟 Value of 所有Possible outcomes
然後因為之前某場CF, 我也得知了一個經常會用到的Property叫
Linearity of Expectation
Linearity of Expectation
這個是這條題目的重點, 是很方便很強大的Property, 可惜我對他的理解等於零
在CF上面厚顏地開了Post求問, 有人給了一些很好的Reference, 看了之後才開始有點理解
http://codeforces.com/blog/entry/18025#comment-228851
http://codeforces.com/blog/entry/18025#comment-228851
這個Property, 引用Wiki的說法:
![\operatorname{E}[a X + b Y + c] = a \operatorname{E}[X] + b \operatorname{E}[Y] + c\,](http://upload.wikimedia.org/math/f/c/e/fce3165addbee8064fefd39136b38947.png)
即使 X , Y 是 dependent 的Random Variable!!
先不詳細說這個東西, 回到題目上面
設 C為你會準備的Maximum # of bananas,
那麼題目就是求 E(X) = E(C - X) = C - E(X) where X = expected # of bananas give out
那麼題目就分兩部分了: 找出C跟找出E(X)
先說找 C
首先跟KMP一樣, 要先找出Pattern 的"最長前後綴"
由於string很短, 不用failure function找也可以...直接substring()找就行了...
由於string很短, 不用failure function找也可以...直接substring()找就行了...
有了這個之後..就可以直接用String的長度 S
去算出所有可能性裡面包括最多Pattern的String究竟有多少個Pattern
去算出所有可能性裡面包括最多Pattern的String究竟有多少個Pattern
是為C
重點還是要在算E(X)上面吧
首先說一下不懂答案思路之前的想法:
跟上面說的一樣, 我只會最基本的Definition
所以很自然就會去想
E(X) = P(Exact 1 banana)*1 + P(Exact 2 bananas)*2 + ...
(詳情我CF那個Post有說, 可以自己去看)
但當然這樣算沒有好處, exact X banana這些event 明顯就不是independent的
無限double count, 也不知道怎用 (知道也不會用, 想也知難code) inclusion-exclusion principle
總之直感也知道不是這樣直接去數的, 用Counting之類的數法是不行的了
然後...答案竟然是很直接的...
設P 為 Pattern在某一個位置出現的機率, 這個易算, 直接用Product Rule乘起來就是了
然後重點是:
By Linearity Of Expectation, E(X) = P*(S-L+1) As there are (S-L+1) possible starting point for Pattern
這句是如何來的...!?
看了CF那個Post後...我終於有了以下的理解 (還不知道對不對, 最少我信了)
先說一下Random Variable
它們只是一些有不同值的Variable, 每個值都associate 一個probability, 當然加起來就是 1
視乎情況, 這些值可以自己define出來的, 最常見的就是 1 跟 0 (某些desire result就設1, with some probability P, otherwise 0 with (1-P))
由於他們是variable, 可以照樣自己設立一些equation
例如設 Z 為 # of bananas giving out, 我不知道Z 的所有Value跟它們的probability
但照樣可以寫一個equation
Z = A_1 + A_2 + A_3...
A_i 是 # of banana when pattern start at position n
A_i 是 # of banana when pattern start at position n
A_i 我們倒是知道的, 沒錯就是最常用的 {1 with some probability p, 0 otherwise}
這個 some probability p 就是solution中算的 P, 所有A_i 的 p 都是一樣的
現在不難發現A_i 互相也不是independent 的!
在某一個位置假設出現了pattern, 某些位置就不可能出現了...
這就是Linearity Of Expectation 發光的地方了!
即使 X , Y 是 dependent 的Random Variable!!
Z = A_1 + A_2 + A_3...
==>
E(Z) = E(A_1 + A_2 + ...) = E(A_1) + E(A_2) + ...
= P*1 + P*1 + ...
= P*(S-L+1)
嗚啊...即使不是Independent也還是可以直接這樣做, So 變態...
嗚啊...即使不是Independent也還是可以直接這樣做, So 變態...
這個技巧不用真的很熟悉Probability...也可以照學起來吧, 思路而已...
這題做不到真的不可惜, 因為回頭看根本不是能做到的東東
還有要知道: 不恥下問真的很重要, CF真的是很好的平台 :)
PS: 最後糾結的是...比較 P 跟 0的時候 不知道為什麼不能用eps, 不是應該要用才對嗎? 用了反而會錯, sample case都過不了...eps這個東東也是要認真面對一下了
#include<bits/stdc++.h>
using namespace std;
int T, L,S,K;
int alphabet[300];
string kb, pat;
int main(){
scanf("%d", &T);
for(int qwe=1; qwe <= T; qwe++){
scanf("%d%d%d", &K,&L,&S);
cin>>kb>>pat;
memset(alphabet,0,sizeof(alphabet));
for(int i=0; i<K; i++) alphabet[kb[i]]++;
// O = maximum overlap
int O = 0;
double maxBanana = 0, expectedBanana = 0, P_fixedPoint = 1;
for(int i=0; i<L;i++) P_fixedPoint *= (alphabet[pat[i]]*1.0/K);
if(P_fixedPoint > 0){
for(int i=1; i<L; i++) if(pat.substr(0,i) == pat.substr(L-i)) O = i;
maxBanana = 1.0 + (S-L)/(L-O);
expectedBanana = P_fixedPoint * (S-L+1);
}
printf("Case #%d: %.8f\n", qwe, maxBanana - expectedBanana);
}
return 0;
}
C: (Ad-hoc, Greedy)
這題真的太太太可惜了...回頭看真的應該要做到的..
題目是說:
給了 D 種錢幣, 每種錢幣可以用C個, 現在要你合出 [1, V] 所有的value
當然有機會合不了, 所以你可以額外增加某一些種類的錢幣, 當然它們也只能用C個
問最少要另外增加多少種類的錢幣?
這兒我的思路, 一下子就飛去 Coin Change的 Classic DP去了
這個就是我開首說的壞習慣...
由Day 1 開始玩比賽到現在, 我每次看到題目有一點點像我聽過的Classic Problem
就會往那方向去想, 以為是一些簡單變種還是什麼
就會往那方向去想, 以為是一些簡單變種還是什麼
但其實by experience, 很多時候都是錯的...
有時候, 根本不用想那麼複雜(像這題)
有時候, 有一點點像, 但其實差很多很多 (特別是Graph類的題目)
總之這樣的"聯想式"的思考好像不太有效呢...很多時把自己帶進死胡同
這題結果也是這樣的, 其實跟Coin Change沒有關係...(當然如果會的話會有幫助)
整道題目只考你一個發現:
能合到的value像一條條segment, 是有range的
例如你不增加種類, 可能合到 [1,5], [10,12]....
這樣的話 其實 "6" 是一定要增加的了, 因為用現在所有種類都合不出來,
也不可能用比6 大的種類合出來, 對吧?
這樣的話就是Greedy的想法了
我們想 maintain X, where X 是 最少的value such that [1,X] 都是你能合出來的
那麼X+1怎樣合出來呢?
可以試用 現在的種類(如果有還沒用的話)試試合不合到
不能的話只能增加合成種類
當X >= V 的時候 算法就完成了
When we add a new denomination X to S, the new set of values we could produce include each of the values we could produce with the existing set S plus between 0 and C of the new denomination X. If X is at most N+1, then this new set of values will be the set of all values from 0 to N+X*C, so we can update N to N+X*C.
由於只有D種現有錢幣, 而增加種類即使 X 變為 X+C*(X+1) = X(C+1) +C
C最少是 1 , 所以 X 最少是2倍2倍地增長, 直到 V, 最多就是O(lg V) 次
TOTAL = O(D + lg V) 的LOOP
這樣的分析..跟Facebook Hacker Cup 某題有點像, 也是不用嚴格地分析, 只要證明了
最少是2倍2倍地增加/減少, 就可以得出 O(lg X)的bound, 用來說服自己很有用
說起來, 這題的難度全部在於發現如何update X, 分析複雜度
至於Greedy地增加種類..是很直接的, 當時我是這樣猜, 但不能很系統地說服自己Greedy是正確的, 結果根本就是很明顯嘛...
int T,n,c,d,v,ans;
LL up, used, D[105];
int main(){
scanf("%d", &T);
for(int qwe=1; qwe<=T;qwe++){
used = up = ans = 0;
scanf("%d%d%d", &c,&d,&v);
F(i,0,d) scanf("%lld", &D[i]);
sort(D,D+d);
while(up < v){
LL X = up+1;
if(used < d && D[used] <= X){
up+= c*D[used++];
}
else{
up += c*X; ans++;
}
}
printf("Case #%d: %d\n", qwe, ans);
}
return 0;
}
終於終於 都把GCJ Round 1 的東東都搞完了...
剩下的就是String的文章, 還有Kattis那邊的"Lecture"吧?
String也是我拖太久 看到題B要用到的時候我已經打了自己兩巴 ...
(雖然根本重點在Expected Value)
GCJ, 下年再見吧 :/
