0w1

Yuki

Yuki 301 サイコロで確率問題 (1)

Problem Description: You have a dice with 6 faces, mapping to integer in 1..6. You roll the dice, and sum up them along the process. However, you will reset the sum to 0, when the sum has exceeded N. Find the expected number of rolls you h…

Yuki 550 夏休みの思い出(1)

Problem Description: Solve f(x) = x * x * x + A * x * x + B * x + C, given A, B, and C. Output the solutions in increasing order.Constraints: -1e18 -1e9 It is guaranteed that there are exactly 3 distinct solutionsSolution: pekempey showed …

Yuki 546 オンリー・ワン

Problem Description: Given N numbers as C[0...N], L, and H, find the number of values in range [L, H] that is multiple of exactly one value in C.Constraints: 1 ≤ N ≤ 10 1 ≤ C[i] ≤ 1e9 1 ≤ L ≤ H ≤ 1e9Solution: Solve for (L' = 1, H' = H) and…

Yuki 599 回文かい

Problem Description: You are given a string S. You are requested to split it into some substrings, and suppose you decompose it into k substring as , then must hold for each . You are interested in knowing the number of ways to decompose t…

Yuki 612 Move on grid

Problem Description: Initially you are at coordinate (0, 0, 0). At each second, you have equal probability to move yourself with vector (-a, 0, 0), (a, 0, 0), (0, -b, 0), (0, b, 0), (0, 0, -c), (0, 0, c). Given t, a, b, c, d, e, and let p …

Yuki 615 集合に分けよう

Problem Description: There is a set of N numbers. You would like to split the set into K non-empty subsets, so that the sum of contribution of each subset is minimal. Contribution of a subset can be computed as the absolute difference betw…

Yuki 616 へんなソート

Problem Description: You are given an array A with length N. You have a weird "sorting" algorithm, the output is non-deterministic, but we know that it must be some arrangement of the input array, and contains no more than K inversions. Fi…

Yuki 626 Randomized 01 Knapsack

Problem Description: 0/1 Knapsack problem. Test cases are generated at complete randomness.Constraints: 2 ≤ N ≤ 5000 v[i], w[i] is uniformly distributed in range [1, 1e12] 1 ≤ W ≤ 1e12 * NSolution: Branch and Bound. Referenced kimiyuki's b…

Yuki 589 Counting Even

Problem Description: Given a non-negative integer N, find the number of i, such that C(N, i) % 2 == 0 and 0 ≤ i ≤ N.Constraints: 0 ≤ N ≤ 1e18Solution: According Lucas's theorem, since we are considering modulo 2, we can observe that i can …

Yuki 125 悪の花弁

Problem Description: There are K kinds of colors, each with at least one instance of object. There are C[i] number of instances of color i. You are to arrange them into a ring, and you want to know how many different kinds of rings could b…

Yuki 42 貯金箱の溜息

Problem Description: There are 6 kinds of coins, with units 1, 5, 10, 50, 100, 500, respectively. You have infinite number of each of them. You are to deal with T test cases, and in each case you will be given a value M, where you should o…

Yuki 514 宝探し3 ( Ad hoc, Interactive )

No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…

Yuki 470 Inverse S+T Problem ( 2SAT, Dummy Constraints )

No.470 Inverse S+T Problem - yukicoder題意: 給定 N 個長度為三的字串,求一種分割,使得每個字串被分為兩個非空子字串,且不存在重複的字串。制約: N ≤ 1e5 sigma: { 'a'~'z', 'A'~'Z' }解法: 注意到當 N > | sigma | 時,一定無解,所以 N 可以視作 ≤…

Yuki 230 Splarraay スプラレェーイ ( bitset )

No.230 Splarraay スプラレェーイ - yukicoder題意: 初始時有一個長度為 N 的陣列。現在 a, b 兩人玩遊戲,有 Q 個操作依序被進行,第 i 個操作可以用 ( x[ i ], l[ i ], r[ i ] ) 描述: x = 0 : 令 ca 為 arr[ l, r ] 中 a 塗色數,cb 為 arr[ l, r ] 中 b 塗色…

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,問最大幸…

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 的圖案…

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 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

Yuki 243 出席番号(2) ( DP, Inclusion Exclusion )

No.243 出席番号(2) - yukicoder題意: 有 N 位可分別的學生,現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數,對 1e9 + 7 取模。資料規模: 生徒の数Nが最初の行で与えられる。1≤N≤500…

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

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

Yuki 210 探し物はどこですか? ( Expectation, Priority Queue )

No.210 探し物はどこですか? - yukicoder題意: 有若干個房間,我們想找到一個藏在某處的寶物,而每個房間有寶物的機率為 P / 1000,如果該房間確實有寶物,則每次檢查這個房間會找到寶物的機率為 Q / 100。求最佳檢查順序下,能找到寶物的最小期望檢查次數…

Yuki 412 花火大会 ( DP )

No.412 花火大会 - yukicoder題意: 有三個人分別要 R[ 0 ], R[ 1 ], R[ 2 ] 以上面積的一塊布料。現在有若干個布料,求有多少種帶布料的方法,能滿足三個人的需要。資料規模: 布料數 1≤N≤30 布料大小 1≤Ei≤100 時限 2000 ms 記憶體 512 MB解法: 想省去討…

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

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

Yuki 416 旅行会社 ( Union Find, Smaller to Larger, Time Reverse )

No.416 旅行会社 - yukicoder題意: 給一個圖,和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點,求哪一次破壞後無法從 0 達到。若一開始就不能到達,輸出 0,若破壞完依然能到達,輸出 -1。資料規模: 節點數 2≤N≤1e5 初始橋的數量 1≤M≤2e…