Subscribed unsubscribe Subscribe Subscribe

0w1

Atcoder

ARC 073 F - Many Moves ( DP, Segment Tree )

F: Many Moves - AtCoder Regular Contest 073 | AtCoder題意: 在一個一維的棋盤上,你有兩顆棋,一顆在 A 位置,另一顆在 B 位置。有 Q 次操作,第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後,可…

ARC 073 E - Ball Coloring ( Greedy )

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個箱子,裡面有兩個球,球有各自的重量。對於每個箱子,都需要將其中一顆球放到袋子 A,另一顆放到袋子 B。一個袋子的價值是其中最大的重量和最小的重量的差。求最小的價值乘積。制約…

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

ARC 072 F - Dam ( Greedy, Monotonous, Deque )

F: Dam - AtCoder Regular Contest 072 | AtCoder題意: 有一個水壩,容量是 L。有 N 天,第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩,晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i,問使得第 i 天恰有容量 L 的水在水壩…

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 は整数解法: 枚舉開頭是正或負。由左到右確定數字,只有在必要…

ARC 071 F - Infinite Sequence ( DP )

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder題意: 問有多少無窮長度數列 A[] 滿足: 1. i 的下一個元素開始連續 A[ i ] 個皆相同 2. 對所有的 N ≤ i, j,A[ i ] = A[ j ] 輸出答案對 1e9 + 7 取模。制約: 1≤n≤1e6 n は整数解法: 首先…

ARC 071 D - 井井井 ( Math )

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

ARC 071 E - TrBBnsformBBtion ( Ad hoc )

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder題意: 給字串 S, T。Q 筆詢問,指定 S 的某個子字串 S', T 的某個子字串 T',問是否能透過施行以下操作任意次由 S' 轉換為 T'。 1. 將 'A' 換成 "BB" 2. 將 'B' 換成 "AA" 3. 將 "AAA" 換成 "…

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

AGC 12 D - Colorful Balls ( Math, Combination )

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

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

ARC 065 D - 連結 ( Ad hoc )

D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意: 給相同節點數的兩個圖,對於每個點,求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模: 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…

ARC 064 D - An Ordinary Game ( Ad hoc, Game Theory )

D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder題意: 給一個字串,每次可選取非兩端的任意字元使其消失,但前提是消失後不能有任意兩個相鄰字元相同。兩個人輪流做,先不能做的輸,求誰贏。資料規模: 3 ≤ | S | ≤ 1e5解法: 考慮最終狀態的…

ARC 003 D - シャッフル席替え ( Monte Carlo, Hoeffdings Inequality )

D: シャッフル席替え - AtCoder Regular Contest 003 | AtCoder ARC#003D from nullmineral www.slideshare.net かなりわかりやすいスライドですが、覚えておきたいものをメモ: Hoeffdings Inequality ● X1, X2, …, Xn を独立な Bernoulli 確率変数とする ●…

ABC 036 D - 塗り絵 ( Tree DP )

D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder dp[ u ][ j ] : the number of valid combinations, when now on node u ( not yet colored ), and its father is white / black dp[ u ][ j ] = product( dp[ v ][ 0 ] ) + product( dp[ v ][ 1 ] ) * …

ABC 4 D - マーブル ( DP )

D: マーブル - AtCoder Beginner Contest 004 | AtCoder #include <bits/stdc++.h> using namespace std; const int MAXR = 300 + 2; const int MAXC = 300 + 2; const int MAXB = 300 + 2; const int INF = 0x3f3f3f3f; #define rep( i, a ) for(int i = 0; i < (int)( a )</bits/stdc++.h>…

ABC 3 D - AtCoder社の冬 ( DP )

D: AtCoder社の冬 - AtCoder Beginner Contest 003 | AtCoder torus711さんの解き方( DPは想定解ではない模様 )が勉強になりました。ありがとうございます。 torus711.hatenablog.com X * Y の小長方形をDPで方法数を求めます、その小長方形が条件を満たす様…

ABC 26 D - 高橋君ボール1号 ( Binary search + EPS )

D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder 精度が怖い。 出力するものがたとえ1e-10の誤差だけあったとしても関数が出るものに1e-5ぐらい影響がまだるので、ちゃんと限界まで行かないとやばい。 #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…

ABC 32 D - ナップサック問題 ( 01Knapsack, 3 solutions )

D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder いい練習になった。 #include <bits/stdc++.h> using namespace std; const int MAXN = 200 + 5; typedef long long ll; typedef pair<ll, ll> pll; int n, c; int v[ MAXN ], w[ MAXN ]; void solve1(){ // n <= 30 </ll,></bits/stdc++.h>…

ABC 32 C - 列 ( Crawling / log() / Segment Tree )

C: 列 - AtCoder Beginner Contest 032 | AtCoder Crawling. O( n ). #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e9 + 9; typedef long long ll; int n, k; int s[ MAXN ]; void solve(){ if( count( s, s + n, 0 ) ){ pr</bits/stdc++.h>…

ABC 27 D - ロボット ( Adhoc )

D: ロボット - AtCoder Beginner Contest 027 | AtCoder 各Mについて右、左のどちらにすすむかをいちいち決めるとやばい。そもそもそれを早くする方法もあまり考えられない。しかしよく考えると、右に移動と決めたら、移動しないと比べて全体的に 右にある +…

ABC 29 D - 1 ( 桁DP )

D: 1 - AtCoder Beginner Contest 029 | AtCoder 桁DP は応用が利くなぁー(満足) #include <bits/stdc++.h> using namespace std; const int MAXN = 1e9 + 9; const int MAXP = 10; typedef unsigned long long ull; #define rep( i, a ) for(int i = 0; i < (int)( a ); </bits/stdc++.h>…

ABC 27 C - 倍々ゲーム ( Game theory, Adhoc )

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder abc027 from AtCoder Inc. www.slideshare.net ちょっと面白かった。説明はスライドの図を見た方がわかりやすい。こういったアプローチは幾つか選択肢木を描いて考察した方がでやすいですね。 #incl…

ABC 22 D - Big Bang ( Geometry, Centroid )

http://abc022.contest.atcoder.jp/tasks/abc022_d Problem Statement: Given n ≤ 1e5 points in a 2D plane, it is then rotated, moved by the whole picture, and enlarged p times from its center. Find p. There are a few ways to solve this problem…

ABC 22 C - Blue Bird ( Floyd Warshall )

C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder Problem Statement: Given a graph of n ≤ 300 nodes and some edges, find the minimum weight sum of a cycle that starts from 1, goes to some other nodes and end in 1. Basically, we will be…

ABC 9 D - 漸化式 ( Fast matrix multiplication + XOR / AND property )

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder I was surprised that this could be matrix multiplication as well. Abc009 from AtCoder Inc. www.slideshare.net According to the slides, when the operation has property of 0, commutative rul…

ABC 23 D - 射撃王 ( Binary search )

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder Search for the minimum height that is possible. Judge by the deadline, which should be pre-calculated and sorted. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXH = </bits/stdc++.h>…

ABC 21 C - 正直者の高橋くん ( Dijkstra + DP )

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder 経路数の計算、dijkstra を一回やって disをたどりながら dpするだけだね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; const int MAXM = 200 + 2; const int MOD = 1e9 + 7;</bits/stdc++.h>…

ABC 17 C - ハイスコア ( Imosu or Segment Tree )

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder Basically we would like to find the element that is covered with the least cost. It is intuitive to use segment tree, but actually we could use imosu algorithm to maintain the differen…

ABC 15 D - 高橋くんの苦悩 ( 01Knapsack DP )

D: 高橋くんの苦悩 - AtCoder Beginner Contest 015 | AtCoder ただのナップサック。一回しか使えないという条件があれば、枚挙の順序は逆にして同じものが複数回更新に使われないように注意すること。 #include <bits/stdc++.h> using namespace std; const int MAXW = 1e4</bits/stdc++.h>…

ABC 14 D - 閉路 ( Doubling LCA )

D: 閉路 - AtCoder Beginner Contest 014 | AtCoder A small practice for doubling LCA. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXQ = 1e5 + 5; const int LGN = 20; // 2 ^ 19 > 1e5 int n; vector<int> G[ MAXN ]; // connects</int></bits/stdc++.h>…

ABC 14 C - AtColor ( Imosu + Discretization )

C: AtColor - AtCoder Beginner Contest 014 | AtCoder Problem Statement: Given n ranges [ a[ i ], b[ i ] ], find the maximum covered count of any point. We can use imosu algorithm, where we maintain the value of difference for two adjacent v…

ABC 13 D - 阿弥陀 ( Doubling )

D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder Without the variable D, we can simulate the process by swapping the numbers where edges exist, since making an edge on the bottom is equivalent to swapping the index of the two lines. We c…

ABC 11 D - 大ジャンプ ( Probability )

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder Problem Statement: Given n: number of jumps, d: distance of each jump, find the probability to land in coordinate ( x, y ) when n jumps are made arbitrarily. We will first get rid of d…

ABC 8 D - 金塊ゲーム ( DP )

D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoder Let dp[ i ][ j ][ k ][ l ]: maximum score for rectangle upper left ( i, j ) lower right ( k, l ) ( taken from AtCoder Beginner Contest 008 解説 ) we can split the problem into four sub…

ABC 8 C - コイン ( Expectation )

C: コイン - AtCoder Beginner Contest 008 | AtCoder Problem statement: Given some coins and their value, initially they are in any random permutation, all heads facing up. You will flip each coin from left to right, and every time a coin is…