Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank題意: 有 N 個線段,用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後,每個線斷所成的圓面積總和為何。制約: 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法: 首先…

HR Spanning Tree Fraction ( 最優比例生成樹, Binary Search, Spanning Tree )

Programming Problems and Competitions :: HackerRank題意: N 個點 M 個邊,第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹,使得 sum( a ) / sum( b ) 最大。制約: 2 ≤ N ≤ 1e5 N - 1≤ M ≤ 1e5 1 ≤ a[ i ], b[ i ] ≤ 100解法: 裸的最優比例生成樹。 聽…

ARC 072 F - Dam ( Greedy, Monotonous, Deque )

F: Dam - AtCoder Regular Contest 072 | AtCoder題意: 有一個水壩,容量是 L。有 N 天,第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩,晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i,問使得第 i 天恰有容量 L 的水在水壩…

ARC 072 E - Alice in linear land ( DP )

E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder題意: 有一個車子在數線上的原點。目標是 D。依序有 N 個操作,d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ],但特別地,如果操作後不會接近,則該次操作無…

ARC 072 D - Alice&Brown ( Game Theory, SG )

D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder題意: 兩堆石頭,數量 X, Y。輪流操作,一次選一個正整數的偶數 v,從一個至少有 v 個石頭的堆裡除去,並在另一堆上添加 v / 2 顆石頭。先不能操作的人輸。問雙方最佳操作下誰贏。制約: 0 ≤ X, Y ≤…

ARC 072 C - Sequence ( Greedy )

C: Sequence - AtCoder Regular Contest 072 | AtCoder題意: 給 N 個數字的數列 A。一次操作選一個數字 +1 或 -1。問最少要幾次操作,才能使得前綴和的正負交替。制約: 2≦n≦1e5 |ai|≦1e9 ai は整数解法: 枚舉開頭是正或負。由左到右確定數字,只有在必要…

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 隻馬,任兩隻不共享位置的處於某整數位置,並有一個最高速度的屬性描述。當後面的馬追上前面的馬時,…

CFR 798 D. Mike and distribution ( Adhoc / Random )

Problem - D - Codeforces題意: 給長度 N 的兩個數列 A, B,求構造一個 C[],使得 len( C ) ≤ N / 2 + 1,且所有元素相異,且任意 i 滿足 1 ≤ C[ i ] ≤ N,並有 sum( A[ k ] for k in C ) * 2 > sum( A ) 且 sum( B[ k ] for k in C ) * 2 > sum( B )。制約…

CFR 798 C. Mike and gcd problem ( Math )

Problem - C - Codeforces題意: 給長度為 N 的數列 A。每次可以進行的操作為,選擇一個 i,並執行 A[ i ], A[ i + 1 ] = A[ i ] - A[ i + 1 ], A[ i ] + A[ i + 1 ]。問至少要進行幾次操作,才能使得 gcd( A ) > 1。制約: The first line contains a singl…

CFR 795 L. Bars ( Binary Search )

Problem - L - Codeforces題意: 有 N 天,你有 K 個巧克力棒。第一天和最後一天一定是空的,而且你一定要吃巧克力棒。其他天有些要工作,所以那些天不能吃巧克力棒。問最佳的安排下,你最少的最多不能吃巧克力棒的連續天數。制約: The first line contains…

CFR 795 K. Stepan and Vowels ( Ad hoc )

Problem - K - Codeforces題意: 給一個長度為 N 的字串,要求進行壓縮,規則如下: 若 "aeiouy" 任意一個字符連續出現兩次以上,則壓縮為一個。 例外是若 'e' 或 'o' 連續出現恰兩次,則不能壓縮。制約: The first line contains the integer n (1 ≤ n ≤ 1…

CFR 795 J. Stepan's Series ( Ad hoc )

Problem - J - Codeforces題意: 給一個長度為 N 的字串,由 "YN?" 組成。'?' 有可能為 'Y',有可能為 'N'。給定一個 K,問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的,也就是左界左邊和右界右邊的元素必須為 'Y'。制約…

CFR 795 I. Composing Of String ( DP )

Problem - I - Codeforces題意: 有 N 種字串。你的目標字串為 target。問至少要連接幾次字串,才能使得這個大字串的子序列有 target。制約: The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set. The next n lin…

CFR 795 H. Repairing Of String ( Ad hoc )

Problem - H - Codeforces題意: 給 C[],C[ i ] 代表長度為 i 的元素種類單一子字串的數量。求構造字串。制約: The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string. The second line contains the seque…

CFR 795 G. Perfectionist Arkadiy ( Math )

Problem - G - Codeforces題意: 給 A, H, W,代表有一個紙張 H * W 大小,圖片是一個邊長為 A 的正方形。現在要放任意個正方形,使得所有相鄰正方形之間,以及邊界和其相鄰的正方形的間距為任意實數 x。問 x 最小可以是多少,無解則輸出 -1。制約: The fir…

CFR 795 F. Pens And Days Of Week ( Periodic )

Problem - F - Codeforces題意:制約: The first line contains the integer n (1 ≤ n ≤ 50 000) — the number of pens Stepan has. The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 1e9), where ai is equal to the number …

CFR 795 E. Big Number and Remainder ( Math )

Problem - E - Codeforces題意: 給大數 N,以及一個數字 M。考慮 N 的所有循環 ( N[ x : ] + N[ : x ], for any N[ x ] != 0 ),問其中模 M 後最小的數字為何。制約: The first line contains the integer which Stepan has. The length of Stepan's integ…

CFR 795 D. Lie or Truth ( Ad hoc )

Problem - D - Codeforces題意: 給長度 N 的 A, B 數列。問是否可以只任意排列 [ L, R ] 區間內的元素,使得 A = B。制約: The first line contains three integers n, l, r (1 ≤ n ≤ 1e5, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the position…

CFR 795 C. Maximum Number ( Greedy )

Problem - C - Codeforces題意: 你有無限多個七段顯示器,問不超過 n 個段可以發光的前提下,可構成的最大數字是多少。制約: The first line contains the integer n (2 ≤ n ≤ 100 000) — the maximum number of sections which can be highlighted on the…

CFR 795 B. Significant Cups ( Monotonicity )

Problem - B - Codeforces題意: 你有 n 個 PhOI 獎牌,m 個 IOI 獎牌,各自用價值 c 和重量 w 描述。你有一個容器可以容下不超過 d 的總重量,問在兩種獎牌至少各一枚,且當一種獎牌中價值為 x 的獎牌被納入則所有價值超過 x 的同種獎牌也都必須納入的前提…

CFR 795 A. Amusement Park ( Greedy, Ternary Search )

Problem - A - Codeforces題意: 有 N 個人,用一個 01 序列描述,0 代表小孩,1 代表大人。給定 C1, C2,你要將這些人分群,使得每個群至少有一個大人,而且最小化 sum( C1 + C2 * ( X[ i ] - 1 )^2 ),其中 X[ i ] 代表第 i 個群的人數。制約: The first …

CSAcademy 25. Zone Capture ( BCC )

Round #25 (Div. 2 only)題意: 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約: 1 ≤ N, M ≤ 1000解法: 將…

CSAcademy 25. Min Ends Subsequence ( Persistent Segment Tree )

Round #25 (Div. 2 only)題意: 給一個排列 1 ~ N,問最長的一個子序列,滿足:頭尾元素都比所有中間的元素大。輸出長度。制約: 1 ≤ N ≤ 1e5解法: 不失一般性,假設最長的這個子序列的頭 i 和尾 j 滿足:i 枚舉所有 i,令 j 為 i 顯然這個 j 是最優的,而…

Yuki 489 株に挑戦 ( Sliding Window )

No.489 株に挑戦 - yukicoder題意: 買賣股票,買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約: 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法: 努力寫了一次線段樹,但 python 也很給力的 TLE 了。 經典的滑動視窗: window[ i ]: i …

Yuki 497 入れ子の箱 ( DP )

No.497 入れ子の箱 - yukicoder題意: 給 N 個箱子,用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。制約: 1≤N≤1000 1≤Xi,Yi,Zi解法: 依最小的…

Yuki 502 階乗を計算するだけ ( Offline )

No.502 階乗を計算するだけ - yukicoder題意: 給 n,求 X: X = n! mod (1e9+7)制約: 0 ≤ n ≤ 1e18解法: 首先 n ≥ 1e9 + 7 時,X 顯然為 0。 本地建表,將 1e7 的倍數都填上去,那麼計算量便是至多 1e7。 MOD = int( 1e9 + 7 ) ''' Used for offline prep…

Yuki 496 ワープクリスタル (給料日前編) ( DP )

No.496 ワープクリスタル (給料日前編) - yukicoder題意: 你有 N 顆一次性的魔法石頭,第 i 顆可以幫你在 X 軸上 + X[ i ],Y 軸上 + Y[ i ],但花費魔力 C[ i ]。你現在在 ( 0, 0 ),你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格,花費 F。…

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder題意: 給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。制約: N ≤ 1e18解法: 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

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 …

ARC 071 F - Infinite Sequence ( DP )

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder題意: 問有多少無窮長度數列 A[] 滿足: 1. i 的下一個元素開始連續 A[ i ] 個皆相同 2. 對所有的 N ≤ i, j,A[ i ] = A[ j ] 輸出答案對 1e9 + 7 取模。制約: 1≤n≤1e6 n は整数解法: 首先…

ARC 071 D - 井井井 ( Math )

D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder題意: 在二維座標系上,給 N 個縱線,M 個橫線,問所有可形成的四邊形面積總和。輸出答案對 1e9 + 7 取模。制約: 2≤n,m≤1e5 xi,yi は整数である。解法: 首先顯然兩個維度可以獨立看待,因此考慮…

ARC 071 E - TrBBnsformBBtion ( Ad hoc )

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder題意: 給字串 S, T。Q 筆詢問,指定 S 的某個子字串 S', T 的某個子字串 T',問是否能透過施行以下操作任意次由 S' 轉換為 T'。 1. 將 'A' 換成 "BB" 2. 將 'B' 換成 "AA" 3. 將 "AAA" 換成 "…

ARC 071 C - 怪文書 ( Greedy )

C: 怪文書 / Dubious Document - AtCoder Regular Contest 071 | AtCoder題意: 給 N 個字串,求一個最長的字串,若相同則字典序最小,使得每一個字串都能透過任意刪除、交換位置得到。制約: 1≤n≤50 i=1,…,n に対して、 1≤|Si|≤50 i=1,…,n に対して、 Si は…

CFR 616 E. Sum of Remainders ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N, M,求: 資料規模: The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.解法: 首先觀察到 因此所求可以寫成 考慮比較簡單的這個問題: 這個的求法是基於平方分割,細節和這篇…

PE 401 Sum of squares of divisors ( Math, Sqrt Decomposition )

Well, I know that posting this might no be completely appropriate but...題意: 問 [ 1, 1e15 ] 所有整數的因數平方總和為多少。解法: 也就是平方分割,而枚舉 d 轉換成枚舉 N // d 那部分我一直很搞不清楚,但其實只要知道這件事就可以理解: 這件事成…

CFR 327 C. Magic Five ( Math )

Problem - 327C - Codeforces題意: 給一個大數 A,將其複製 K 次連接成一個新的大數 S。問有多少種方法任意刪除 S 中的數字,使得留下來的數字被 5 整除。允許領導 0,但不允許空字串。兩個方法相同若且唯若兩個方法刪除的數字的位置都是一樣的。資料規模:…

CFR 244 B. Undoubtedly Lucky Numbers ( Digit DP, Python deepcopy() )

Problem - B - Codeforces題意: 給正整數 N,問有多少正整數不超過 N,在十進制下可以用不超過兩種數字表示。資料規模: N ≤ 1e9解法: dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴,已使用的數字是 ( j, k ),滿足 j 用 python 的編程瓶頸在於宣…

CFR 120 B. Quiz League ( Python read / write file )

Problem - B - Codeforces題意: 很水,不太重要,這裡記錄 python 的讀 / 寫檔。 前三行有,就等價 C++ 開了 freopen() import sys sys.stdin = open( 'input.txt', 'r' ) sys.stdout = open( 'output.txt', 'w' ) N, K = map( int, input().split() ) K -=…

CFR 86 D. Powerful array ( Mo's Algorithm, Math )

Problem - D - Codeforces題意: 給一個長度為 N 的數列 A[]。T 筆詢問,問對 [ L, R ] 中存在的所有相異數值 s,SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中,s 出現的次數。資料規模: First line contains two integers n and t (1 …

CSAcademy 23 E. No Prime Sum ( Bipartite Matching, Minimum Vertex Cover )

Round #23 (Div. 2 only)題意: 給 N 個相異正整數,問最少要移除幾個數字,能使任意兩個數字的和不為質數。輸出方案。限制: 2≤N≤2000 The elements of S are distinct integers between 1 and 10^5解法: 首先顯然偶數+偶數以及奇數+奇數的情形一定不會產…

CSAcademy 23 D. Disk Mechanism ( Greedy )

Round #23 (Div. 2 only)題意: 給若干個中心,現在你要以這些中心擺放圓。有左數起第 i 個圓的半徑可以是 [ L[ i ], R[ i ] ] 中任意整數。兩個相鄰的圓必須相切。問有幾種方案。限制: 2≤N≤1e5 The point coordinates are given in increasing order and t…

CSAcademy 23 C. Permutation Matrix ( Periodic, Union Find )

Round #23 (Div. 2 only)題意: 給一個長度 M 的排列 P,現在要做一個 N * M 的矩陣,第 i 行是 P^i( P )。 問 M 個列分別的數值總和為何。限制: 1 ≤ N, M ≤ 1e5解法: 顯然會形成一些循環,用 dfs 找出這些循環並記錄每個節點在每個循環中哪個位置,預處理…

CSAcademy 23 B. Fast Travel ( Greedy )

Round #23 (Div. 2 only)題意: 有 N 個城市,以座標描述。兩個城市之間的移動的所需時間是曼哈頓距離。有些城市是特別的 ( S = 1 ),特別的城市之間可以花費 T 單位時間進行瞬間移動。Q 筆詢問,每次問兩個城市之間最少需要花費的移動時間。限制: 2≤N≤1000…

CFR 301 A. Yaroslav and Sequence ( Greedy )

Problem - 301A - Codeforces題意: 給一個長度為 2 * N - 1 的數列 A。你可以進行任意次以下的操作: 選擇任意 N 個相異的元素,讓他們的符號反轉 ( 乘上 -1 )。 問操作後,可以得到的最大數列和為何。資料規模: The first line contains an integer n (2 …

CFR 656 E. Out of Controls ( Python )

Problem - E - Codeforces題意: 給一個 N * N 的鄰接矩陣表示 ( i, j ) 間的邊的距離。問最遠點對的距離為何。 但是,規定不能用類如 for, while, repeat 等關鍵詞 ( 詳見題目本身 )。資料規模: The first line of the input contains a single integer N …

CFR 656 B. Scrambled ( Math, Periodic, Python )

Problem - B - Codeforces題意: 這是愚人節題,瓶頸貌似是在要花點時間把這稍微被打亂的文章看完。 總之題意就是給 M, R,問 [ 0, ∞ ] 這些整數中,有多少百分比的 d 對任意一個 0 ≤ i 資料規模: N, MAXM, MAXR ≤ 16解法: 顯然會以 LCM 為單位形成週期。…