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

幅優先探索の問題 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>…

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

飛行機で何往復できるかという問題 普通にやると大変なので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>…

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

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

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

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

連想配列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>…

二重ループの効率化の問題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>

文字列一致の問題 鍵盤の右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>…

典型的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>…

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

二重ループ中の計算 #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>

背の順に並べるという問題 #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>

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

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

島の人口を均等に分散すべく橋をかける問題 総人口/島の数で目標値を求め,その状態にしていったときに隣の島に流入、流出(マイナス流入)を加算していく. #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>…

ドアの合計の開いた時間を求める問題 #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>

集合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>

pairについて この問題では結局使わなかったけど調べたので書いとく. //市の名前と人口を入力 string s; int x; vector<pair<string, int> > city; for(int i=0;i<n;i++){ cin>>s>>x; city.push_back(make_pair(s,x)); } vector<pair<string, int>> city; int>>はint> > と書かないとcompilation errorを吐く.</pair<string,></n;i++){></pair<string,>

文字列のカウント string str = "a1a2a3a4a5a6"; int cnt = count(str.begin(),str.end(),'a');//6 #include <bits/stdc++.h> using namespace std; struct Initializer { Initializer() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); } } in</bits/stdc++.h>…

文字列を右90度に回転させる問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 50; int main() { char a[MAX_N][MAX_N+1]; char b[MAX_N][MAX_N+1]; int n; cin>>n; //input for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } //回転 for(int i=0;i</n;i++){></bits/stdc++.h>

a以上b以下の数字のうちxで割り切れるものの数を答える. for文でループで解くのは一重ループだとしてもb = 10^18とか与えられるとキツイ. 上図で赤はxで割り切れる数 上段 = 中段 - 下段で考えた. aがxで割り切れた場合はaの1つ分を足す必要がある. #include <bits/stdc++.h></bits/stdc++.h>…

counter変数の加算で右辺に条件式を持ってきてもよいことがわかった. ex) int cnt = 0; cnt += 0<=k && k<=10; //kが0<=k<=10ならばTrue=1が加算され,そうでなければFalse=0が加算される. #include <bits/stdc++.h> using namespace std; int main() { int k,s; int x,y,z; </bits/stdc++.h>…

定数 const int N = 1000; const int inf = (int)1e9 + 1; const ll big = (ll)1e18 + 1; const int P = 31; const int MOD = (int)1e9 + 7; const int MOD1 = (int)1e9 + 9; const int MAX_INT = (1 << 31) - 1; const double eps = 1e-6; const double pi …

文字列反転の問題 文字列反転は次のようにする. string str = "abcde"; reverse(str.begin(),str.end());//"edcba" #include <bits/stdc++.h> using namespace std; int main() { string str; cin>>str; int start=0,end=0; for(int i=0;i</bits/stdc++.h>

factorialを求める問題 大きい数値はll型を使う. int型(4byte)の範囲は20億くらいを目安にする. #include <bits/stdc++.h> using namespace std; #define ll long long int #define MOD (ll)1e9+7 #define MAX(X,Y) ((X)>(Y)?(X):(Y)) #define MIN(X,Y) ((X)<(Y)?(X):(Y)) i</bits/stdc++.h>…

文字列についての問題 文字列の要素1つはchar型だと知った. ex) string str = "abcde"; cout<<typeid(str[1]).name()<<endl; //c よってsubstr(ポインタの位置,そこから何文字分?)を使って部分文字列を使った. #include <bits/stdc++.h> using namespace std; int main() { string s; int n; vector<string> ss; cin>>s>>n; sort(s.begin(),s.end()); for(int i=0;i<5;i++){ for(int…</string></typeid(str[1]).name()<<endl;>

入力に対して出力を行うのをプログラムがやってくれる. mainの後ろに置く. // ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif