Tamflexの貯蔵庫

やる気のない備忘録

atcoder

arc 059

arc059.contest.atcoder.jp 飴が個,人がのときの答えをとおけば以下の漸化式が成立する。 の部分は最初に計算しておいてのオーダで計算できて結局時間計算量は template <long long modulo> class Modulo { private: long long pow(long long q) { long long a=1; long long y=</long>…

abc 040

abc040.contest.atcoder.jp解説を勉強してみた トポロジカルソートの場合の数の算出をbitDPを用いてO(n!)をO(m2^n)にする問題 (頂点集合Sとおいた時のルートの要素数) とおけば以下の漸化式で求まる ただし からへの辺が存在しない 集合をbit列で表し小さい…

abc 040

abc040.contest.atcoder.jpunion findを使いましょう. 新しい道からどんどん素集合データ構造を更新して行って,その時の各クエリが要求するノードが含まれる集合の濃度(要素数)を記憶,あとで出力すればとける. unionfind自体は知っていてなんとなく使う気が…

abc 039

abc039.contest.atcoder.jp白の周囲を白にして、その後黒の周囲を黒にして元に戻るか判定する. int h,w; int a[100][100]; int b[100][100]; int c[100][100]; bool range(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w; } int main() { cin >…

abc 037

abc037.contest.atcoder.jp DPの問題. 点を始点とする場合の数はその点の周囲のマス+1になる.あとは再帰的に計算してメモ化すればできる. ll T[1010][1010]; ll dp[1010][1010]; int h, w; ll f(int x, int y, ll p) { if(x<0||x>=h||y<0||y>=w) return 0; i…

abc 038

LISの二次元バージョン.x座標でソートしてy座標のLISを求めればいい ここでうまいと思ったのはy座標を負にすること. 問題では狭義単調増加の最長増加列を求めさせているので,x座標が同じだと条件に合わない. そこで負にすることで絶対値が大きい順に並べこれ…

arc 051

arc051.contest.atcoder.jp A問題 円の中心が長方形の内側か外側にあるかで場合分けすれば解けます. int main() { P p; double r; cin>>p.x>>p.y>>r; P q1,q2; cin>>q1.x>>q1.y>>q2.x>>q2.y; P q = (q1+q2)/2; P q3(q1.x,q2.y); P q4(q2.x,q1.y); bool red, …

abc 034

c問題 abc034.contest.atcoder.jp前にやった剰余のやつ. フェルマーの小定理を用いて逆元を求める. template <long long modulo> class Modulo { private: long long inv() { long long p = mod - 2; long long ans = 1; for(;p != 0;p >>= 1LL) { if(p&1LL)ans=(ans * x) % mo</long>…

abc 033

abc033.contest.atcoder.jp解説が詳しい 各点からすべての点への線分を考え角度を求める. 角度を求めた後, 鈍角と直角の数を数える. ここでミソなのはx軸のx特異点)でこれはすべての角度に2πを足して二分探索すればとける. int main() { ll n; cin >> n; ll …

abc 036

d問題 abc036.contest.atcoder.jpdfsとメモ再帰化でできる…はずだったのにlonglongとintを使い間違えて無事終了 #include <bits/stdc++.h> #define SIZE 300005 #define MOD 1000000007LL #define INF 1 << 29 #define LLINF 1LL << 60 #define REP(i,n) for(int i=0;i</bits/stdc++.h>

abc 032

D問題 N void solve1() { int n1 = N/2; int n2 = (N + 1)/2; vector<pair<ll,ll> > a; REP(i,1<</pair<ll,ll>

abc 019

D問題 abc019.contest.atcoder.jpdouble sweepというアルゴリズムを用いる(らしい) 任意の頂点から最も離れた頂点をとした場合、木の直径はから最も離れた頂点までの距離となる。背理法によって簡単に示せる。 これによって回の検索で直径が計算される。 int…

abc 020

D問題 abc020.contest.atcoder.jp を求めよ。 15点解法 ll gcd(ll x, ll y) { if(x == 0 || y == 0) return max(x,y); ll a = max(x,y); ll b = min(x,y); return gcd(a%b,b); } ll lcm(ll x, ll y) { return x * y / gcd(x,y); } int main() { cin.tie(0); …

abc 021

D問題 abc021.contest.atcoder.jp 99点解法 計算量 int n, k; ll dp[10010][10010]; int main() { cin.tie(0); ios::sync_with_stdio(false); // FROM HERE cin >> n >> k; RREP(i,0,n) dp[0][i] = 1LL; RREP(i,1,k) RREP(j,1,n) dp[i][j] = (dp[i-1][j] + d…

abc 031

D問題 abc031.contest.atcoder.jp数字iがa[i-1]の長さの文字列に対応しているとして、深さ優先探索で解く。最大9種類のパターンに対しそれぞれ最大3文字なので3^9 = 19683通りしかないので時間内に解けそう。判定はそれぞれのデータセット(v,w)に対して Σ{i …