0w1

Atcoder

ARC 039 C - 幼稚園児高橋君

Problem Description: You are on an infinitely large grid. Initially you are at coordinate (0, 0). You would move towards of the four directions (URDL) each unit of time, and stop at the first integer coordinate that had not yet been visite…

ARC 039 D - 旅行会社高橋君

Problem Description: You have a graph with N vertices, M edges. You are then given Q queries, each denoted by three indexes of nodes, A, B, and C. For every such query, you need to output whether it is possible to visit node A, B, and C, i…

ARC 074 F - Lotus Leaves ( Flow, Mincut )

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder題意: H * W 的棋盤。 起點 S,終點 T。這兩個點都有葉子。 其他葉子用 'o' 描述。 每次可以選擇同行或同列的 'o' 移動到那裡。 問最少要移除多少葉子才能使 S 不能到達 T。無解輸出 -1。制約: 2≤…

ARC 074 E - RGB Sequence ( DP )

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder題意: N 個格子一排。 有三種顏色可以塗。 M 條限制,表示 [ L, R ] 中要有 X 種顏色。 求方案數模 1e9 + 7。制約: 1≤N≤300 1≤M≤300 1≤li≤ri≤N 1≤xi≤3解法: dp[ i ][ j ][ k ]:第 { 1, 2, 3 } …

ARC 074 D - 3N Numbers ( Segment Tree )

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder題意: 給長度 3 * N 的數列 A[]。刪除 N 個元素後,希望前 N 個元素總和 - 後 N 個元素總和最大。制約: N ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法: 考慮一條線,從 N 掃描到 2 * N。 這條線會將數列分成兩塊,…

ARC 074 C - Chocolate Bar ( Ad hoc )

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder題意: 把巧克力沿著線切,分成三個非空的塊。 問最大和最小的塊的面積差最小是多少。制約: 2 ≤ H, W ≤ 1e5解法: 只可能有兩種切法 | | | 或 | -。90 度旋轉再做一樣的事情。 第一刀切下去之後顯…

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について右、左のどちらにすすむかをいちいち決めるとやばい。そもそもそれを早くする方法もあまり考えられない。しかしよく考えると、右に移動と決めたら、移動しないと比べて全体的に 右にある +…