0w1

Atcoder

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…