修学旅行に行くのでパソコンとは長らくおわかれ

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

pojまた落ちた（？） ｹﾞｷﾅｴなう

ﾀﾞｲｸｽﾄﾗやってごにょごにょするだけ #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>…

PKU online judgeにハマった。 もはや中毒者になってきている。

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

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

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

ちょっと考えたら解法が浮かんでくるのではないだろうか。 解法： d[i]をi番目のつららの長さとする。 まず、一番長いつららd[i]が折れるのにかかる時間はL-d[i]である。 次に、二番目にながいつららについて、その両隣のどちらかに自分より長いつらら（つま…

ヤバ問 解説は後ほど #include <cstdio> #include <algorithm> using namespace std; const int INF = 10000000; int n,t[10003]; int dp[2][5101][2]; int main(){ scanf("%d",&n); for(int i = 0;i < n-1;i++){ scanf("%d",&t[i]); } for(int i = 0;i < 2;i++){ for(int j = 0</algorithm></cstdio>…

累積和 入門 #include <cstdio> #include <algorithm> using namespace std; const int mod = 100000; int main(){ int n,m,d[100003]={0},ans=0; scanf("%d%d",&n,&m); for(int i = 2;i <= n;i++){ int tmp; scanf("%d",&tmp); d[i] = tmp + d[i-1]; } int nau = 1; for(int i </algorithm></cstdio>…

頭が悪い。解法： priority_queueと、二分探索をもちいた。 おそらくJOI解説とほとんどおんなじ。 気が向いたら詳しく説明します。priority_queue、大きいほうからでてくるのすっかり忘れてましたね #include <cstdio> #include <utility> #include <queue> #include <vector> #include <algorithm> usin</algorithm></vector></queue></utility></cstdio>…

解法： それぞれの座標に行く回数をn-1回分まで記録しておき、その回数が奇数だったら最初の文字（東、西）を反転させ、偶数の場合なにもしない。 最後にn回目の散歩の終わる座標を求めて出力。計算量O(HW)。 #include <cstdio> using namespace std; int h,w,n; int</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やるだけ 自分が親であるのをカウント。これも…

問題概要 二つの文字列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>…

やるだけ・ JOI予選っぽい問題だったし一発AC #include <cstdio> #include <algorithm> #include <utility> using namespace std; typedef pair<int,int> P; P p[50003]; int main(){ int n,t; int ans = 0; int d[50003]; scanf("%d%d",&t,&n); for(int i = 0;i < n;i++){ scanf("%d",&d[i]); p[i</int,int></utility></algorithm></cstdio>…

なぜかWAになる こんどまた解き直す。 保存用 #include <cstdio> #include <iostream> #include <algorithm> #include <cstdlib> using namespace std; int n,n2; long long int d[50]; typedef pair<long long int,int> P; P ps[1 << (40 / 2)]; int main(){ while(1){ scanf("%d",&n); if(n == 0)break; for(int i = </long></cstdlib></algorithm></iostream></cstdio>…

顕著な二分探索。なんかにぶたん使わなくても解けるらしいのですがややこしそうなので二分探索を使うほうがいいと思います。 #include <cstdio> #include <algorithm> using namespace std; int nau; int t[100003]; int main(){ while(1){ int d,n,m; scanf("%d",&d); if(d == </algorithm></cstdio>…

m解法の詳細は、連続する"IOI"の数を計算する。（たとえば、IOIOIのとき2） その値をtとすると、ans += max(0,t-n+1)で答えが求まる。 少し考えればできる問題。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ while(1){ int n,m; char s</iostream></algorithm></cstdio>…

難しい。解法についてはJOIの解法を見るよりこちらを参照したほうがいい気がします。AOJ 0531 : Paint Color - きままにものづくり AOJ 0531 : Paint Color - きままにものづくり #include <cstdio> #include <vector> #include <algorithm> #include <queue> #include <string.h> #include <iostream> using namesp</iostream></string.h></queue></algorithm></vector></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>…