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

Dashboard - Qualification Round 2017 - Google Code Jam題意： 給 N * N 的棋盤，以及一些士兵。士兵有三種 : { 'x', '+', 'o' }，若沒有士兵用 '.' 描述。一個格子至多一個士兵。士兵配置的規則如下： 1. 任意兩個在同個水平或鉛直線上的士兵，必須有其中…

Dashboard - Qualification Round 2017 - Google Code Jam題意： 有 N 個空間排成一排，有 K 個人依序決定自己要進哪個空間。令一個空間 i 的左邊連續空房間的數量為 L[ i ]，右邊連續空房間的數量為 R[ i ]，那麼任何人都會優先考慮 min( L[ i ], R[ i ] ) …

Dashboard - Qualification Round 2017 - Google Code Jam題意： 問不超過 N 的最大的，以十進制表示時，由左到右檢視，數字呈非遞減的數為何。制約： 1 ≤ T ≤ 100. 1 ≤ N ≤ 1e18. 解法： 一開始寫數位統計 dp 寫到快哭出來。 仔細想想，只要倒著決定就可以…

Dashboard - Qualification Round 2017 - Google Code Jam題意： 給一個由 '+', '-' 組成的序列。問能不能透過任意次操作將該序列全部元素變成 '+'。操作只有一種，將連續 K 個元素內容反轉。制約： 1 ≤ T ≤ 100. Every character in S is either + or -. 2 …

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

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

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

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

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

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

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

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

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

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

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

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

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…

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

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

Problem - C - Codeforces題意： 給一個長度為 N 的數列，要做 K 次操作。每次將數列排序後，奇數項 ( 1 based ) 和 X 做 xor，偶數項不變。問所有操作結束後，數列的長相。資料規模： First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤…

題意： 有些整數點上有朋友，每個朋友有個最高速率。問所有朋友集結到任意實數點需要的最短時間。資料規模： The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends. The second line contains n integers x1, x2, ..., xn (1…

Problem - C - Codeforces題意： 給一個 N * M 的矩陣。K 筆詢問，每次問 [ L, R ] 範圍的行是否存在一個列，使得在 [ L, R ] 之間為非遞減。資料規模： The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the num…

除了細節稍做改良之外，提供路徑打印模式，有答案便能快速給出路徑。現在配合人腦，勉強能解出5 * 5。 還有些功能正在思考怎麼實作比較好： 像是若知道某些字串存在，但不知道何時何地使用，是否能做合理的剪枝。 也該做某種東西顯示它大略的進度，否則還要…

因為不可能讓程式自己獨立解出答案，改成可以支持各種操作的方式輔助縮減答案範圍，再用人腦解決。 第二次寫就好很多了，語法也比較熟悉。 這個版本支持輸入 $表示空的格子，也能指定遞迴深度，還有事先寫好哪些字是禁用的。利用的剪枝還是比較基礎，對於需…

Brain Word Puzzle - Google Play の Android アプリ WordBrain on the App Store 這是一個文字遊戲，前面的關卡都是一個 4 * 3 的矩陣，每個格子裡有一個字母。會給兩個長度，相加等於 12，第一次操作要選擇一個字母當起點，然後移動到尚未拜訪的周圍八格其…