紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

C++

【蟻本】Lake Counting

// 蟻本p.35 // Lake Counting(POJ No.2386) // 深さ優先探索で同じ文字を消していく問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 100; static const int MAX_M = 100; char field[MAX_N][MAX_M]; int n,m; int dx[8]={1,1,0,-1,-1,-1,0,1</bits/stdc++.h>…

【蟻本】部分和問題

// あり本 p.34 // 部分和問題 // 数列の中からいくつか選び和がkにできるか判定する #include <bits/stdc++.h> using namespace std; static const int MAX_N = 20; int cnt = 0; int k,n; int a[MAX_N]; bool dfs(int i,int s) { if(i==n)return s==k; //a[i]を使わない場</bits/stdc++.h>…

ABC022_C

頂点1を含まないグラフを考えてその最短経路を作れば良いと思ったが 頂点1を含まないグラフの作り方 == 頂点1に隣接している頂点の選び方O(N^2) dijkstra法O(N^2) よって全体でO(N^4)掛かってしまい案の定TLEだった. #include <bits/stdc++.h> using namespace std; static </bits/stdc++.h>…

ABC007_C

幅優先探索の問題 queueにいれて順番に計算していく. 座標を扱う際にtypedefが便利 typedef pair<int,int> P; que.push(P(x,y)); #include <bits/stdc++.h> using namespace std; int r,c,sx,sy,gx,gy; int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1}; static const int MAX_R =50; stat</bits/stdc++.h></int,int>…

【c++】vectorの重複要素の削除

C++

unique()は配列の長さは変わらないため重複で削除された空きの場所にゴミが入る #include <bits/stdc++.h> using namespace std; void printVector(vector<int> &v){ for(int i=0;i<v.size();i++){ cout<<v[i]<<endl; } } int main() { vector<int> vec; vec.push_back(1); vec.push_back(2); vec.push_back(2); vec.push_back(3); vec.push_back</v.size();i++){></int></bits/stdc++.h>…

ABC019_C

2で割り切れたら割り続けて集合に入れる. 2で割り切るのは右ビットシフトと同義 a[i] /= 2; a[i] = a[i]>>1; a[i] =>>1;//これはダメ a[i]>>1;//これもダメ 解答 #include <bits/stdc++.h> using namespace std; #define ll long long int static const int MAX_N = 100000;</bits/stdc++.h>…

ABC030_C

飛行機で何往復できるかという問題 普通にやると大変なのでlower_bound()による二分探索を使った. lower_bound(a,a+n,value)はvalue以上の値の位置を返す. #include <bits/stdc++.h> using namespace std; int main(){ int a[5] = {1,3,5,7,9}; int* pos = lower_bound(a,a+</bits/stdc++.h>…

ABC026_C

※bukaという変数とkouhaiという変数が混ざって大変汚いコード 部下と上司の木を表現してある社員が部下を持たなければ1, 部下を持っていればその部下の中からmax(部下の給料)+min(部下の給料)+1を返す. メモ化再起風に解いた. #include <bits/stdc++.h> using namespace std</bits/stdc++.h>…

ABC029_C

'a','b','c'から構成できるn文字の文字列を全て挙げる問題. n=2ならaa,ab,ac,ba,bb,bc,ca,cb,cc文字が増えていくので文字列と文字列の長さを引数にした関数を作ればよい. #include <bits/stdc++.h> using namespace std; char alphabet[4] = {'a','b','c'}; int n; void sol</bits/stdc++.h>…

C++ setの要素の検索

C++

setにある要素が含まれているか否かを判定するにはS.find(value)を用いる. 要素が含まれていない場合はS.end()を返す. よって if(S.find(x)!=S.end())cout<<"要素あり"; else cout<<"要素なし"; のように判定すればよい. #include <bits/stdc++.h> using namespace std; int</bits/stdc++.h>…

Project Euler 83 Path sum: four ways

問題を見た時からdijkstra法だと分かっていたが集中してやりたかったので敢えて取っておいた問題 #include <bits/stdc++.h> using namespace std; static const int WHITE = 1; static const int GRAY = 2; static const int BLACK = 3; static const int INF = 1<<21; stat</bits/stdc++.h>…

ABC020_C

2分探索と単一始点最短経路問題の問題 dijkstra法は二次元配列と頂点の番号を対応させて考えればよい. #include <bits/stdc++.h> using namespace std; /* 考え方 1.2文探索でtmp<=tを満たす最大のtmpを見つける 2.dijkstra法で'#'の移動コストがtmpであるとして'S'->'G'へ</bits/stdc++.h>…

単一始点最短経路 dijkstra法

C++

#include <bits/stdc++.h> using namespace std; static const int MAX_N = 100; static const int WHITE = 0;//未踏 static const int GRAY = 1;//確定している点と隣接 static const int BLACK = 2;//確定 static const int INF = 1<<21; int M[MAX_N][MAX_N] = {0};//隣</bits/stdc++.h>…

全探索 整数を作れるかの問題

C++

配列の要素から整数を作れるかを判定する関数 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 1000; int n;//配列Aの大きさ int m;//判定する整数 int A[MAX_N]; bool solve(int i,int m){ /* 整数mが作れるか否かの再起関数 */ if(m==0)return t</bits/stdc++.h>…

便利ワザ4

C++

INT_MIN,INT_MAXがint型の最大,最小値の定数らしい. #include <bits/stdc++.h> using namespace std; int main() { int a = INT_MAX; int b = INT_MIN; cout<</bits/stdc++.h>

ABC033_C

1+2*3+0+5*6+7 のように+か*で繋がった式が与えられる. 式の結果が0となるように,式のある値を0に入れ替える. この時最小の入れ替え回数を求めるという問題.足し算はそれぞれの値で0と入れ替えなければならない. 掛け算はひとつ0があればよい. 掛け算のほう…

ABC036_C

連想配列mapを使う問題 map M; M[key] = value; とし, keyを与えられた数値にvalueをその数値が何番目に大きいのかを記録TLE解法 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 100000; int main() { int n,x; set<int> s; int a[MAX_N],b[MAX_N]; ci</int></bits/stdc++.h>…

ABC038_C

二重ループの効率化の問題TLEだったやつ #include <bits/stdc++.h> using namespace std; static const int MAX_N = 100000; int main() { int n,a[MAX_N+1],l,r,ans = 0; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i</bits/stdc++.h>

ABC039_C

文字列一致の問題 鍵盤の右20個の文字列が与えられるので今いる場所を当てるというやつ. #include <bits/stdc++.h> using namespace std; string func(string str,int n){ /* 文字列strを整数n倍し文字列を返す関数 */ string tmp = str; for(int i=1;i<n;i++){ str += tmp; } return str; } int main() { string s; cin>>s; string keyboard </n;i++){></bits/stdc++.h>…

ABC040_C

典型的DP問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 100000; int main() { int dp[MAX_N+1] = {0};//i本目の柱までにかかる最小コスト int n,x,height[MAX_N+1]; cin>>n; for(int i=1;i<=n;i++){ cin>>height[i]; } dp[1]=0; dp[2]=abs(</bits/stdc++.h>…

ABC035_C

一列に並んだオセロ(最初は全て黒)を指定された左と右の位置で反転を繰り返すという問題. 普通にやっていたら配列サイズ200,000、指定位置の個数や左,右の範囲が大きい場合でTLEを起こす. 普通にやった場合の解 #include <bits/stdc++.h> using namespace std; int main() {</bits/stdc++.h>…

分割統治法

C++

分割統治法を用いて最大値を求める. #include <bits/stdc++.h> using namespace std; int findMaximum(int A[],int left,int right) { int u,v,m,x,l=left,r=right; m = (l+r)/2; if(l==r-1){ return A[l]; }else{ u = findMaximum(A,l,m); v = findMaximum(A,m,r); x = max</bits/stdc++.h>…

lower_bound()

C++

lower_bound()について int A[14] = {1,1,2,2,2,4,5,5,6,8,8,8,10,15}; int *pos; int idx; pos = lower_bound(A,A+14,3);//3以上の値の先頭のものを指す idx = distance(A,pos);//Aは0番目, posは5番目を指しているので5 ちなみに要素の最大値よりも大きい…

ABC037_C

二重ループ中の計算 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 100000; int main() { int n,k,a[MAX_N],tmp; int *s; long long int res = 0; cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i</n;i++){></bits/stdc++.h>

ABC051_C

背の順に並べるという問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = (int)1e5; int main() { int n,x; priority_queue<pair<int,int> > pq; cin>>n; for(int i=1;i<=n;i++){ cin>>x; pq.push(make_pair(x,i)); } while(!pq.empty()){ cout<</pair<int,int></bits/stdc++.h>

ABC028_C

A < B < C < D < E の入力に対して考えうる3つの和の中で3番目に大きい物を答えるという問題 #include <bits/stdc++.h> using namespace std; int main() { priority_queue<int> pq; set<int> s; int a[5]; for(int i=0;i<5;i++){ cin>>a[i]; } sort(a,a+5); do{ int x = a[0]+a[1]+a[</int></int></bits/stdc++.h>…

ABC054_C

階乗して並び変えたもののうち島1から始まるPATHを数える. グラフを隣接リストから隣接行列に変形する. はじめから島1が最初になるようにvector<> islandを作ったためnext_permutatino()しても時間的に問題ない. #include <bits/stdc++.h> using namespace std; template <class ForwardIterator, class T> v</class></bits/stdc++.h>…

ABC027_B

島の人口を均等に分散すべく橋をかける問題 総人口/島の数で目標値を求め,その状態にしていったときに隣の島に流入、流出(マイナス流入)を加算していく. #include <bits/stdc++.h> using namespace std; int main() { int n,a[100],total=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; to</n;i++){></bits/stdc++.h>…

ABC024_B

ドアの合計の開いた時間を求める問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = (int)1e5; int main() { int n,t,a[MAX_N]; cin>>n>>t; for(int i=0;i<n;i++)cin>>a[i]; int res=t;//最後に開く分 for(int i=1;i</n;i++)cin></bits/stdc++.h>

ABC032_B

集合setを用いる問題 集合への挿入は set<string> ss; ss.insert("aaa"); ss.insert("bbb"); ss.insert("aaa"); cout<<(int)ss.size()<<endl;//2 この時(int)でキャストしないと幾つかのテストケースでREをとってしまった. #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) int main() { set<string> ss; string s; int k; cin>>s>>k…</n;i++)></endl;//2></string>