Codeforces Education Round 1

經過N個月, 公司的Project 終於見到尾聲...趁住扮工時間的空閑, 隨便找了一下CF的比賽來玩

很久之前看到CF推出的Education Round 系列已經感到興趣, 決定玩下 Round 1

看名字覺得是for 新手學習用, 所以很想玩, 但竟然...此Round 無Editorial...

究竟無Editorial 點樣可以Educate到人呢 ?

Anyway 這場有A-F共6題, 難度我覺得也是D2至D1尾吧? 最後AC了5題, 最後一題有點想法但Code不出來

要說學習了什麼, 倒不如說溫故知新, 特別是問了Peter神及GG 一些埋藏多年的白痴問題

Codeforces Education Round 1

題目: http://www.codeforces.com/contest/598/problems

A: (Math)

題目就不詳說了。
數據很小, 題目也很直觀, 基本有bitwise operation的底子可以直接code出來。
要是沒有的話其實暴試, repeat squaring之類的 怎樣也能AC。

B: (String, Ad-hoc, STL)

這題是Given 一條 string S, 然後 有一堆range query [l_i, r_i] 及T , 代表在這個range (inclusive) 內的substring 要向右rotate (shift ) T 次.

老實說這條應該是想最久的吧...因為比題目結構嚇倒了, 直接想到什麼range query什麼segment tree都出來了。

結果第二天扮工時間再看題目, 發現數據根本很小, 直接暴力做就可以了...

當然T 可以很大, 但由於 rotate 多過range的長度等於重置一次, 直接T%L (L = r_i - l_i + 1) 就好了。

我是用最慢但應該最易看的白痴寫法: C++的 STL, substr() 了很多次, 左拆右拆的, 一樣能AC。

只是看了Peter神跟 Gary神的 Code, 他們都不需要用C++的東西, 有點慚愧...

D: (Graph: DFS)

容我先跳過C, 因為題C數據上是最少人AC的, 我也最後才做, 也是相對學習得較多的一題。

題目很有趣, Given 一個2D Grid,  每格可以是路, 可以是牆。 如果是牆的話上面會有名畫一張。 然後Given m 個起始位置, 問如果你由該位置開始一直行, 怎樣行都可以 (除了穿牆), 你總共能看到多少名畫。

這樣想吧, 其實連續起來的路是一個component, Grid入面就有數個disjoint 既 components, 每個component入面不論那點作為開始, 看到的數量也是一樣的。

每個component 就像是圍棋內的一塊棋, 他們的「氣」就是名畫的數量

扯遠了...其實沒什麼關係XD

所以做法很簡單, 直接DFS, 把每個位置都歸入某個component內, 順便計算該component能看到的名畫數量。如果某點已經知道屬於那個component, 那便不用再花時間DFS了, 直接output 答案便可。 每個格子能看到的名畫數量可以在DFS前先計算好。

思路不難想, 算是鬥快寫DFS吧?

AC Code: http://www.codeforces.com/contest/598/submission/18879479

E: (DP)

這題老實說, 對我來講算是開始有難度了...雖然我知還是很簡單的題目。

題目是這樣的:  有朱古力一條, 有N*M 格,  現在你可以拆斷它, 但一定要直線或橫線, 整數地拆。每拆一次 cost 為該線的square, 問如果你想要exactly k 格朱古力, 最少cost 的拆法要多少

這類題目我有陰影, 總是想起從前有條POJ 好像叫Stick的題目, 當年覺得完全沒有思路, 不可能做得出, 然後Leo好像淡淡說了句: 呢條唔係Search ja咩? 

自那時起我都以為Search是一類特別的題目Category...
其實到現在也不太清楚他講乜春, 但這條的確是Searching, 雖然實作上是用DP做啦 (可以這樣說吧?)

數據很小, 其實也明顯是要你直接用DP做的了, 數據小到DP的方法也很直接

DP(N, M, K) :=  Minimum Cost to get K chocolates out of N*M one

DP(N, M, K)  = Min ( DP(N_1, M, K_1) + DP(N_2, M, K_2) + M*M,   DP(N, M_1, K_1) + DP(N, M_2, K_2) + N*N) for all N_1+N_2 = N, M_1+M_2 = M, K_1+K_2 = K

說白了, 就是每條邊, 和K的每種可能性 (K=4的話, 左邊0粒, 右邊4粒 / 左邊1粒, 右邊3粒...)都試掉, 看那種最優。

Code是不難寫的, base case小心點處理就好了。我是用Top-Down的寫法, Peter 神是用Bottom-Up的, 分別也不太大。

唯一WA了一棍...是被白痴位陰掉了...他有很大量的Query數目...但其實DP State pre-compute一次就行了, 第一棍把DP 放進 Input Query 的loop 裡了, 吃了TLE。

要說這條的學習, 我總是在想要是數據再大一點, 不能直接DP時, 會不會有其它做法, 這個還未有答案。

另外就是我對於分析這種Recursion + Memorization 的Complexity 很弱, 完全不知怎樣分析, master theorem好像也不能apply, 當然靠經驗感覺我知道肯定不會TLE, 但從來不知道正確及General的分析方法, 究竟是Big-O of 什麼。

有關這個, 我在Stack Overflow上問了一下, 好像也沒什麼特別的答案
http://stackoverflow.com/questions/38215549/how-to-analysis-the-time-complexity-of-this-code/38240874?noredirect=1#comment63937690_38240874

倒是Peter神的想法是把DP state的tree 做一次DFS, 所以是O(|V|+|E|), 然後看題目決定|V|和|E|是什麼, 這個想法當然好, 但我不肯定是不是General所有DP 的solution都可以這樣想, anyway仿然要#Adore#一下

C: (Geom)

最後解到的這題, 只有63個人AC了的這題, 其實不難理解。

題目本身不算難...但是一碰到Geom, 就一定會弄到精度問題, WA也不為過 

我沒有為自己WA了 13棍而開脫。

好吧先說題目 :)

題目是Given 10^5 個 vector, 全部連住Origin的。問那兩支vector的角是最小的, 這裡說的角沒有方向, 總之是該兩支vector的+角或-角magnitude 最小的 就ok。可以print出任何答案。

話說這樣的數據量, 基本上是要O( N lg(N) )的了, 看完題目基本就是Sort by Angle了吧

印象中Sort by Angle有兩種方法做, 但我只記得一種: 用atan2() 來sort.

當然n年沒有code過 geom題目的我, 一定要google atan2的用法...那些就不說了 :(

題解就是sort 完, 然後每一支vector跟前一支 (或後一支) 計一下角度, 然後找最minimum 那一pair 就好了 (最minimum 那一pair 在sort 完後一定是相鄰的, 對吧?) 

小心最後一支也要跟第一支比較。

問題來了, 一直WA一直WA, 完全不知錯在那裡。看完TEST CASE更加相信是精度問題...

所以這題的99%難度在精度問題。 以往我只知道要用eps, 但怎樣用, 為何要這樣用我也忘光了。所以我發射飛彈, 試了eps 由  e-6 開始到e-18 都試過了, 全部都WA....

終於最後, 忍不住, 隨手打開第一名那個的Code看...根本與我沒分別...唯一的分別, 在於他是用long double, 我是用double!!!!

我改完之後, 果然AC了.....!

究竟何時要用long double, 何時要用double? 我也不知道, 這是一個謎...

另外之後我問了GG, 究竟何時要用eps,  現在有一個更好的concept了....

原來eps的原意是比較2個double variable是否一樣, 而當你想 differentiate 它們的時候, 就要用上eps 來比較 ( <= 或 >= ). 在這題中用不上, 因為我們只考慮角度, 有些題目可能也要考慮長度, 那麼可能就有分別了 (sort by 角度, 角度一樣不等於"一樣")

而eps 通常是set e-8, 是-8,  至於為什麼, 連GG也說不知道 =.=


F: (Geom?)(最後一題的思路有時間後補吧...)

回到家打果然比在公司偷偷打要好得多。

這題的題目光用看的也感受到變態程度, 直到現在更只有 2個人AC...

題目大意是Given 一個 N-Side polygon, 可以Concave, Input格式為N 點, 點可以同線。
然後Given 一堆query, 每個query 是一條線, (可能) intercept with this polygon.
問, 在這條線在polygon 內的總長度是多少?

好吧我的確沒什麼完整的思路, 但腦海中立即出現的是當年CSC326 學的 Ray-Casting Algorithm (好像是叫這名字?)

好像是Given一點, 向住某一條線"射"出去, 看看穿過多少條polygon的邊。按照單雙數, 可以得知該點是否在Polygon內。

或許當中有某些思路可以apply? 沒什麼方向。 結論是為何Education Round沒有Editorial??

---

PS (Bonus)

雖然很慢, 但有感覺自己一直在進步, 可能一些以前沒有學懂的現在都會主動去學而且大約都能學會。但實在是不夠時間用, 在教會也開始要幫忙作鼓手跟導師, 工作上也愈來愈忙 (雖然快將轉工了應該), 加上要做Gym還有一大堆聚會要去, 有種感覺是一天24小時真的太少了....

另外之前在FB 路過看到一條好像是數學Olympic的題目, 對於0數學底的我, 也有些想法, 跟Peter神討論了一下, 可惜還是沒有答案~

以下是完全沒有數學底子 我的想法, 正確答案在Facebook 這幅圖的top comment已經有了 (按照那個like的數目來看)  好像是用一些我看不明白的number theory 的argument

所以這兒的想法只是自己的FF

首先證明 y = x^3 + 37 (mod 3)

By Fermat's Little's Theorem, y^2 = 1 (mod 3), So L.H.S. = y^2 ... y^2 * y (mod 3) =  y (mod 3)
R.H.S. = x^3 + 37 (mod 3),  So  y = x^3 + 37 (mod 3), Q.E.D.

然後下面是一些完全9 up 的東西, 是關於Chinese Remainder Theorem的。
從 Wiki 可以看到,

Suppose n₁, ..., n_k are positive integers that are pairwise coprime. Then, for any given sequence of integers a₁, ..., a_k, there exists an integer x solving the following system of simultaneous congruences.

這兒我重點關注 any sequence of integers a_i 這句。
我想, 這是不是等同說明

Given y = x^3 + 37 (mod 3)
There Exist some a' = x^3 + 37 (mod 5)  such that 
 y = a' (mod 5) 

因為 3 跟 5是co-prime嘛, 然後x^3 + 37 也肯定是integer for any x
同理 其它 prime number 也跟 3 是 co-prime, 所以 y = x^3 + 37 (mod p) 

然後L.H.S 跟R.H.S. 一同自乘 37次 就行了...


但這只是我的狂想, 因為我根本不了解Chinese Remainder Theorem, 特別是我覺得以上的argument 有違

A solution x exists if and only if

${\displaystyle a_{i}\equiv a_{j}{\pmod {\gcd(n_{i},n_{j})}},}$

所以也就沒再深究下去了。(後註: 後來想下去果然還是錯得很離譜XD)

Google Code Jam 2015 Round 1B

幾經辛苦,  終於把GCJ 1B的題解都看完, 理解後又做完了

說是全部做完也不太正確, 我最後還是沒做A-Large 以示我的不滿

話說近幾天我開始思考, 為什麼前些日子, 某些比賽/題目

做完之後即使沒想法, 看完題解還是自我感覺良好 很有得著

反之GCJ (還有近來一些CF)的題目好像沒有這樣的感覺?

是我熱情又下降了還是怎樣

最後得出的結論是: 題目的Ad-hoc程度

之前很有得著的題目, 全部都可以很實在地學到一些明顯以後都會用得上的Trick /技巧

例如我還得有一個是用Matrix Multiplication做 N很大的DP

還有前幾篇說的用BIT 數Total Inversion Number的做法

用2個BIT 做Range Add, Range Query的方法

留意題目可能有 SQRT(N) 的暴試方法等

我叫這些做 "性價比" 很高的Tricks, 感覺很多時都會用得上 (而我以前又完全沒學過的)

但就是有些題目, 完全是Ad-hoc的, 可能需要即時的觀察, 推斷, 證明一大堆東西

才會有一個算法出來  但由於題目是Ad-hoc的,  解這些題目中所用到的技巧 根本以後都用不上

我個人不太喜歡這些題目...因為感覺上如果即場做不到, 事後看題解再做也沒意義

反正題解的方法也就只適用於該題目....對吧?

而很不巧的...GCJ 1B 跟1C的題目我認為Ad-hoc度很高, 就是說即使事後明白了也好像沒什麼實在的得著....姑且先寫一下GCJ 1B的題解

Google Code Jam 2015 Round 1B

差47名....但不可惜的, 因為不是時間問題

我看了一下第1000名的分, 起碼要做到多一題才能上頭1000名

題目: https://code.google.com/codejam/contest/8224486/dashboard#s=p0&a=1

A-Small: (Ad-hoc, Greedy)

題A可以說是我最不滿的一題了

題目要求把數字A轉去B, 當中可以用2種Operations:

1. 把A+1
2. 把A Reverse (eg: 123-->321)

問最少要多少Operation才能由A到B?

太多事要證明了, 而官方答案也沒好好的證明題解

我只能說很多人都是蒙混地AC的...

我在CF上求證明, 也沒人理會, 反而是有人回答我他完全忘了這個Case卻AC了 (他得到很多負評)

我的Small是用DP做的, 就是把全部"path"試一下, 要是步數較少的位則update

(跟Dijkstra一樣)

這兒我有賭博成份: 

如果按我CF上的問題來說: 有一Path A-->C-->B 是最優解where C > B > A

eg:  .....-->18-->81-->82-->28 

那我的DP會錯

但我還是照交了, 證明我當時是多絕望

結果竟然AC了...

A-Large: (Ad-hoc)

再來看Large的數據, 加上AC了Small

我有幾點懷疑:

1. 根本不會出現A-->C-->B
2. Reverse不能把digit數加大 (eg 999-->1000)  
3. 所以可能是由(A-->10-->99-->100-->999-->1000) 這樣的分解去做
4. 每一位數的Range內不能暴試...出題者可能有些很快的方法可以由100-->999
5. 可能每一位數的Range內只會最多用Reverse一次? 其它的都是+1?

我是有這樣的估計, 但完全證明不了, 就是證明了也很煩..所以果斷放棄

而按CF紅字User 加 Google官方題解, 這些都是正確的...

準備的來說, Strategy是把 尾N/2 個digit 合到999..9, 一個Reverse, 再用+1 就可以快速把位數增大...就這樣去由A去到B...

但為何Reverse肯定是這樣用一次是最好的我就不明白了...

我也唯有這題沒回頭再去交了, 這題真的太Ad-hoc了, 即使辛苦AC了也沒學習價值吧...

B-Small: (Brute Force)

這題有意思多了

題目給了一個 n*m 的grid

要安排 k 個人住在裡面  一格住一個人

要是有2個人 adjacent 的話, "不開心度" 會加一

現在你可以任意安排k 個人住在那些位置, 問最少的"不開心度"是多少?

想了一想好像也沒什麼想法

也沒什麼Pattern

所以我直接暴試了 (題目數據也是想我們這樣吧...)

就Bit-wise暴試把k 個人都亂放, 看看那個Configuration 的"不開心度"最少就好了~

由於是暴試, 也沒什麼好證明的, Code得對就能AC

B-Large: (Ad-hoc, Pattern Observe, Greedy)

我特意為了這一題, 開了一個我認為好像很多高級題目都會有關的Tag: Pattern Observe

話說這一題, 是真心唯一一題可恨的, 看了題解後認為這一題是有機會可以做到的...

話說比賽中我已經有了一個正確的方向, 很多題目都會利用這一種思想:

不要直接想把k 個人放在那,  去想那些 n*m-k 個格子不要放人"

就是逆轉思維 GCJ 好像很喜歡這種思路呢

簡單來說就是先假設N*M全部都是人, 然後試試把人踢走

踢剩 k 個人就完結  怎樣踢才是最好的呢?

比賽中我認為這題沒什麼Pattern, 原因是: 明顯地如果 k < n*m / 2

可以梅花間竹地安排住客, 答案是0

但要是一多過, 就完全沒Pattern了...

看完題解後, 才發現, 其實是有Pattern的....

首先要是 k <= ceil (n*m/2) 答案就是0

要是大過呢?

大過的時候, 再把Case分為 1D 和 2D (這個CF也見過幾次, 可能是很常見的分析技巧?)

1D的時候, 不難發現只要隔一個隔一個地踢走人就好了 這樣每次都能減少最大限度的"不開心度" (ie: 2)

2D (n 和 m >= 2)

 .3.2     .3.3.     2.3.2     .3.3.
 3.4.     3.4.3     .4.4.     3.4.3
 .4.3     .4.4.     3.4.3     .4.4.
 2.3.     2.3.2     .4.4.     3.4.3
                    2.3.2     .3.3.

4 x 4     4 x 5     5 x 5     5 x 5

借官方的圖一下, 圖中的數字是"如果踢走該位人士, 可以減走的不開心度"

注意 . 的位置是必需有人住的, 也就是說最多就只能把有數字的位置都踢走住客

然後不難發現, 只要Greedy地把佔最多不開心度的人先踢走...肯定會把答案減至minimum 吧?

然後再發現, 其實不開心度的值只會有"2,3,4" 3種

這兒引入一種 可能很常用的技巧, 把Grid 分為 3種可能性的 Size來Observe Pattern:

1. Odd * Odd
2. Even * Even
3. Odd * Even

以這題來說, 把3種情況都畫一下數一下2,3,4的數量, 跟它們的 n , m 之間的關係

很快就有一個pattern出來了

唯一要注意的是 Odd*Odd的Case, 是可以有2種不同的"踢走人的Configuration"

另外2種Case的2種不同Config是 Mirror, 唯有Odd*Odd是有機會不同

不知按那一種去做才更好, 2種都要試一下

下面的code 的 k 跟上面的定義不同, 自己看comment

#include<bits/stdc++.h>
using namespace std;

int T,r,c,n,k,totalScore, subtract1, subtract2;
int p1[5], p2[5];
int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe <= T; qwe++){
        scanf("%d%d%d", &r,&c,&n);
        printf("Case #%d: ", qwe);

        k = r*c - n; // # to removed from full occupied building
        totalScore = 2*r*c - r - c;
        memset(p1,0,sizeof(p1));
        memset(p2,0,sizeof(p2));
        subtract1 = subtract2 = 0;

        if(n <= (r*c + 2-1)/2) printf("0\n"); // ceil(r*c/2)
        else if(r == 1 || c == 1) printf("%d\n", totalScore - 2*k);
        else{
            if(r%2 == 0 || c %2 == 0){
                p1[2] = p2[2] = 2;
                p1[4] = p2[4] = (r-2)*(c-2)/2;
                p1[3] = p2[3] = r*c/2 - p1[2] - p1[4];
            }
            else{
                p1[2] = 4, p2[2] = 0;
                p1[4] = ((r-2)*(c-2) + 2 -1)/2; p2[4] = (r-2)*(c-2)/2;  //p1_4 = ceil((r-2)(c-2)/2)
                p1[3] = 2*((c-2)/2 + (r-2)/2); p2[3] = 2*((c-2+2-1)/2 + (r-2+2-1)/2); //p2_3 = 2*(ceil((c-2)/2) + ceil((r-2)/2))
            }

            int tmp1 = k, tmp2 = k;
            int x = 4;
            while(tmp1){
                if(p1[x]){p1[x]--; tmp1--;subtract1 += x;}
                else x--;

            }
            x = 4;
            while(tmp2){
                if(p2[x]){p2[x]--; tmp2--;subtract2 += x;}
                else x--;
            }
            printf("%d\n", totalScore - max(subtract1, subtract2));
        }


    }
    return 0;
}

這題學到的可能比較有用的是:

1. 要是2D的Case太難想, 先想1D, 可能可以引伸到2D, 又或者1D的Case是Special Case要分開處理
2. 要Observe Pattern時, 把情況分為: Odd*Odd, Even*Even, Odd*Even, 而且可以的話最好邊長 > 2 (4*4, 3*5...etc)

C-Small-1 (Ad-hoc)

C也是另一題比較有意思的題目...做不到也是無可厚非, 因為我對Event沒什麼概念

題目太長了就不另外說了

這題是少數Small Case分 2題的題目

Small-1來說由於只有 2個Hikers

我以人力分析了所有可能性, 由於Herbert 能以光速跑動

直接把它想成能和hiker "差不多" 一起跑就好了

(Just before / Just after hiker)

不難發現如果只有2個Hiker, 最多的Encounter只會是一次

Case有3-4個, 就不詳細寫了

基本思路是算一算Herbert 走完一圈的時間, 跟兩個Hiker走完一圈和兩圈的時間之間的關係

又, 由於Herbert可以跟隨便一個Hiker一起走, 直接分析兩個Hiker 跑到 0 度時的時間就行了

假設Hiker 1 初始距離 比Hiker 2 遠離終點

剛要是Hiker 1 跑完一圈的時間比Hiker 2  跑完兩圈的時間快, 則答案是 0, 因為Herbert可以跟住Hiker 1 一起跑 (以Just before的距離跟住他所以不造成Encounter)

還有其它Case都差不多...就這樣了

寫的時候很混亂, 能AC也是很開心的...

#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 flt(x,y) ((x)+eps < (y))
using namespace std;

int T,n,ans;
vector<PII> hiker;
int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &n);
        int cnt = 0;
        hiker.clear();
        for(int i=0,tp,tm,th; i<n;i++){
            scanf("%d%d%d", &tp, &th, &tm);
            while(th--){
                hiker.pb(mp(tp, tm++));
            }
        }

        if(cnt == 1 || hiker[0].y == hiker[1].y)
            printf("Case #%d: %d\n", qwe, 0);
        else{
            sort(hiker.begin(), hiker.end());
            if(hiker[0].y > hiker[1].y){
                double t0 = (360.0 - hiker[0].x)/(360.0/hiker[0].y);
                double t1 = (720.0 - hiker[1].x)/(360.0/hiker[1].y);
                if(flt(t0,t1)) ans = 0; else ans = 1;
            }
            else{
                double t0 = (360.0 - hiker[0].x)/(360.0/hiker[0].y);
                double t1 = (360.0 - hiker[1].x)/(360.0/hiker[1].y);
                if(flt(t1,t0)) ans = 0;
                else{
                    t0 = (720.0 - hiker[0].x)/(360.0/hiker[0].y);
                    if(flt(t1,t0)) ans = 0;
                    else ans = 1;
                }
            }
            printf("Case #%d: %d\n", qwe, ans);
        }
    }
    return 0;
}

C-Small-2: (Ad-hoc, Greedy)

要過Small 2 要對所謂Event有一定的概念呢

其實重點是有很多重要的Observations...

首先, 能任意改變速度完全對答案沒有影響...

假設最後答案是X, 在Encounter X 次的條件下, Herbert跑完一圈的時間是在限定的range內

相對來說, 它的跑速也是在限定的Range內, 是constant的speed

所以完全不用想什麼改速度之類的Strategy..

然後X最大也只會是H 次, where H = | hikers |

這很正常吧...因為只要Herbert以光速跑動, 一開始就把所有人Encounter一次回終點, 這樣也是 H 次而已

然後我來想定義一下這題的Event...

由於上面的Observation, 不難發現答案跟Herbert 跑完一圈回0度的時間有關係的

所以倒不如把所有Hiker跑到0度的時間當做Event Point, 看看Herbert在這個Event Point的時間點剛好跑回終點的話會發生什麼事

Call the time at which Herbert finishes his hike X, and the times when the hiker reaches Herbert’s starting point T1, T2, T3, etc.

• If X <= T1, then there is one encounter with the hiker as Herbert passes.
• If T1 < X < T2, then there are no encounters with the hiker.
• If T2 <= X < T3, then the hiker passes Herbert once.
• If T3 <= X < T4, then the hiker passes Herbert twice.
• etc.

上面是官方答案抄出來的

要是 X 比某一個Hiker 第一次回0度的時間還早的話, Herbert 肯定爬他頭了

要是在第一次回0度跟第2次回0度中間 則沒有Encounter

之後每一個range都會把Encounter數 + 1

這些T1,T2...就是所謂的Event Point了...它們把Herbert到達的時間分成很多段

每一段的Encounter都可以算出來

又, 由於答案最多是H

所以每一個Hiker 只需要找出它們頭 H 個Event

把Total H^2 個Event 排一下序 (按時間)

把counter設為H   如果該名Hiker是第一次相遇 (T1) 則把counter -1, 其它時候都+1

再假設Herbert 在每一個Event Just before / Just after 回到終點

看看在那一個Event Point的時間會是最少Encounter

#include <bits/stdc++.h>
#define eps 1e-9
#define flt(x,y) (((x) + eps) < (y))
#define feq(x,y) (fabs((x)-(y)) <= eps)
#define LL long long
using namespace std;
int T,N,ans;
bool meet[500005];

struct H{
    LL D, M;
    H(){}
    H(LL D, LL M): D(D), M(M){}
};

struct E{
    double T;
    int id;
    E(){}
    E(double T, int id): T(T), id(id){}
};

vector<H> hikers;
vector<E> eventPoints;

bool tt(E a, E b){
    return flt(a.T, b.T);
}

int main() {
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &N);
        hikers.clear();
        eventPoints.clear();
        memset(meet, 0, sizeof(meet));

        for(LL i=0,d,h,m; i<N;i++){
            scanf("%I64d%I64d%I64d", &d,&h, &m);
            for(int j=0; j<h;j++) hikers.push_back(H(d, m+j));
        }
        int ANS = hikers.size();
        ans = hikers.size();
        for(int i=0; i<hikers.size(); i++){
            for(int j=0; j<hikers.size(); j++)
                eventPoints.push_back(E(hikers[i].M*j + hikers[i].M * (360.0 - hikers[i].D) / 360, i));
        }
        sort(eventPoints.begin(), eventPoints.end(), tt);
        for(int i=0; i<eventPoints.size(); i++){
            if(!meet[eventPoints[i].id]){
                ans--; meet[eventPoints[i].id] = 1;
            }
            else ans++;
            if(i< eventPoints.size()-1 && feq(eventPoints[i].T, eventPoints[i+1].T)) continue;

            ANS = min(ANS, ans);
        }
        ANS = min(ANS, ans);
        printf("Case #%d: %d\n", qwe, ANS);
    }
    return 0;
}

C-Large (Ad-hoc, Greedy, STL)

最後的最後的C-Large了

其實如果一個人能想到C-Small-2

C-Large就很容易了

最大的問題是, 不能把H^2 個Event全部試, 也不能全部儲起

會TLE + MLE的說...

這兒需要用到最後的Observation:

每個Hiker 可以把答案 減1 的機會只有一次

最多就只會 - H

所以總的來說, 我們只要試2*H個Event就可以了

2*H 個Event以後就沒辦法把答案變成 < H了

(這個Observation再來一次也想不到...)

所以答案呼之欲出了: 只去數頭2*H個Event

用Priority Queue! (Min Queue, 按時間排)

先把H 個 T1 Event 放進Queue, 然後每處理一個Event, 才把它下一個Event push進queue

這樣做2*H次就完結

有一個小Tricky位時, 某些 Event T1 跟 其它非T1 Event的時間是一樣的, 

這時必需先處理非T1 Event (先加1)

原因是physically Herbert不能跟T1 Exactly一樣時間到達終點而使答案減1

它必需比T1 慢一點點 (just after)的時間到達, 所以減1的步驟肯定是最後處理 (不然算答案時可能會比正確答案少!)

Code的時間, Implement STL的Priority Queue (本來是max heap)時 加上 greater<>, 再在struct內加上 > 的overload就可以變成min heap了, 而在overload時我考慮了 Event的cycle (就是T1 還是非T1), 非T1的Priority更高

AC是AC了, 但執行時間還是有點慢呢..(在CF上交是2074ms)

#include <bits/stdc++.h>
#define eps 1e-9
#define flt(x,y) (((x) + eps) < (y))
#define feq(x,y) (fabs((x)-(y)) <= eps)
#define LL long long
using namespace std;
int T,N,ans;
bool meet[500005];

struct H{
    LL D, M;
    H(){}
    H(LL D, LL M): D(D), M(M){}
};

struct E{
    double T;
    int id;
    int cycle;
    E(){}
    E(double T, int id, int cycle): T(T), id(id),cycle(cycle){}
    bool operator>(const E& a)const{
        return flt(a.T , T) || (feq(a.T,T) && cycle < a.cycle); //if same time, then T2, T3...priority before T1
    }
};

vector<H> hikers;
priority_queue<E, vector<E>, greater<E> > q; // default is max heap, use greater comp to make it min heap

bool tt(E a, E b){
    return flt(a.T, b.T);
}

int main() {
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &N);
        hikers.clear();
        while(!q.empty()) q.pop();
        memset(meet, 0, sizeof(meet));

        for(LL i=0,d,h,m; i<N;i++){
            scanf("%I64d%I64d%I64d", &d,&h, &m);
            for(int j=0; j<h;j++) hikers.push_back(H(d, m+j));
        }
        int ANS = hikers.size();
        ans = hikers.size();

        for(int i=0; i<hikers.size(); i++){
            q.push(E(hikers[i].M * (360.0 - hikers[i].D) / 360, i, 1));
        }
        // only test 2*H events is enough, or afterwards all ans will >= H
        // As we implement the comp with cycle, same time is handled correctly (add 1 before minus 1)
        // use priority queue to real time generate event so that we do not need to store all H^2 events
        for(int i=0; i<2*hikers.size(); i++){
            E tmp = q.top(); q.pop();
            if(!meet[tmp.id]){
                meet[tmp.id] = 1; ans--;
            }
            else ans++;
            q.push(E(tmp.T + hikers[tmp.id].M, tmp.id, tmp.cycle+1));
            ANS = min(ANS, ans);
        }
        ANS = min(ANS, ans);
        printf("Case #%d: %d\n", qwe, ANS);
    }
    return 0;
}

總結來說, 發現這場所有題目都有Ad-hoc的Tag了吧...

究竟在這些題目上能學多少實用的東西呢? 我也不知道..

題B跟題C的思路還是可以學習一下的吧? 題A就....算了吧