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

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

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

ABC020_C

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

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>

ABC033_B

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

ABC035_B

文字列のカウント 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>…

ABC039_B

文字列を右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>

ABC048_B

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

ABC051_B

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

便利ワザ2

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

ABC053_B

文字列反転の問題 文字列反転は次のようにする. 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>

ABC055_B

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

ABC025_A

文字列についての問題 文字列の要素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

ABC046_A

種類を数える問題 集合(set)を用いる #include <bits/stdc++.h> using namespace std; int main() { int a,b,c; set<int> s; cin>>a>>b>>c; s.insert(a);//集合sにaを挿入 s.insert(b); s.insert(c); cout<</int></bits/stdc++.h>

標準ライブラリ一括インクルード

#include <bits/stdc++.h></bits/stdc++.h>

ABC050_A

文字列を分割して数値にする問題C++におけるsplit関数の実装 qiita.com #include <iostream> #include <cstdio> #include <string> #include <sstream> #include <vector> using namespace std; int stoi(std::string str){ int ret; std::stringstream ss; ss<<str; ss>>ret; return ret; } vector<string> split(const s</string></str;></vector></sstream></string></cstdio></iostream>…

ABC051_A

文字列の置換 www.geocities.jp #include<iostream> #include<string> using namespace std; // 文字列を置換する std::string Replace(std::string String, std::string From, std::string To ) { std::string::size_type Pos( String.find( From ) ); while( Pos != std::str</string></iostream>…