朝早九點開波..

A - "K"子棋, given current state, 問 rotate 90^o 後邊一邊會勝出 (可以both/neither)

但開頭 score 分佈出錯左, 以為有 trap, 所以無即刻揼.. 決定睇埋B,C先

B - given sequence , 可以 add/delete/change (各自有 cost) , 目標係試 neighbour 的 difference <= M, 求 min cost

C - 兩人玩的game, 一開始有兩個數 (A,B), 每一個 step 可以改為 (A , B-A*k) 或 (A-B*k , A) , k 是正整數, 問某個 range 入面有幾多 pair (A,B) 是 winning state

analyze下, B 明顯係 DP, 應該幾輕鬆 ; 但 C 疑似 Nim game 果類, 基本上係未 code 過

之後佢出 clarification 改返分數, 發現 A 佔分最少, 於是放心去寫A, 大約 30 mins 時 A-small  Correct!

今次打算用一個 strategy - 唔隊 large 住, 之後有時間再 double check 多次, 因為 large 得一次機會同埋GCJ 計時間係計最後 submission, 對penalty無咩影響 (如果之後會再 submit 的話)

寫 B - DP, change 同 delete 好易 handle, add 諗左一陣, 確定係 round up 除法, 過 test case, Correct!

之後就朝 C 進發

C - 睇多睇又唔似 nim, 於是用 memorization 的方法去打個表搵observation, 得到

很明顯地有 pattern -- 之後就陷入一小時的掙扎

一開始以為係好簡單既 pattern, 但試左幾個 sequence 後後面又總係唔 work, 於是出動武器 - KMP 用電腦去搵 pattern, 但 turns out 佢係無一個 "repeat" 既 component ..!

唔忿氣, 出動埋 guassian , 話唔定係一條 polynomial , 入左頭 5 個數落去就知唔 work - solve 出黎的 coefficient 唔係 integer ... 睇黎條 sequence 唔係 polynomial ..

諗

諗

諗

剩返 20 mins 果陣, 突然發現 -

 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******

每一行/列 * 的數目 等於 果行/列 的篇號!

諗深一層, 其實係同 self-describe sequence 差唔多  突然感覺到離答案只差一步

揼... 揼... 揼...

大約剩返 8 mins 時揼好, submit, Incorrect

灰左一灰, 但立即想到是 BIT 越界問題, 改, Correct!

Result ..

113

gagguy Me

100

2:30:38

32:50

1:36:12

50:27

1:39:01

2:26:02  1 wrong try

2:26:38

不過最滿足都係做到條 C

後記

睇返 official report, 原來 B 有 的做法, C 和 golden ratio 有關

GCJ 牽涉的範疇真的很廣泛, 學多d野才是上策