Subscribed unsubscribe Subscribe Subscribe

0w1

GCJ

GCJ 2017 R1B C. Pony Express ( Floyd Warshall, Dijkstra )

Dashboard - Round 1B 2017 - Google Code Jam題意: T 筆測資。有 N 個城市,用相鄰矩陣表示距離,不保證輸入距離滿足三角不等式。每個城市有一隻馬,用可行走距離 E 和最高速度 S 描述。Q 筆詢問,問 u 到 v 的最少時間。詢問之間不互相影響,而在一筆詢問…

GCJ 2017 R1B A. Steed 2: Cruise Control ( Binary Search )

Dashboard - Round 1B 2017 - Google Code Jam嗯..? 好像根本就不用二分搜題意: T 筆測資。你在數線上的原點,目的地是 D。除了你現在騎著的馬,一共有 N 隻馬,任兩隻不共享位置的處於某整數位置,並有一個最高速度的屬性描述。當後面的馬追上前面的馬時,…

GCJ 2017 Qual D. Fashion Show ( Bipartite Matching )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 給 N * N 的棋盤,以及一些士兵。士兵有三種 : { 'x', '+', 'o' },若沒有士兵用 '.' 描述。一個格子至多一個士兵。士兵配置的規則如下: 1. 任意兩個在同個水平或鉛直線上的士兵,必須有其中…

GCJ 2017 Qual C. Bathroom Stalls ( Math )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 有 N 個空間排成一排,有 K 個人依序決定自己要進哪個空間。令一個空間 i 的左邊連續空房間的數量為 L[ i ],右邊連續空房間的數量為 R[ i ],那麼任何人都會優先考慮 min( L[ i ], R[ i ] ) …

GCJ 2017 Qual B. Tidy Numbers ( Ad hoc )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 問不超過 N 的最大的,以十進制表示時,由左到右檢視,數字呈非遞減的數為何。制約: 1 ≤ T ≤ 100. 1 ≤ N ≤ 1e18. 解法: 一開始寫數位統計 dp 寫到快哭出來。 仔細想想,只要倒著決定就可以…

GCJ 2017 Qual A. Oversized Pancake Flipper ( Greedy )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 給一個由 '+', '-' 組成的序列。問能不能透過任意次操作將該序列全部元素變成 '+'。操作只有一種,將連續 K 個元素內容反轉。制約: 1 ≤ T ≤ 100. Every character in S is either + or -. 2 …

GCJ 2016 R1A pC. BFFs ( Graph Adhoc )

Dashboard - Round 1A 2016 - Google Code Jam There are two possible ways to form a maximum cycle: 1. Sum up for each pair ( u, v ) that share bidirectional edges, length of chain that starts with u, and v, such like f[ f[ .. f[ v ] ] ] u ->…

GCJ 2016 R1A pB. Rank and File ( Adhoc )

Dashboard - Round 1A 2016 - Google Code Jam The constraints were small ( T ≤ 50, N ≤ 50, H ≤ 2500 ) so I stuck and thought it could be solved by some brute force methods. However, if the point is reached, it will very easy. Thinking it cle…

GCJ 2016 R1A pA. The Last Word ( Greedy )

Dashboard - Round 1A 2016 - Google Code Jam It is very intuitive to come up with the greedy strategy where, alphabetically less characters go to the back, otherwise to the front. #include <bits/stdc++.h> using namespace std; int main(){ int T; scanf("%d"</bits/stdc++.h>…

GCJ 2016 QR C. Coin Jam ( Ad hoc )

Dashboard - Qualification Round 2016 - Google Code Jam There are several solutions, and mine is of the easier one. Since the input is fixed, 16 and 32, observing that both of them are even numbers, we will come up to that, given any number…

GCJ 2016 QR B. Revenge of the Pancakes ( Greedy )

Dashboard - Qualification Round 2016 - Google Code Jam This can be solved by DP, too. However the greedy approach is easy to come up with and shorter in code. With some observation, it is easy to find that the flips will be made from left …

GCJ 2016 QR A. Counting Sheep ( Brute Force )

Dashboard - Qualification Round 2016 - Google Code Jam It just feels like it will definitely finish before 20000 times, if solution exists. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; typedef long long ll; ll n; void solve(){ </bits/stdc++.h>…

GCJ 2014 R1A pB. Full Binary Tree ( DFS )

Dashboard - Round 1A 2014 - Google Code Jam 題目中一個合法的完全樹的定義是,所有節點的子節點數為0或2。要求的是移除最少點使得給定的樹成為完全樹。因為數據範圍小,可以考慮枚舉每個節點作為根,再做一次線性的深搜處理。根據定義可以得到遞迴函數,…