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

Tamflexの貯蔵庫

やる気のない備忘録

複数プロジェクトが併存できるC++用の汎用的なMakefile

c++

汎用的に使えるMakefileを作ってみた github.com詳細はこちらから qiita.com

codeIQ 1621

なんとなくlower_boundでやりたかった. vector<ll> p; void init() { p.resize(10000); fill(p.begin(),p.end(),1LL<<30); int m = 0; p[m++] = 2; for(int i=3;i<=100000;i+=2) { bool flag = true; for(int j=0;p[j]*p[j]<=i;j++) { if(i%p[j]==0) { flag = fa</ll>…

codeIQ 1630

abc029にも似た, というかほぼ同じな問題があった. 念の為long long intを用いて解いた. void solve(ll n) { n++; ll d = 1, t, ans = 0; while(n>d) { t = d; d *= 10; ans += (n/d)*t+(n%d>t*7?(n%d>=t*8?t:(n%d)%t):0); } cout << ans << "\n"; } int mai…

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

c++11でグラフ理論

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

aoj DPL_3_B

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

codeIQ 2749

オセロのAIと同じ要領でできる. 初手判定に要注意 int a[25]; int dx[] = {1,1, 1, 0,-1,-1,-1,0}; int dy[] = {1,0,-1,-1,-1, 0, 1,1}; vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss</string></string>…

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番目の品…

C++でのBM法の実装

c++

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

菱形上の最短経路 | Aizu Online Judge 添字の扱いが厄介 vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss, tmp, delim)) res.push_back(tmp); return res; } int main() { vector<int> v; st</int></string></string>…

aoj 0087

逆ポーランド記法 | Aizu Online Judge やるだけ vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss, tmp, delim)) res.push_back(tmp); return res; } int main() { string s; while(getl</string></string>…

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 - Mayan Calculation

連想配列を使えば楽に解ける long long を使うことに注意 #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; int main() { string s; ll l,h,ans,x[2]; cin>>l>>h; vector<string> a(20,""); map<string,ll> b; REP(i,l) { getline(cin,s); if(s==""){i--;continue;} REP(j,s.size())…</string,ll></string></n;i++)></bits/stdc++.h>

codingame - The Gift

貪欲的に小さい順にとけば良い. #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; int main() { ll n,c; cin>>n>>c; vector<ll> a(n,0); REP(i,n) cin >> a[i]; string ans = ""; sort(a.begin(),a.end()); REP(i,n) { int t=(a[i]</ll></n;i++)></bits/stdc++.h>

codingame - Bender, a depressed robot

ループ判定が面倒 自分は同じ所を同じ向きで通った場合にループ判定を出すようにした. しかしこれだけでは最後のテストケースが落ちるので20回以上同じ所を同じ向きで通った場合判定を出すようにした. struct P { int x,y; P(){}; P(int x, int y): x(x), y(…

codingame - Network Cabling

x軸またはy軸に平行なメインケーブルから各家庭に枝を伸ばせば良い. 中央値は絶対偏差の和を最小にすることが知られているので, メインケーブルのy座標/x座標は中央値を用いると良さそう. 証明はこちらなど↓ 連続関数に関してはこちら↓ http://web.uvic.ca/~…

codingame - Teads Sponsored Contest

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

codingame - Indiana - Level 1

やるだけ int main() { int W; // number of columns. int H; // number of rows. cin >> W >> H; cin.ignore(); vector<vector<int>> T(W,vector<int>(H,0)); REP(i,H)REP(j,W) cin >> T[i][j]; int EX; // the coordinate along the X axis of the exit (not useful for thi</int></vector<int>…

codingame - The Paranoid Android

そこまで難しくはないが例外処理に手間取った. struct Info { int floor; int pos; Info(){}; Info(int f,int p):floor(f),pos(p){}; bool operator==(const Info &a) { return floor==a.floor && pos==a.pos; } }; const int SPACE = 0; const int BLOCK = …

codingame - Stock Exchange Losses

int main() { ll n; cin >> n; ll ans = 0, m = LLINF; vector<ll> a(n); REP(i,n) cin >> a[i]; DOWN(i,n-1,0) { m = min(a[i],m); ans = min(m-a[i],ans); } cout << ans << endl; return 0; }</ll>

aoj 0082

メリーゴーランド | Aizu Online Judge 愚直そのもの int main() { int a[] = {1,2,1,2,1,4,1,4}; int p[8],i=0; while(cin >> p[(i++)%8]) { if(i%8==0) { int ans=0, md = 1e5, dist; REP(j,8) { dist = 0; REP(k,8) dist+=(p[k]>a[(k+j)%8])?p[k]-a[(k+j)…

aoj 0080

3乗根 | Aizu Online Judge やるだけ void solve(const double q) { double a = q*0.5; while(fabs(a*a*a-q)>=1e-5*q) a -= (a*a*a-q)/(3*a*a); printf("%lf\n",a); } int main() { double q; while(cin>>q,q>0) solve(q); return 0; }

aoj 0078

魔方陣 | Aizu Online Judge やるだけ int main() { int n; while(cin>>n,n) { vector<vector<int> > T(n,vector<int>(n,0)); int k=1, x=n/2+1, y=n/2; while(k<=n*n) { while(T[x][y]!=0) { x = (x+1)%n; y = (y-1)%n; y = y<0? y+n : y; } T[x][y] = k; x = (x+1)%n; y = (</int></vector<int>…

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 0073

四角すいの表面積 | Aizu Online Judge #include <bits/stdc++.h> main(){int x,h;while(scanf("%d%d",&x,&h),x)printf("%f\n",x*(x+sqrt(4*h*h+x*x)));} $<.map(&:to_i).each_slice(2){|a|puts (x=a[0]**2)+Math.sqrt(x*(x+4*a[1]**2))if a[0]!=0}</bits/stdc++.h>

aoj 0071

爆弾の連鎖 | Aizu Online Judge x,y座標の変換に注意. int a[8][8]; void f(int x, int y) { a[x][y]=0; for(int i=1;i<=3;i++) { if(x+i>7) break; if(a[x+i][y]) f(x+i,y); } for(int i=1;i<=3;i++) { if(x-i<0) break; if(a[x-i][y]) f(x-i,y); } for(in…

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 0067

島の数 | Aizu Online Judgeやるだけ. int a[144]; void flip(int x, int y) { if(x>11||y>11||x<0||y<0) return; if(a[x+y*12]) { a[x+y*12] = 0; flip(x+1,y); flip(x-1,y); flip(x,y+1); flip(x,y-1); } } void solve() { int cnt = 0; REP(i,144) if(a[i…

aoj 0066

三目並べ | Aizu Online Judge やるだけ. char solve(string s) { REP(i,3) { if(s[i*3]==s[i*3+1]&&s[i*3]==s[i*3+2]&&s[i*3]!='s') return s[i*3]; if(s[i]==s[i+3]&&s[i]==s[i+6]&&s[i]!='s') return s[i]; } if(s[0]==s[4]&&s[4]==s[8]&&s[4]!='s') retu…

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 0048

階級 | Aizu Online Judge「やるだけ」なのに何故か頑張ってしまった...(277 byte)上には上がいるみたいです(T T) AIZU ONLINE JUDGE #include <bits/stdc++.h> main(){char* s[]={"light fly","fly","bantam","feather","light","light welter","welter","light middle","m</bits/stdc++.h>…

aoj 0047

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047scanfの使い方の復習. int main() { cin.tie(0); ios::sync_with_stdio(false); char c1, c2; int a[3] = {1,0,0}; while(~scanf("%c,%c\n",&c1,&c2)) swap(a[c1-'A'],a[c2-'A']); REP(i,3) i…

aoj 0044

最小の素数と最大の素数 | Aizu Online Judge全探索してからやったけど, 直近だけ探索すればよかったかも. bool prime(int n) { if(n<=1) return false; if(n==2) return true; if(n%2==0) return false; for(int i=3; i<=sqrt(n); i+=2) if(n%i==0) return …

競技プログラミング 備忘録

c++

競技プログラミングでつよい人のコードを見ると, 冒頭に大量のマクロや一行で記された関数の羅列を見かけることが多い.競プロにおいてはコード自体の保守性や拡張性よりも,アルゴリズムそのものに対する理解,およびその実装力が求められるので本質的なところ…

aoj 0043

パズル | Aizu Online Judge いわゆる麻雀. 清一色の状況下, 一向聴かどうか判定し上がり牌を出力する. dfsで順子・暗刻を落としていき,最後に対子が残ればtrueとなるようにすればよい. 13枚しかないので1〜9について仮想的な1枚を加え,それぞれ「上がり」か…

aoj 0042

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

テンパズル

c++

テンパズル - Wikipedia数式 | Aizu Online Judge においては除算が含まれなかったが, 除算も含めて計算できるものを作成した. まず除算について, すべて整数なので計算結果は0除算の時を除き有理数になることが保証される.したがってpairで分母分子を保存し…

aoj 0040

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