解法：Segment Tree(RMQ)セグツリやるだけUSACOの問題。Range Minimum QueryとRange Maximum Queryを同時に処理する。計算量O(Q lg N). #include <cstdio> #include <algorithm> #include <climits> using namespace std; typedef pair<int,int> P; int n,q,seg[2][121072],nn; P query(int a,int </int,int></climits></algorithm></cstdio>…

例の平方分割で解ける問題バケットのサイズを色々試してみた。B = 1100 → TLE (>20000MS) B = 1000 → 11735MS B = 900 → 11782MS B = 850 → 11829MS B = 800 → 11157MS B = 700 → 12235MS結果B = 800が一番早い（？） #include <cstdio> #include <vector> #include <algorithm> using n</algorithm></vector></cstdio>…

見るからにDPっぽいDP.N だから恐らくO(N)なんだけど頭が悪いからO(N log N)でといた。dp[i] := i番目の駅に行くときのかかる値段の最小値で求まる。よく読んでいなくて無駄なWAを生やしすぎたし英語力ない。ACしたあと中国人のブログ見てたらみんなO(N)でと…

問題文 http://poj.org/problem?id=3051 深さ優先探索やるだけ char型嫌いでint型好きなので配列はintにした。JOI予選まであとn日！！！（n #include <cstdio> #include <algorithm> using namespace std; int w,h,t=0,ans=0; int d[1005][90]; int dx[] = {0,-1,0,1}; int dy[]</algorithm></cstdio>…

http://poj.org/problem?id=2394解法：ダイクストラやるだけ。JOI予選近いですね・・・ #include <cstdio> #include <queue> #include <vector> using namespace std; int f,p,c,m; const int INF = 100000000; const int MAX_V = 510; struct edge{ int to,cost;}; typedef pair<int,int> P;</int,int></vector></queue></cstdio>…

問題文 http://poj.org/problem?id=3627謎問 priority_queueつかうだけ。 sortしたら間に合わないとか言うやつなのかな？ #include <cstdio> #include <queue> using namespace std; int n,s,b,ans; int main(){ scanf("%d%d",&n,&b); priority_queue<int> que; for(int i = 0;i </int></queue></cstdio>…

問題文 http://poj.org/problem?id=3615ワーシャルフロイド法をちょっとだけいじる。 N iostreamを使うとTLEした。 #include <cstdio> using namespace std; const int INF = 100000000; int n,m,t; int d[305][305]; int main(){ for(int i = 0;i <= 303;i++){ for(</cstdio>…

問題文 http://poj.org/problem?id=3620 解法：深さ優先探索やるだけ。 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n,m,k,tmp,ans=0,d[110][110]; int da[] = {0,1,0,-1}; int db[] = {1,0,-1,0}; void dfs(int a,int b){ tmp++; d[a][b] = 0;</algorithm></cstdio></iostream>…

問題文 http://poj.org/problem?id=3626 解法：幅優先探索やるだけ。 感想：JOI予選にでてもおかしくない。 #include <cstdio> #include <iostream> #include <queue> using namespace std; typedef pair<int,int> P; const int t = 510; const int INF = 100000; int x,y,n,ans; int d[1020][1</int,int></queue></iostream></cstdio>…

ダイクストラ二分ぐらいで瞬殺。 #include <cstdio> #include <queue> #include <iostream> using namespace std; const int INF = 100000000; const int MAX_V = 1002; struct edge{ int to,cost;}; typedef pair<int,int> P; int V; vector<edge> G[MAX_V]; int d[MAX_V]; void dijkstra(int s){ pr</edge></int,int></iostream></queue></cstdio>…

ドミノ敷き詰め問題。 完全マッチングの個数を数える問題ともいうのかな。 bitDPでときました。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; int w,h; long long int dp[2][1 << 11]; int main(){ while(1){ scanf("%d%d",&h,&w); if(h == 0 && w =</string.h></algorithm></cstdio>…

こんな簡単なDPが眠っていたとは。。。 #include <cstdio> #include <algorithm> using namespace std; int p; int s[150002]; int dp[150002][2]; int main(){ scanf("%d",&p); for(int i = 1;i <= p;i++)scanf("%d",&s[i]); for(int i = 1;i <= p;i++){ dp[i][0] = max(dp[i-1</algorithm></cstdio>…

ただのDPのはずかstrlen()多用しすぎててTLEにになっていた。 気をつけよう。 #include <cstdio> #include <string.h> #include <iostream> using namespace std; char a[202],b[202],c[404]; bool dp[202][202]; int main(){ int n; cin >> n; int co = 1; while(n--){ memset(dp, 0, si</iostream></string.h></cstdio>…

とても頭のわるいソースになった。英語読めな過ぎて「最初のところから25以上離れない」みたいな重要なところを読み飛ばしており仕方なくsetを使っていた。解き終えてからほかの人のブログで知った。 set＜string＞にしたらTLEになったので仕方なくpair使い…

くっそ頭悪い 戒め #include <set> #include <algorithm> #include <string> #include <queue> #include <iostream> #include <utility> #include <cstdio> #include <string.h> #include <vector> using namespace std; long long int d[10010]; long long int tmp[10010]; int main(){ long long int n; scanf("%lld",&n); for(in…</vector></string.h></cstdio></utility></iostream></queue></string></algorithm></set>

問題文典型DP。やるだけ。頭悪い。 #include <set> #include <algorithm> #include <queue> #include <utility> #include <cstdio> #include <string.h> #include <vector> using namespace std; typedef pair<int,int> P; P dp[5003]; int a[5003]; int main(){ int n; for(int i = 0;i <= 5000;i++){ dp[i].first = 1; } scanf(</int,int></vector></string.h></cstdio></utility></queue></algorithm></set>…

個数制限付き部分和問題完全に蟻ゲー詳しくは蟻本p62参照 #include <algorithm> #include <string.h> #include <iostream> #include <cstdio> using namespace std; int a[11]; int m[11]; int dp[100003]; int main(){ int cash; while(cin >> cash){ int n; scanf("%d",&n); for(int i = 0;i < n;i</cstdio></iostream></string.h></algorithm>…

英語読めなさすぎ。冷える。 #include <cstdio> #include <algorithm> using namespace std; int d[30004]={0}; int main(){ int n; int ans = 100000000; int tmp = 0; scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&tmp); d[i] = d[i-1]; if(tmp==1)d[i]++; } int </algorithm></cstdio>…

USACOの簡単な問題 計算するだけ #include <cstdio> using namespace std; int main(){ int n,k; scanf("%d%d",&n,&k); while(k--){ int ans = 0; int s,t,r; scanf("%d%d%d",&s,&t,&r); int ka = n / s; if(n % s != 0)ka++; ans += ka; int q = ka / t; if(ka % t </cstdio>…

詳しくは蟻本p99参照クラスカルやるだけ。unionfindとkruskalなんも見ないで実装できたのでgood. #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 20003; const int MAX_E = 50003; int par[MAX_N]; int rank[MAX_N]; struct edge{int from,to,</algorithm></cstdio>…

昨日の夜POJ落ちてたが復旧していた。SegmentTreeつかわなくてもできそうだが練習のため使用。LanguageをG++ではTLEになったがC++にしたら通った。 POJの闇である。 #include <cstdio> #include <climits> #include <algorithm> #include <utility> #include <iostream> //http://poj.org/problem?id=2823 us</iostream></utility></algorithm></climits></cstdio>…

ﾀﾞｲｸｽﾄﾗやってごにょごにょするだけ #include <cstdio> #include <queue> #include <utility> #include <climits> using namespace std; typedef unsigned long long int ll; typedef pair<ll,int> P; struct edge{int to,cost;}; const ll INF = ULLONG_MAX; ll d[50003]; int v,e; priority_queue<P, vector<P>,gr</p,></ll,int></climits></utility></queue></cstdio>…

POJスランプに陥ったPOJ2027 poj1003 poj1942 poj2665 poj2196

つまり (a+b)!/a!b!するだけ #include <cstdio> #include <utility> using namespace std; int main(){ while(1){ long long int a,b,ans; scanf("%lld%lld",&a,&b); if(a == 0 && b == 0)break; if(b>a)swap(a,b); ans = 1; for(long long int i = a+b;i > a;i--){ ans *= i;</utility></cstdio>…

poj1218 計算・楽しい poj1046 探索 poj1664 典型DP poj3006 エラトステネスのﾌﾙｲ・楽しい poj1006 やるだけ・楽しいPOJ1218が美しくかけたので載せる。 #include <iostream> using namespace std; int d[102],t,co; int main(){ for(int i = 1;i <= 100;i++){ co = 0;</iostream>…

poj1922 やるだけ poj2350 やるだけ poj2533 典型DP poj1012 数学 poj1852 蟻

問題概要 文字数N( 与えられた文字列を回文にするには最小何文字新たに挿入すればよいか。 解法 N まず、左から読んだときの文字列と右から読んだときの文字列について最長共通部分列を求める。 真ん中になる文字を決め、その文字から右の文字列と左の文字列…

解法：ナイーブな実装.O(N^4).O(N^4)になるのでダメ、といっているものを拝見しましたが、実はO(N^4)でいけます。（ちょっと工夫が必要だけど累積和を二次元にするだけです。 難しく考えすぎるとかえってダメな場合もありますね、、、。 #include <cstdio> #include <algorithm></algorithm></cstdio>…

究極のやるだけ。 誤読しててつらかった。 プログラミングよりも英語読むほうが難しく感じた・ #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ int m,t,u,f,d; int p[3]={0}; int ans = 0; scanf("%d%d%d%d%d",&m,&t,&u,&f,&d); char s; i</iostream></algorithm></cstdio>…

問題概要 学生の数(n)、クエリの数(m)が与えられる。各クエリはn以下の二つの整数があり二人の学生は同じ宗教であることを示している。 学校内で予想できる最大の宗教の数はいくつかもとめる。 解法 Union-Findやるだけ 自分が親であるのをカウント。これも…