Python
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…
Problem - 622D - Codeforces題意： 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列，使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約： 1 ≤ N ≤ 5e5解法： 看解說，覺得非常神祕，遇到類似題應該還是不會。 主要想法是這樣，猜測可以直接…
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().…
https://www.hackerrank.com/contests/capture-the-flag/challenges/secret-key与えられたリンクに入る。 ソース読む。 secret.js を呼ぶ事に気づく。 それを読んで、key.json を dict としてパスコード承認の動作をしているとわかる。 url の末尾を key.jso…
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。時間 / 空間複雜度…
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…
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 につ…
Problem - E - Codeforces題意： 你在玩遊戲，一場有三種結果，勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時，會立刻退出遊戲。現在你有一個序列描述 N 場遊戲，而你知道你打完這 N 場後退出。有些紀錄被塗成 '?'，要你復原出一個合理…
Problem - D - Codeforces題意： 要求在 K 行以內，用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭，也不會有連續的 '-' 或是連續的空白。制約： The first line contains number k (1 ≤ k ≤ 1e5). T…
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 …
No.162 8020運動 - yukicoder題意： 你上下各有一排 14 個連續的牙齒。 你現在 A 歲，你想知道你在 80 歲時，期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法： 考慮動態規劃： dp[ i ][ j ][ k ] : 經過 i …
No.361 門松ゲーム2 - yukicoder題意： 一開始有一個長度 L 單位的棒子。輪流操作，操作要選擇一個棒子，砍成三個不同長度的棒子，令這三個棒子的長度為 L1, L2, L3，則必須滿足： max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D 先不能操作的人輸，問誰贏。制…
No.421 しろくろチョコレート - yukicoder題意： 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了，用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100，每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10，隨便吃一塊會得到幸福值 1，問最大幸…
Problem - E - Codeforces題意： 給一個數列，對每一個值輸出： 1 if 它不屬於任何一個 LIS 2 if 它屬於某個 LIS，但沒有它也存在相同長度的 LIS 3 if 拔掉它的話 LIS 長度會改變制約： N ≤ 1e5 A ≤ 1e5解法： 用 dp 跟 BIT 的要領求出 st_len[ i ]: 以位置 …
No.409 ダイエット - yukicoder題意： 有 N 天，第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位，你想減肥，所以每天你可以選擇吃或不吃。如果吃了，你的體重就會增加吃掉的重量並歸零壓力值，否則你會減去 A 單位的重量但同時增加一個單…
No.377 背景パターン - yukicoder題意： H * W 格子的壁紙，每個格子有 K 種顏色中一種。這個壁紙由無窮左到無窮右不重疊貼滿，無窮下方至無窮下方也一樣。問牆壁的圖案有多少種，對 1e9 + 7 取模。兩個牆壁的圖案相同若且唯若同時存在相同一個 H * W 的圖案…
Programming Problems and Competitions :: HackerRank題意： 有 N 個線段，用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後，每個線斷所成的圓面積總和為何。制約： 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法： 首先…
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解法： 裸的最優比例生成樹。 聽…
E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder題意： 有一個車子在數線上的原點。目標是 D。依序有 N 個操作，d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ]，但特別地，如果操作後不會接近，則該次操作無…
D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder題意： 兩堆石頭，數量 X, Y。輪流操作，一次選一個正整數的偶數 v，從一個至少有 v 個石頭的堆裡除去，並在另一堆上添加 v / 2 顆石頭。先不能操作的人輸。問雙方最佳操作下誰贏。制約： 0 ≤ X, Y ≤…
C: Sequence - AtCoder Regular Contest 072 | AtCoder題意： 給 N 個數字的數列 A。一次操作選一個數字 +1 或 -1。問最少要幾次操作，才能使得前綴和的正負交替。制約： 2≦n≦1e5 |ai|≦1e9 ai は整数解法： 枚舉開頭是正或負。由左到右確定數字，只有在必要…
Dashboard - Round 1B 2017 - Google Code Jam題意： T 筆測資。有 N 個城市，用相鄰矩陣表示距離，不保證輸入距離滿足三角不等式。每個城市有一隻馬，用可行走距離 E 和最高速度 S 描述。Q 筆詢問，問 u 到 v 的最少時間。詢問之間不互相影響，而在一筆詢問…
Dashboard - Round 1B 2017 - Google Code Jam嗯..? 好像根本就不用二分搜題意： T 筆測資。你在數線上的原點，目的地是 D。除了你現在騎著的馬，一共有 N 隻馬，任兩隻不共享位置的處於某整數位置，並有一個最高速度的屬性描述。當後面的馬追上前面的馬時，…
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 )。制約…
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…
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…
No.489 株に挑戦 - yukicoder題意： 買賣股票，買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約： 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法： 努力寫了一次線段樹，但 python 也很給力的 TLE 了。 經典的滑動視窗： window[ i ]: i …
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解法： 依最小的…
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…
No.496 ワープクリスタル (給料日前編) - yukicoder題意： 你有 N 顆一次性的魔法石頭，第 i 顆可以幫你在 X 軸上 + X[ i ]，Y 軸上 + Y[ i ]，但花費魔力 C[ i ]。你現在在 ( 0, 0 )，你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格，花費 F。…
