0w1

Python

CFR 806 A. Success Rate ( Math, Extended GCD )

Problem - A - Codeforces題意: 你現在寫了 y 個題目,答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。制約: The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the next t l…

CFR 622 D. Optimal Number Permutation ( Ad hoc )

Problem - 622D - Codeforces題意: 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約: 1 ≤ N ≤ 5e5解法: 看解說,覺得非常神祕,遇到類似題應該還是不會。 主要想法是這樣,猜測可以直接…

CTF HR Infinite Links ( Web Crawler )

https://www.hackerrank.com/contests/capture-the-flag/challenges/infinite-links簡単な Web Crawler を書くだけ。 import urllib.request from queue import Queue def retrieve_msg_links( link ): line = list( urllib.request.urlopen( link ).read().…

CTF HR Secret Key

https://www.hackerrank.com/contests/capture-the-flag/challenges/secret-key与えられたリンクに入る。 ソース読む。 secret.js を呼ぶ事に気づく。 それを読んで、key.json を dict としてパスコード承認の動作をしているとわかる。 url の末尾を key.jso…

HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意: 給 N 個元素,問最小的 x ,使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約: 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法: 經典題,開 log 比較,二分搜 x。時間 / 空間複雜度…

CFR 803 F. Coprime Subsequences ( Inclusion Exclusion, Math, Sieve )

Problem - F - Codeforces題意: 給 N 個元素的數列 A。問有幾種不同的非空子序列,其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約: The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

ARC 073 D - Simple Knapsack ( DP )

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個物品要做 01 背包問題。背包容量 W,要求價值最大。注意有個特殊限制:所有物品的容量和第一個物品的容量的差不超過 3。制約: 1≦N≦100 1≦W≦1e9 1≦wi≦1e9 すべての i=2,3,…,N につ…

CFR 803 E. Roma and Poker ( DP )

Problem - E - Codeforces題意: 你在玩遊戲,一場有三種結果,勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時,會立刻退出遊戲。現在你有一個序列描述 N 場遊戲,而你知道你打完這 N 場後退出。有些紀錄被塗成 '?',要你復原出一個合理…

CFR 803 D. Magazine Ad ( Binary Search )

Problem - D - Codeforces題意: 要求在 K 行以內,用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭,也不會有連續的 '-' 或是連續的空白。制約: The first line contains number k (1 ≤ k ≤ 1e5). T…

CFR 803 B. Distances to Zero ( Ad hoc )

Problem - B - Codeforces題意: 給一個數列,其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。制約: The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array …

Yuki 162 8020運動 ( DP )

No.162 8020運動 - yukicoder題意: 你上下各有一排 14 個連續的牙齒。 你現在 A 歲,你想知道你在 80 歲時,期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法: 考慮動態規劃: dp[ i ][ j ][ k ] : 經過 i …

Yuki 361 門松ゲーム2 ( SG, Game Theory )

No.361 門松ゲーム2 - yukicoder題意: 一開始有一個長度 L 單位的棒子。輪流操作,操作要選擇一個棒子,砍成三個不同長度的棒子,令這三個棒子的長度為 L1, L2, L3,則必須滿足: max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D 先不能操作的人輸,問誰贏。制…

Yuki 421 しろくろチョコレート ( Greedy, Maximum Bipartite Matching )

No.421 しろくろチョコレート - yukicoder題意: 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了,用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100,每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10,隨便吃一塊會得到幸福值 1,問最大幸…

CFR 486 E. LIS of Sequence ( DP, Fenwick Tree )

Problem - E - Codeforces題意: 給一個數列,對每一個值輸出: 1 if 它不屬於任何一個 LIS 2 if 它屬於某個 LIS,但沒有它也存在相同長度的 LIS 3 if 拔掉它的話 LIS 長度會改變制約: N ≤ 1e5 A ≤ 1e5解法: 用 dp 跟 BIT 的要領求出 st_len[ i ]: 以位置 …

Yuki 409 ダイエット ( Decision Monotonous, DP )

No.409 ダイエット - yukicoder題意: 有 N 天,第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位,你想減肥,所以每天你可以選擇吃或不吃。如果吃了,你的體重就會增加吃掉的重量並歸零壓力值,否則你會減去 A 單位的重量但同時增加一個單…

Yuki 377 背景パターン ( Burnside Lemma, Math )

No.377 背景パターン - yukicoder題意: H * W 格子的壁紙,每個格子有 K 種顏色中一種。這個壁紙由無窮左到無窮右不重疊貼滿,無窮下方至無窮下方也一樣。問牆壁的圖案有多少種,對 1e9 + 7 取模。兩個牆壁的圖案相同若且唯若同時存在相同一個 H * W 的圖案…

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

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 C - 怪文書 ( Greedy )

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

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

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 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 為單位形成週期。…

CFR 525 E. Anya and Cubes ( Search )

Problem - E - Codeforces題意: 給 N 個數字的數列 A[]。你可以選至多 K 個數字,將它們變成自己的階乘,這個操作對同一個元素只能使用一次。問有幾種方法可以得到一個子集合,其總和恰為 S。兩種方法相同若且唯若集合相同且施加的操作相同。資料規模: The…

AGC 12 C - Tautonym Puzzle ( Binary Enumeration )

C: Tautonym Puzzle - AtCoder Grand Contest 012 | AtCoder題意: 要求構造一個字串 S,使得 S 有洽 N 個偶數長度 ( ≥ 2 ) 的子序列,使得子序列前半等於子序列後半。資料規模: 1≦|s|≦200 s は 1 から 100 までの整数で表される 100 種類の文字のみからな…

AGC 12 B - Splatter Painting ( BFS )

B: Splatter Painting - AtCoder Grand Contest 012 | AtCoder題意: 給一張圖,以及 Q 次操作,每次操作將離 u 距離 d 內的所有節點塗色為 c。初始時每個節點顏色為 0。問所有操作結束後,每個節點分別顏色是什麼。資料規模: 1≦N,M,Q≦1e5 1≦ai,bi,vi≦N ai≠…

CFR 44 E. Anfisa the Monkey ( Greedy )

Problem - 44E - Codeforces題意: 給 K, A, B,以及一個字串 S。要求輸出方案,使得將 S 分為 K 個子字串,滿足所有子字串長度在 [ A, B ] 之間。資料規模: The first line contains three integers k, a and b (1 ≤ k ≤ 200, 1 ≤ a ≤ b ≤ 200). The secon…

CFR 768 D. Jon and Orbs ( DP, Probability )

Problem - D - Codeforces題意: 有 K 種卡片,每天都可以抽一張,抽到的種類機率分佈是隨機均勻。Q 筆詢問,問第幾天開始可以確定,對於任意一種卡片,有 P / 2000 的機率有至少一張。資料規模: First line consists of two space separated integers k, q…

CFR 552 E. Vanya and Brackets ( Greedy, Expression Parsing, Python )

Problem - E - Codeforces題意: 給一個由 '+', '*', '0' ~ '9' 組成的合法數式,要求在任意合法的位置插入一對括弧,求最大可能結果。資料規模: The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digi…