2014-10-01から1ヶ月間の記事一覧
やるだけ。 #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>…
精進足りな過ぎてやばい.
問題文ちゃんと読もうな。 #include <cstdio> #include <iostream> using namespace std; int main(){ char d[11]; scanf("%s",&d); int k; int sum = 0; for(int i = 0;i < 10;i++){ if(d[i] == '?'){ k = 10 - i; }else if(d[i] == 'X'){ sum += 10 * (10 - i); }else{ int n</iostream></cstdio>…
普通にDPするだけ。 INFがINFになってなくて辛い思いをした。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int INF = 1000000000; int k[153]; int d[153][11][2]; int dp[153][11][80]; int n,m; int main(){ while(1){ scanf("%d%d",&n,&m)</string.h></algorithm></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>…
解法:半分全列挙 粘り勝ち。実際WA続いたのはAOJがサーバーの負担を減らすためにテストデータをまとめた結果初期化が必要になってそれを忘れていただけだからたぶん本番はダイジョブ。計算量はO(N^2logN).まあ典型のやつですね。蟻本を読もう。 #include <cstdio> #in</cstdio>…
解法は顕著。 もし文字a[i] == b[j]だったらdp[i][j] = dp[i-1][j-1] + 1;をすることによって連続する文字列を求める。常にdp[i][j]の値をチェックし、最大のものが解。計算量はO(N^2). #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int d</algorithm></iostream></cstring></cstdio>…
こういう系の問題一番苦手。 実装力がない。 オーダーから察するにO(N)問題。int s[i]; (i番目について、白の碁石の連続している数) int k[i]; (i番目について、黒の碁石の連続している数) で値をもっておきあとはいわれたとおりにやる。 #include <cstdio> #inclu</cstdio>…
POJのsolved数40超えた。 精進します。
蟻本にある問題。蟻本頭良すぎて焦る。しゃくとり法。 #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>…
蟻本の二分探索のところで、lower_bound,upper_bundあまり使わないの、なんとなくわかった気がする。
二分探索で最小値を求める。 #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>…
ひとつ前の「最悪の記者」のほうが少し難易度が高いきがする。部分点解法全く思いつきませんでしたすいません。 満点解法 深さ優先探索(DFS)をする. まず一番上にあるモビール(?)をもとめる。 そのモビールを関数dfsに投げる 関数dfsはそのモビールに必要…
POJ復活してた
POJがなぜか落ちているので精進できない
部分点解法 N個のチームの順位のつけ方をすべて試し、適する順位を求める。計算量はO(N!)であり、これでは全体の30%しか得点を得られない。 満点解法 トポロジカルソートをする。 計算量はO(N + M).これについてはJOIの解説と全く同じなのでそちらを参照して…
満点解法より効率の悪い解法を考えるほうが難しいと感じた。 部分点解法 4重ループで4本の柱を選び、それが正方形か調べその面積の最大値を求める。O(N).でもこんな解法を本気で考える人はいない気がするな・・・ 満点解法 bool型の配列などで、座標を指定…
ごり押しで何とかいけそうな問題。ソートをして少し考察しましょう。JOIの解説の通りにバケットソートを用いて解きました。問題文の言われたとおりにやっただけなので解説は省かせてもらいます。 #include <cstdio> #include <algorithm> using namespace std; int main(){ int </algorithm></cstdio>…
部分点解法についてのソースも乗のっけていこうと思いましたが、AOJで部分点採点してくれないことに気が付いたのでやめます。すいません。 部分点解法 a[i]からa[i+k-1]までの和をfor文で求め、これを0 オーダーはO(NK). 参考までに↓ int max = 0 for(int i …
joi本選の過去問、簡単な解説付きで載せていきます。