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解法: 首先…

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 G. Perfectionist Arkadiy ( Math )

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

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…

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 ] ) …

ARC 071 D - 井井井 ( Math )

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

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 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 …

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

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

AGC 12 D - Colorful Balls ( Math, Combination )

D: Colorful Balls - AtCoder Grand Contest 012 | AtCoder題意: 有若干個球排成一排,第 i 個球用顏色 C[ i ],重量 W[ i ] 描述。可以進行的操作有兩種: 1. 選擇兩個相異位置的相同顏色的球,若它們的重量和不超過 X,將它們交換位置 2. 選擇兩個相異位…

CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces題意: 你的目標濃度是 N / 1000。你有 K 種液體,濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量,求最小正整數,代表使用的總容量成功調配出目標濃度。資料規模: The first line contains two integers n, k (…

CFR 792 E. Colored Balls ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N 種球的個數 A[]。要求按照下列規則將其分箱: 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下,可以用最少…

CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces題意: 給一個長度為 N 的陣列,用顏色描述。要求對於所有 K 資料規模: N ≤ 1e5解法: 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論:「答案的種類大約在 …

POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze題意: 有 N 個工作,假設當前時間已經過 T 單位,那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作,問最短時間完成的工作序列。資料規模: In the first line of the standard input there is…

POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

http://main.edu.pl/en/archive/oi/2/tro題意: 給很多邊的長度,問是否可以構成三角形,可以的話輸出方案。資料規模: In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the nu…

UVA 3716 DNA Regions ( Math )

ACM-ICPC Live Archive題意: 給兩個字串 A 和 B,你要選擇一個 [ L, R ] 使得所有滿足 L ≤ x ≤ R 的 x 都滿足 A[ x ] ≠ B[ x ] 的比率佔長度的 p% 以下。求最長長度。資料規模: N ≤ 1.5e5解法: 考慮對 A[ x ] ≠ B[ x ] 先做前綴和,令前 x 個字符裡相異的…

CFR 257 D. Sum ( Recursion, Math )

Problem - 257D - Codeforces題意: 給數列 a,滿足 a[ i ] ≤ a[ i + 1 ] ≤ 2 * a[ i ]。要求對每項定正負,使得總和介於 [ 0, a[ 0 ] ]。資料規模: The first line contains integer n (1 ≤ n ≤ 1e5) — the size of the array. The second line contains s…

CFR 785 D. Anton and School - 2 ( Math )

Problem - D - Codeforces題意: 給一個亂的括弧序列,求有幾個不同 ( 任一元素來自原本序列的不同下標 ) 的子序列,是個正確的括弧匹配序列,且前半是 '(',後半是 ')'。資料規模: The only line of the input contains a string s — the bracket sequence…

CFR 128 C. Games with Rectangle ( Math )

Problem - 128C - Codeforces題意: 給一個 N * M 的矩形。現在要做 K 次操作,每次需將原本的矩形嚴格變小,但必須邊長都是整數。問方案數對 1e9 + 7 取模。資料規模: 1 ≤ N, M, K ≤ 1000解法: 二維問題很常有的一個技巧,那就是發現兩個維度獨立。 考慮…

CFR 466 B. Wonder Room ( Square root decomposition, Math )

Problem - B - Codeforces題意: 有 n 個人,現有一個 a * b 的土地。可以任意伸長寬和高,希望面積不小於 6 * n 的前提下,面積最小,求最小面積和對應的長寬。資料規模: n, a, b ≤ 1e9 TL: 1000 ms解法: 不失一般性假設 a ≤ b,顯然最佳解的 a 的上界為 …

IOICJ 57 LCM Problem ( Math, Search )

Problem Description: Given N, you want to know max{ LCM(x,y,z), 1≤x,y,z≤N }.Constraints: 1≤T≤1000 1≤n≤1e6Sample Input: 3 7 9 100Sample Output: 210 504 960300Solution: It is obvious that we would like some of the largest x, y, z, such that …

IOICJ 36 Interval Sum EX ( Math, Segment Tree )

Problem Description: You are given an array A wit length N. You need to support these operations, noted with [ p, e, c ]: if p = 0: __square root and discard non-integer value of range [ e, c ] if p = 1: __change value at e to c if p = 2: …

CFR 442 B. Andrey and Problem ( Math, Probability, Greedy )

Problem - B - Codeforces題意: 你有一件事情要完成,但你太懶所以想請你朋友做。你可以同時請很多朋友做,但是如果兩個以上個朋友同時做出來,他們會覺得你把他們當工具人,不特別看待他們。求最佳策略下,可以不讓朋友傷心而完成這項作業的機率是多少。資…

CFR 484 B. Maximum Value ( Math, Binary Search, Harmonic Series )

Problem - 484B - Codeforces題意: 給 N 個數字的數列 A。求最大的 A[ j ] % A[ i ],滿足 A[ j ] ≥ A[ i ]。資料規模: N ≤ 2e5 max{ A } ≤ 1e6解法: 首先發現相同的值是沒有用的,所以 unique() 一下。此時就能因為 Harmonic Series 想到每個數的倍數數…

CFR 303 A. Lucky Permutation Triple ( Math, Modulo )

Problem - 303A - Codeforces題意: 求長度為 N 的三個排列 A, B, C,使得所有 ( A[ i ] + B[ i ] ) % N = C[ i ]。若無解輸出 - 1。資料規模: N ≤ 1e5解法: 先算一下總和:Sigma( i % N, for all 0 ≤ i 時間 / 空間複雜度: O( N ) #include <bits/stdc++.h> using names</bits/stdc++.h>…

CFR 449 A. Jzzhu and Chocolate ( Math, Sqrt Decomposition )

Problem - 449A - Codeforces題意: 給一個 n * m 的巧克力板,要割 k 次,每次只能割還沒割過的整數水平線或鉛直線,求最小的塊面積最大可以為何。測資規模: A single line contains three integers n, m, k (1 ≤ n, m ≤ 1e9; 1 ≤ k ≤ 2e9).解法: 貌似有…

CFR 351 A. Jeff and Rounding ( Ad hoc, Math )

kmjp さんの記事を参考にしました。 Problem - A - Codeforces題意: 給你 2 * N 個數字,要把 N 個數向下取整,另外 N 個數向上取整。問總和的最小變化量是多少。資料規模: The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n …

CFR 235 B. Let's Play Osu! ( DP, Math )

Problem - B - Codeforces題意: 假設有個 OX 序列,每個連續段 'O' 長度若為 x,則該段貢獻為 x^2。已知序列長度,以及分別每個字符為 O 的機率,求期望貢獻和。資料規模: The first line contains an integer n (1 ≤ n ≤ 1e5) — the number of clicks. Th…

CFR 696 C. PLEASE ( Math )

Problem - 696C - Codeforces題意: 給你 K 個數 A[ i ],代表 N = PI{ A[ i ], for all i }。 有三個杯子,一開始中間的杯子裡面有寶物,每回合平等隨機地選左邊的或右邊的杯子,和中間的杯子交換。求 N 回合後,寶物在中間的機率。以分數形式表示,並分別…

CFR 354 C. Vasya and Beautiful Arrays ( Math, Harmonic Series, Number Theory )

Problem - C - Codeforces題意: 給你一個數列,有 N 個元素,再給你一個整數 K。你可以分別將數列中每個元素 a[ i ] 變為 [ max( 1, a[ i ] - K ), a[ i ] ] 中任意一個整數。求變換過的數列的最大可能最大公因數。資料規模: 1 ≤ n ≤ 3e5 1 ≤ k ≤ 1e6 1 ≤ …

Bangladesh OI 2016 National Round pB. Beautiful Factorial Game ( Math )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意: 給 N, K,求 N! 整除 K ^ x 的最大 x 是多少。資料規模: For easy versi…

CFR 7 C. Line ( Extgcd, Math )

http://codeforces.com/contest/7/problem/C題意: 給一個方程式 Ax + By + C = 0,找一組整數 ( x, y ) 在該直線上。或者判斷不存在。解法: 先用 ext_gcd 判斷 Ax + By = gcd( A, B ) 時的 x, y 分別是多少。 ext_gcd 要背!不懂還是要硬背!( 我總是想不…

CFR 251 E. Devu and Birthday Celebration ( Inclusion Exclusion, Number Theory )

Problem - E - Codeforces題意: Q 筆詢問: 有 N 顆糖果要分給 F 個人,每個人至少拿到一顆,但希望每個人的糖果個數的最大公因數為 1。求方法數模上 1e9 + 7。資料規模: 1 ≤ Q ≤ 1e5 1 ≤ F ≤ N ≤ 1e5 時間限制: 5000 ms 空間限制: 256 MB解法: 考慮 N …

Yuki 242 ビンゴゲーム ( Expectation, Math )

No.242 ビンゴゲーム - yukicoder題意: 在 5 * 5 的矩陣玩賓果 ( 縱橫斜連線 ),每個格子都不重複存在一個介於 1 ~ 99 之間的一個整數。求矩陣裡的格子裡的數字都完全隨機,叫出的號碼也都完全隨機的情況下,喊到第 N 個數時,期望有多少連線。資料規模: 1…

Yuki 320 眠れない夜に ( Math, Fibonacci )

No.320 眠れない夜に - yukicoderかなりフィボナッチ数列の勉強になったので、ちょっとノートをします。pekempey さんの記事を参考にしました。ある項目に 1 少なく数えるのは、その項目から と負のフィボナッチ数列を並列して進ませる事と同じで、縦の総和…

Yuki 389 ロジックパズルの組み合わせ ( Combinatorics, Math )

No.389 ロジックパズルの組み合わせ - yukicoder題意: 在一排 M 個格子上放黑色點,依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點,且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。資料規模: 1 ≤ M 0 ≤ H[ i ] SIGMA{ H } ≤ M 保證若有一…

Yuki 403 2^2^2 ( Fast Multiplication, Math, Little Fermat's Theorem )

No.403 2^2^2 - yukicoder自分が pow() の中に普段書いてる res = 1 は間違ってるみたですね。0^n = 0, for all n > 0 ですから。 const int MOD7 = ( int ) 1e9 + 7; ll A, B, C; void init(){ scanf( "%lld^%lld^%lld", &A, &B, &C ); } ll ll_pow( ll v, …

Yuki 152 貯金箱の消失 ( Triangle, Math )

No.152 貯金箱の消失 - yukicoder 直角三角形の辺はそれぞれ x * x + y * y, x * x - y * y, 2 * x * y と表せる。 総和をとると、2 * x * x + 2 * x * y ≤ L が問題の核心だと分かる。 ここで x, y を枚挙。 #include <bits/stdc++.h> using namespace std; signed main(){</bits/stdc++.h>…

Yuki 176 2種類の切手 ( Math, Square Root Decomposition )

No.176 2種類の切手 - yukicoder先に T ≥ lcm( A, B ) させるように余る lcm( A, B ) * k を最大の整数 k で取る。 すると最悪の場合、T = 1e9, max( A, B ) = min( A, B ) = 1e4.5 となる。 しかしここで max( A, B ) を枚挙しても間に合う。 O( sqrt( T ) …

Yuki 53 悪の漸化式 ( 特性方程式, 精度, Math )

No.53 悪の漸化式 - yukicoder 高校数学は忘れないでおきましょう yukicoder No.53 - 悪の漸化式(writer担当) - ゲームにっき(仮)別館(仮) #include <bits/stdc++.h> using namespace std; signed main(){ int N; cin >> N; cout << fixed << setprecision( 10 ) << 4</bits/stdc++.h>…

CFR 201 A. Clear Symmetry ( Ad hoc, Math )

Problem - A - Codeforces題意: 一個方陣,初始所有值為 0,塞 1 進去,1 彼此不相鄰,且最後方陣必須上下、左右分別成對稱。給 1 的數量,求至少要邊長多少的方陣才能塞下。資料規模: 1 的個數 1 ≤ X ≤ 100解法: 先注意到因為必須對稱,奇數邊長的方陣一…

CFR 566 F. Clique in the Divisibility Graph ( DP, Math, Complexity Analysis )

Problem - 566F - Codeforces題意: 給一個嚴格遞增序列。求子序列最長長度,子序列滿足所有相鄰元素對,後一個元素可以被前一個整除。資料規模: 序列長度 1 ≤ N ≤ 1e6 元素大小 1 ≤ A[ i ] ≤ 1e6 時限 1000 ms 記憶體 256 MB解法: 注意到 [ 1, N ] 的數的…

CFR 453 B. Little Pony and Harmony Chest ( bits DP + Math )

Problem - B - Codeforces 題意: 給一個序列 A,要你求一個相同長度的 B 序列,使 B 序列中任意兩個數字皆互質,此前提下 SIGMA{ abs( A[ i ] - B[ i ] ) } 最小。輸出 B 的長相。 解法: A 最大只會有 30,可以證明 B 只需考慮 [ 1, 60 ] 內的數。因為如果…

HR Find the Seed ( DP + Matrix Inverse - Gauss Elimination )

https://www.hackerrank.com/challenges/find-the-seed F( n ) = c( 1 ) * F( n - 1 ) + c( 2 ) * F( n - 2 ) .. + c( n ) * F( 0 ) => c( n ) * F( 0 ) = F( n ) - c( 1 ) * F( n - 1 ) - c( 2 ) * F( n - 2 ) .. - c( n - 1 ) * F( 1 ) => F( 0 ) = invers…

HE April Circuits 3A - Bear and Vectors ( Math )

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vectors/ Two vectors v1( a1, b1 ), v2( a2, b2 ) are perpendicular to each other iff ( v1 dot v2 ) = a1 * a2 + b1 * b2 = 0. And since ( ka, kb ) = k( a, b ) is parallel to (…

HE April Circuits 2A - Bear and All Permutations ( Bigint )

https://www.hackerearth.com/april-circuits/algorithm/2a-bear-and-all-permutations-1/ We can simply simulate for each answer since n is only up to 12. However, it still takes a lot of time, and the number is extremely large, we will have to…

HE April Circuits 1A - Bear and Vowels ( Simulation )

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vowels-2/ Simply simulate as the description provides. #include <bits/stdc++.h> using namespace std; const int MAXS = 50 + 2; const string vowel = "aeiouy"; string s; void solve(){ int vo</bits/stdc++.h>…

CFR Educational 12 D. Simple Subset ( Math + Adhoc )

Problem - D - Codeforces 2 elements with same value should never co-exist since it will be an even number, which will not be a prime number when summed, unless they were both 1. 2 even numbers nor 2 odd numbers can not co-exist as well. So…