読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

循環少数のプログラム

フロイドの循環検出法 - Wikipedia これを使うらしい int f(int n) { int p = 1, q = 1; int s = 0, t = 0; // start : s, goal : t while(1) { p = (p*10)%n; q = (q*10)%n; q = (q*10)%n; if(p==q) break; } if(p!=0) { q = 1; s = 1; while(p!=q) { s++; …

abc 040

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

codeIQ 2529

codeiq.jpf,gは割と簡単だけど,hが面倒. #include <bits/stdc++.h> #define EPS 1e-10 ll power(ll x,ll n){ll a=1;REP(i,n)a*=x;return a;} ll f(double a, double b, double c, double d) { double e = 180-(b+c+d); double f = 180-(a+b+c); a *= M_PI/180; b *= M_PI/18</bits/stdc++.h>…

codeIQ 2717

dfsで全探索する. int n; vector<int> a; int dfs(int k, int sum) { if(k==a.size()) return sum; int x = dfs(k+1,sum+a[k]); int y = dfs(k+1,sum); return abs(n-x)<abs(n-y)? x : y; } int main() { int t; cin >> n; while(cin >> t) a.push_back(t); sort(a.begin(),a.end()); cout << abs(n-dfs(0,0)) <</abs(n-y)?></int>…

abc 040

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

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座標が同じだと条件に合わない. そこで負にすることで絶対値が大きい順に並べこれ…

codeIQ 2791

codeiq.jp例によってdfsとメモ再帰で解けます. struct P { int x; int y; P(){}; P(int x,int y):x(x),y(y){}; P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;} P operator+=(const P&q){x+=q.x;y+=q.y;return *this;} bool operator!=(const P&…

c++11でグラフ理論

競プロで頻繁にグラフが絡む問題が出題されます. 隣接リストvector<vector<Edge>>を継承してグラフの様々な値を求めることができるクラスを作ってみました. 使い方 ・宣言 graph<T> g((int)n): 重みの型がTの,頂点の数がn個の隣接グラフの宣言. ・辺の挿入 g.direct(src,dst,</t></vector<edge>…

c++11で計算幾何

競プロでは平面幾何の問題が結構出題されます. c++ならば複素数を扱うcomplexを使ってもいいのだけどx,yではなくreal,imagになるのがなんとなく気持ちが悪いので自作してみました. computer geometry

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

codeIQ 2769

よくよく考えればルートの長さはたかだか2種類しかないとわかる. a,b=gets.split(',').map &:to_i p x=a.lcm(b),x==a*b ?x:x*2

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

c++11でモジュロ演算

競プロでモジュロ演算が面倒だったのでこれを簡単に扱えるクラスを作ってみた. 剰余類環と言われているやつで特に素数を法にするものは剰余体と呼ばれ以下のように積に対して逆元が定義できる. よく10^9+7で割った余りを求めさせたりするのでこれでmod周りの…

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>

aoj DPL_3_B

最大長方形 | 動的計画法 | Aizu Online Judge最大長方形を求めさせる問題. こちらを参考に応用する. ヒストグラムの中の最大長方形を求める問題はlog(n)のオーダで求まる. あとはそれを行について行えばいいので計算量はlog(w*h)のオーダーで行ける. struct…

aoj DPL_2_B

Chinese Postman Problem | Aizu Online Judge Spaghetti Source - 無向中国人郵便配達問題 ll chinesePostman(const Graph &g) { ll total = 0; vector<int> odds; REP(u, g.size()) { for(auto e : g[u]) total += e.cost; if (g[u].size() % 2) odds.push_back</int>…

aoj DPL_2_A

Traveling Salesman Problem | Aizu Online Judge 巡回セールスマンの問題 bit dpを使う問題 bit列にした時1を訪れていない頂点, 0を訪れた頂点としてdpを用いる. 計算量はO(n^2*2^n) int n; int d[15][15]; int dp[1<<15][15]; void solve() { REP(i,(1<<n)) fill_n(dp[i],n,INF); dp[(1<<n)-1][0] = 0; DOWN(i,(1<<n)-2,0) REP(v,n) REP(u,n) if(!(i>>u&</n))>…

aoj DPL_1_E

Edit Distance (Levenshtein Distance) | Aizu Online Judge レーベンシュタイン距離を求めるアルゴリズム. 下が詳しい レーベンシュタイン距離 - Wikipedia dpでいける. int solve(string s, string t) { int sn = s.size(); int tn = t.size(); vector<vector<int>> dp</vector<int>…

aoj DPL_1_D

Longest Increasing Subsequence | Aizu Online Judge まずはTLEする回答 dp[i] := (i番目の数まで使った時の最長部分増加列の大きさ) と定義しnについて2重ループを回せばO(n^2)で解ける. すなわちが以前の数より大きければ のような漸化式が書ける int mai…

aoj DPL_1_C

Knapsack Problem | Aizu Online Judge 0/1ナップサック問題とループの向きが単に逆になったパターン. 今回は中間結果の情報は破棄しているが問題によっては必要になる. #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define DOWN(i,b,a) for(int i=b;i>=a;i--) using namespace std; int main() {</n;i++)></bits/stdc++.h>…

aoj DPL_1_B

0-1 Knapsack Problem | Aizu Online Judge 前にも書いたが0/1ナップサック問題には大きく分けて3つの解法がありそのうちdpである2つの解法で解いてみた dp[i][j] := (i番目の品物まで使った時の合計重さjを実現できる最大合計価値) dp[i][j] := (i番目の品…

aoj DPL_1_A

Coin Changing Problem | Aizu Online Judge コイン問題 貪欲法では解けないのでDPを使う. dp[i][j] := (i枚目までのコインを使った時の金額jの最小実現枚数) とすれば計算量O(nm)で解ける #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define INF 1 << 30 using namespace std; int main() { int n, m; cin >> n …</n;i++)></bits/stdc++.h>

aoj ALDS1_14_D

Multiple String Matching | Aizu Online Judge 文字列Sの接尾辞配列を構築すると文字列Tの検索が二分探索で行えるためO(|T|log|S|)のオーダーで行える. 接尾辞配列の構築にかかるコストはO(|S|(log|S|)^2)なので何度もTの検索を行う場合有用である. #includ…

C++でのBM法の実装

文字列検索のアルゴリズムの中で比較的高速なものとして有名なBM法 文字列検索を行った時に役に立ったので書いたソースを載せるなお以下の文献を参考にさせていただきました. http://www.comp.cs.gunma-u.ac.jp/~koichi/ALG2/9beamerBM.pdf #include <bits/stdc++.h> using </bits/stdc++.h>…

aoj ALDS1_14_C

Pattern Search | Aizu Online Judge二次元配列の効率的なハッシュの精製方法について配列 から以下のような行方向のハッシュの配列 を生成する. この時 のように計算すればO(h)のオーダーでハッシュが計算できる.同様に以下のような列方向のハッシュの配列 …

aoj ALDS1_14_B

String Search | Aizu Online Judge 逐一比較だとTLEしてしまったがsubstrなるものを使うと通る. アルゴリズム的には同じオーダなのだけど内部処理で何かが違うのだろう. std::string::substr - C++入門 #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) #define FOR(i,a,b) for(int i=a;i<=b;i++) using namespace std; int main() { string t,p; cin>>t>>p; int</n;i++)></bits/stdc++.h>…

aoj ALDS1_14_A

Naive String Search | Aizu Online Judge やるだけ a,b=$<.map{|s|s.chomp};(c=a.size).times{|v|a[v..c-1]=~/^#{b}/&&p(v)}

aoj 0097

整数の和 | Aizu Online Judge 動的計画法を用いてやる. dp[i][j] := (i個の異なる0〜100の数を用いて和jを実現する場合の数) あとは0〜100まで順に更新する. ここでポイントはdp[i][j]の更新の順序で必ずiについて逆順で更新しなければならない. なぜならば…

aoj 0096

4つの整数の和 | Aizu Online Judge 動的計画法を使ってやる dp[i][j] = (i+1個の数を使って和jを実現する場合の数) あとは適当に1000までという条件を組み込めばOK #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i</bits/stdc++.h>

aoj 0092

正方形探索 | Aizu Online Judge 動的計画法の問題. dp(i,j)を(i,j)を右下の頂点とするの最大サイズと定義し以下のような漸化式を計算すれば良い. dp(i,j) = min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1))+1 あとは最大値を求めればよい. int main() { string s; in…

aoj 0091

にじみ | Aizu Online Judge dfsを使うところまでは良かったが探索の仕方がまずかった. まず最初に試したのは全ての探索木の節/葉において全部(8*8)を探索する方法でこれだとTLEしてしまった. 自力では解けなかったので先人達の答えを拝見させていただいた. …

aoj 0090

シールの重なり | Aizu Online Judge 二円の交点がどのくらい重なっているか数えれば良い. ついでに座標を扱うクラスを拡張した. class P { public: double x,y; P(){};P(double x,double y):x(x),y(y){}; P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;r…

aoj 0086

パトロール | Aizu Online Judge 一筆書き可能か判定する問題, すなわちグラフGが与えられた時そのグラフがオイラー路であるか判定すればよい. オイラー路となる条件は, すべての頂点の次数が偶数⇔オイラー閉路(オイラーグラフ) 奇数次数の頂点が2つで残りが…

codingame - Skynet: the Virus

Ambush Finish the 4th test of the "Skynet: the virus" puzzle with 50 or more remaining links and get a 100% score. (訳) 待ち伏せ "Skynet: the virus"の4番目のテストケースを50辺以上残して完了し,100%のスコアを獲得せよ. というAcheivementがあ…

codingame - Dwarfs standing on the shoulders of giants

メモ再帰によって簡単に解ける template<typename T> struct Edge { int dst; T w; Edge() {}; Edge(int dst): dst(dst) {w=1;}; Edge(int dst, T w): dst(dst), w(w) {}; bool operator < (const Edge &e){return w != e.w ? w > e.w : dst < e.dst;} }; typedef vector<Edge<ll></edge<ll></typename>…

codingame - Teads Sponsored Contest

グラフの直径を求めれば良い 以下が参考になる Spaghetti Source - 木の直径前に解いたabc019のdouble sweepのアルゴリズムを思い出した. 計算量はO(E) この手の問題は多いのでそのうちグラフをクラス化して保存しておきたい. 直径,最小全域木等をg.diameter…

aoj 0081

線対称の位置にある点 | Aizu Online Judge回転行列を利用してといてみた. class P { public: double x,y; P(){};P(double x,double y):x(x),y(y){}; P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;} P operator+=(const P&q){x+=q.x;y+=q.y;ret…

aoj 0077

ランレングス | Aizu Online Judge やるだけ int main() { string s, t = ""; while(cin >> s) { int i = 0; while(i < s.size()) { if(s[i]=='@'){REP(j,s[i+1]-'0')t+=s[i+2];i+=3;} else{t+=s[i];i++;} } cout << t << endl; t = ""; } return 0; }

aoj 0076

宝探し | Aizu Online Judge 久々の投稿 複素数を使うと以下のような漸化式になる あとはやるだけ int main() { int n; complex<double> T[1001]; T[0] = 0.0; T[1] = 1.0; FOR(i,2,1000) T[i] = complex<double>(1.,1./sqrt(i-1))*T[i-1]; while(cin >> n, n!=-1) { printf(</double></double>…

aoj 0072

灯篭 | Aizu Online Judge 最小全域木のコストを求めさせる問題. プリムのアルゴリズムを用いる. Spaghetti Source - 最小全域木 (Prim) typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src)…

aoj 0070

組み合わせの個数 | Aizu Online JudgedfsでやるとTLEしてしまった... int a[10]; int n, s, cnt; void dfs(int m,int r) { if(r > s) return; if(m==n+1) { if(r==s) cnt++; return; } FOR(i,0,9) { if(a[i]) { a[i] = 0; dfs(m+1,r+m*i); a[i] = 1; } } } …

aoj 0068

輪ゴムで囲んだ釘 | Aizu Online Judge 凸包を求めるアルゴリズムが蟻本に乗っていたのでそのまま書いてみた. class P { private: double add(double a,double b){if(abs(a+b)<1e-10*(abs(a)+abs(b)))return 0;else return a+b;} public: double x,y; P(){};…

codeIQ 2685

https://codeiq.jp/q/2685(404になっていたので説明すると,順次追加される数字に対し, それまで追加された数の集合のメジアンを求めさせる問題, だったはず)参考にしたのはこれ↓ でもこれだと負の数に対応できないので無理やり大きい数を足して調整している.…

codeIQ 2683

F(n) = [n*log10(n)] ([x]はxより大きい最小の整数) と定義されるとき G(m) = n (F(n) = m) となるようなnを求めよ, という問題. 2≦m≦1e10なので大体nの範囲は1~1e9程度, なので多めに見積もって1~1e10の範囲を二分探索すれば一瞬で求まる. void solve(ll …

aoj 0042

泥棒 | Aizu Online Judge 0-1ナップサック問題. abc 032 - Tamflexの貯蔵庫 でも書いたように大きく3種類の解法が考えられる. 物体の集合を2分割し組み合わせをすべて試す i番目までの物体を用いたとき重さjを実現できる最大の価値をdp[i][j]とおく i番目ま…

aoj 0040

アフィン暗号 | Aizu Online Judge初歩的な暗号. シーザー暗号に毛の生えた程度. 今回も問題そのものよりI/Oに手間取ってしまった. まず空白で区切らないでcinする方法について,これはgetlineを用いる.一番目にnをとるのでcin.ignore()でバッファを消去する…

aoj 0035

凹みの検知 | Aizu Online Judge幾何の問題 対角線となる二直線の交差を確認する解法 対角線で三角形2つに分割し面積で求める開放 が等が考えられる. 今回は後者で解いてみた.でも本当はrubyのコードにあるように https://www.jaist.ac.jp/~uehara/course/20…

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>