說是全部做完也不太正確, 我最後還是沒做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
我看了一下第1000名的分, 起碼要做到多一題才能上頭1000名
A-Small: (Ad-hoc, Greedy)
題A可以說是我最不滿的一題了
題目要求把數字A轉去B, 當中可以用2種Operations:
- 把A+1
- 把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
我有幾點懷疑:
- 根本不會出現A-->C-->B
- Reverse不能把digit數加大 (eg 999-->1000)
- 所以可能是由(A-->10-->99-->100-->999-->1000) 這樣的分解去做
- 每一位數的Range內不能暴試...出題者可能有些很快的方法可以由100-->999
- 可能每一位數的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:
- Odd * Odd
- Even * Even
- 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; }
這題學到的可能比較有用的是:
- 要是2D的Case太難想, 先想1D, 可能可以引伸到2D, 又或者1D的Case是Special Case要分開處理
- 要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就....算了吧
沒有留言:
張貼留言