問題概要 二つの文字列s,tが与えられる。tの任意の文字を削除してsにすることができるか。 s,tは100000文字を超えない。 解法 t[0]からt見ていきs[0]と同じば場合s[1]について比較。 #include <cstdio> #include <iostream> #include <cstring> using namespace std; int main(){ char s</cstring></iostream></cstdio>…

やるだけ・ #include <cstdio> using namespace std; int main(){ int n,s; int d[21][21]={0}; scanf("%d%d",&n,&s); int co = s; for(int j = 0;j < n;j++){ for(int i = 0;i < n;i++){ if(j >= i){ d[i][j] = co; co++; if(co == 10)co = 1; } } } for(int i = 0;</cstdio>…

やるだけ。 #include <cstdio> #include <cmath> using namespace std; int main(){ int r,m,y; scanf("%d%d%d",&r,&m,&y); double ans=m,k = 1 + (r / 100.0); for(int i = 0;i < y;i++) ans *= k; printf("%.0f\n",floor(ans)); return 0; }</cmath></cstdio>

奇問。 究極のやるだけ。 #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> using namespace std; int main(){ char d[80]; int p[100] = {0}; while(cin >> d){ int len = strlen(d); for(int i= 0;i< len;i++){ if(d[i] >= 65 && d[i] <= 90){ p[d[i]-6</iostream></string></algorithm></cstring></cstdio>…

半分全列挙するだけ。一発ACだった。 #include <cstdio> #include <algorithm> using namespace std; int a[4003],b[4003],c[4003],d[4003]; int e[16000005]; int n; int main(){ scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); } for</algorithm></cstdio>…

蟻本にある問題。蟻本頭良すぎて焦る。しゃくとり法。 #include <cstdio> #include <algorithm> #include <map> #include <set> using namespace std; int main(){ int p,a[1000003]; scanf("%d",&p); for(int i = 0;i < p;i++) scanf("%d",&a[i]); set<int> all; for(int i = 0;i < p;i++){ al</int></set></map></algorithm></cstdio>…

二分探索・平均最大化。 日本TLE怖い協会 もうこの問題は解きたくない。 #include <cstdio> #include <algorithm> #include <functional> #include <utility> using namespace std; int n,k; int v[100010]; int w[100010]; pair<double, int> p[100012]; bool ans(double x){ for(int i = 0;i < n;i++){ p[i] = ma</double,></utility></functional></algorithm></cstdio>…

普通に平均最大化をする。小数の闇を見た。 #include <cstdio> #include <algorithm> #include <functional> #include <iostream> #include <math.h> using namespace std; int n,k,d[1002][2]; double t[1002]; bool ch(double x){ for(int i = 0;i < n;i++){ t[i] = 100.00 * d[i][0] - x * d[i][1]; } sort(</math.h></iostream></functional></algorithm></cstdio>…

普通に二分探索使わなくてもいいのでは？とおもって調べてみたら普通に貪欲法でいけるらしいです。下のブログを参考にしました。POJ-3045 : Cow Acrobats - komiyamの日記 POJ-3045 : Cow Acrobats - komiyamの日記 #include <cstdio> #include <algorithm> #include <utility> using nam</utility></algorithm></cstdio>…

もう解きたくない・ 黒歴史ソース #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000002; int n,k,d[100003]; bool ch( long long int x){ long long int u = 0; for(int i = 0;i < n;i++){ if(d[i] > x){ u += (d[i] - x + k -2)/(k-1); }</algorithm></cstdio>…

二分探索で最小値を求める。 #include <cstdio> using namespace std; const int INF = 100002; int n,m,d[1000002]; bool ch(int x){ int u = 1; int sum = 0; for(int i = 0;i < n;i++){ if(d[i] > x)return false; if(d[i] + sum > x){ u++; sum = d[i]; }else{ s</cstdio>…

顕著な二分探索。説明不要な気がする。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int l,n,m,d[50001]={0}; bool ch(int x){ int u = 0; int pre = 0; for(int i = 1;i <= n+1;i++){ if(d[pre] + x > d[i]){ u++; }else{ pre =</algorithm></cstdio>…

蟻本にある。 二分探索使わなくても解けるのだろうか。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1000000001; int n,c,p[100001]; bool ch(int x){ int nau = 0,sum = 1,pre = p[nau]; while(nau < n && sum < c){ if(pre + x <= p[nau]){</algorithm></cstdio>…

解法：プリム法、またはクラスカル法をやるだけ。なぜプリム法を選んだのかは自分でもわからん。気づいたら組んでいた。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; const int MAX_V = 100; const int INF = 100000000; int cost[MAX_V][MAX_V]; i</iostream></algorithm></cstdio>…

ベルマンフォード法で負閉路の検出をするだけ。細かいところは問題文参照してください。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int MAX_E = 6000; const int MAX_V = 600; const int INF = 100000000; struct edge { int from,to,cost;</string.h></algorithm></cstdio>…

union find参考にさせていただきました。 http://d.hatena.ne.jp/sndr/20121221/1356071878 #include <cstdio> #include <iostream> using namespace std; int par[200003];//親 int rank[200003];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i]</iostream></cstdio>…

顕著なunion-find実行速度遅すぎる。 #include <cstdio> #include <iostream> using namespace std; int par[1002];//親 int rank[1002];//木の深さ void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; rank[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }</iostream></cstdio>…

解法：最長増加部分列(LIS)蟻ゲーです。 #include <cstdio> #include <algorithm> const int INF = 100000000; using namespace std; int main(){ int n; scanf("%d",&n); while(n--){ int p; int d[40003]={0}; int dp[40003] = {0}; scanf("%d",&p); for(int i = 0;i < p;i++)</algorithm></cstdio>…

闇。このブログを参考にさせていただきました。 http://d.hatena.ne.jp/atetubou/20110528/1306544909 以上。 #include <cstdio> #include <algorithm> #include <utility> using namespace std; int main(){ int t; scanf("%d",&t); while(t--){ int n; bool use[5003]; int ans = 0; pa</utility></algorithm></cstdio>…

蟻ゲー以上。 #include <cstdio> #include <string.h> using namespace std; int dp[100003]; int main(){ while(1){ int n,m; int d[102][2]; scanf("%d%d",&n,&m); if(n == 0)break; for(int i = 0;i < n;i++){ scanf("%d",&d[i][0]); } for(int i = 0;i < n;i++){ scanf("%d</string.h></cstdio>…

N年ぶりにDPの問題を解いたけどなんとかできた。。。解法：DP dp[i] = max(dp[i-1],終わる時間がiの中で最も大きいもの);実際問題から計算量O(N)しかありえないっぽいし解法しぼれたのでよかった。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P</int,int></algorithm></cstdio>…

問題文解法：DP中のDP(?) #include <cstdio> #include <algorithm> using namespace std; int main(){ int t,w,dp[3002][32] = {0}; bool ch[1003]; scanf("%d%d",&t,&w); for(int i = 0;i < t;i++){ int tmp; scanf("%d",&tmp); if(tmp == 1){ ch[i+1] = true; }else{ ch[i+1] </algorithm></cstdio>…

なぞに顕著な貪欲。 大きいほうから順に消していけばよい。 #include <cstdio> #include <algorithm> #include <cmath> #include <functional> #include <iostream> using namespace std; int main(){ int n; double d[103] = {0}; scanf("%d",&n); for(int i = 0;i < n;i++){ cin >> d[i]; } sort(d, d + n ,</iostream></functional></cmath></algorithm></cstdio>…

解法：貪欲 こめんと：priority_queueはとても便利。 #include <cstdio> #include <utility> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; typedef pair<int,P> PP; int main(){ int out[50002]={0}; int n; int ans = 0; priority_queue<PP ,vector<PP>,greater<PP> > que; scanf("%d",&n</pp></pp></int,p></int,int></vector></queue></utility></cstdio>…

こういう問題苦手。わかりやすいコーナーケースに気づけなくてめちゃくちゃ時間がかかった。解法：貪欲法。 #include <cstdio> #include <algorithm> #include <utility> #include <cmath> using namespace std; int cas = 1; int main(){ while(1){ pair<int,int> is[1003]; int n,d,ans= 1; scanf("%d%d</int,int></cmath></utility></algorithm></cstdio>…

解法：全探索(dfs)やるだけである。思ったより簡単で腰を抜かす。 #include <set> #include <iostream> #include <cstdio> using namespace std; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; set<int> tmp; int ans = 0; int d[6][6]; void dfs(int x,int y,int s,int g){ if(s == 6)</int></cstdio></iostream></set>…

全列挙。next_permutationを使うとらく。やるだけです。ちょっと数学力が足りないのでせこい技を使ってしまった。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ int n,sum; int d[12]; int c[12][12] = {0}; c[0][0] = 1; c[1][0] = 1; </iostream></algorithm></cstdio>…

あの有名な最長共通部分列問題。典型的な問題。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int main(){ char a[2000],b[2000]; while(cin>>a>>b){ int dp[1001][1001] = {0}; int alen = strlen(a); int blen = strlen(b); for(int i =</cstring></algorithm></iostream></cstdio>…

問題文解法：DP(上の二つのやつのでかいほうを足していくだけ) #include <cstdio> #include <algorithm> using namespace std; int main(){ int n; int t[102][102] = {0}; int dp[102][102] = {0}; scanf("%d",&n); for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ sca</algorithm></cstdio>…

問題👈やるだけ。またまたソート。記事数を増やすために頑張っているんです。 #include <cstdio> #include <algorithm> using namespace std; int main(){ int n,d[10003] = {0}; scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%d",&d[i]); } sort(d,d + n); printf("%d\n",d</algorithm></cstdio>…