与えられた点の集合の中から最大の正方形を探し 面積を出力する問題。２点を決めると、正方形の残り２点が決まるので 残りの２点を二分探索で探した。 #include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; double EPS = 1e-10; double add(double a, </algorithm></cmath></vector></iostream>…

与えられた点と同じ形を点の集合の中から探し、 平行移動する量を出力する問題。二分探索で一つずつ探した。 #include<iostream> #include<vector> #include<set> #include<climits> #include<cfloat> #include<cmath> #include<algorithm> using namespace std; double EPS = 1e-10; double add(double a, double b){ i</algorithm></cmath></cfloat></climits></set></vector></iostream>…

点p(px,py)から速度ベクトルvで打ち出されたレールガンが 原点にたどり着く距離を出力する問題。原点にたどり着くには、一度も反射せずたどり着くか 反射してたどり着くしかない。 後者の場合は反射角が９０度になっていなければならない。cosθ= p・v / |p||…

動的計画法で解いた。dp[ i ][ j ]:=i番目までのカードでj円を作れるパターンの数 #include<iostream> using namespace std; int main(void){ int m,a[8],b[8],g,n,dp[8][1001]; while(cin >> m,m){ for(int i=0;i<8;i++){ for(int j=0;j<1001;j++){ dp[i][j]=0; } } f</iostream>…

メモ化再帰で解いた。dp[ i ][ j ]:=i番目までの計算結果がjのパターン数最初が0の時を考えてなかったせいでWA連発した。 #include<iostream> using namespace std; typedef long long ll; ll dp[101][21]; int a[101],n; ll func(int i, int res){ if(res<0 || 20<res)return 0; if(dp[i][res]>0)re</res)return></iostream>…

上の1行の粒子の通し方を適当に決める。 その後2行目から、前の行を0で揃えるように粒子を通して行く。 つまりa[i][j]をみているとき、a[i-1][j]が1であればa[i][j]に粒子を通す。 最後の行まで通し終わり、すべて0で揃っていたらその通し方が答え。以上を最…

エラトステネスのふるいで十分な数の素数を求める。 Ｎより大きい素数の配列を適当な数まで作り それぞれの和を計算した。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ vector<int>num,ans; int n,p,prime[1000001]; for(int i=0;i<1000001</int></algorithm></vector></iostream>…

x,y,z座標の値をもつ構造体cubeを作り 入力された列をsetに入れて重複を消し (nの三乗)-(setのサイズ)を出力する。 #include<iostream> #include<algorithm> #include<set> using namespace std; struct cube{ int x,y,z; }; bool operator<(const cube& left, const cube& right){ if(</set></algorithm></iostream>…

つららの長さがすべて0になるまでの時間を求める。 lをつららの長さの上限として、dp[i]:=i番目のつららの長さa[i]がlになるまでの時間if(a[i]>a[i-1] && a[i]>a[i+1])dp[i] = l-a[i] else dp[i] = max(dp[i-1], dp[i+1]) + l-a[i] #include<iostream> #include<vector> #inclu</vector></iostream>…

メモ化再帰で解いた。 dp[i][j][p]:=現在(i,j)にいて、状態pである。i…南北 j…東西p= 1…直前に曲っていて、東に進んでいる →東に進み、p=32…直前に曲っていて、北に進んでいる →北に進み、p=43…直前に曲っていない、東に進んでいる →東に進み、p=3 または 北…

y=(i*d)*(i*d) x=d である長方形の面積を足しあわせる。 #include<iostream> using namespace std; int main(void){ int d; while(cin >> d){ int sum=0; for(int i=1;i<600/d;i++) sum+=i*i*d*d*d; cout << sum << endl; } return 0; }</iostream>

スタックを使う問題。 #include<iostream> #include<stack> using namespace std; int main(void){ int x; stack<int>st; while(cin >> x){ if(x==0 && !st.empty()){ cout << st.top() << endl; st.pop(); } else st.push(x); } return 0; }</int></stack></iostream>

¨01234567¨を作るまでの最短手数。 幅優先探索で¨01234567¨からすべての 状態までの操作回数をmapに作っておく。 #include<iostream> #include<string> #include<algorithm> #include<queue> #include<map> using namespace std; int dx[4]={1,-1,4,-4}; map<string,int>res; void bfs(void){ queue<string>que; que.push("</string></string,int></map></queue></algorithm></string></iostream>…

一文字を別の文字に変える操作を繰り返し、 左右対称な文字列を作るまでの最短手数。 #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; int main(void){ string s; while(cin >> s){ int cnt=0; for(int i=0;i</vector></string></algorithm></iostream>

点が三角形の内部にあるかを判定する。解答中の関数 dot()→内積 cross()→外積 is_point_on_line()→点が線分の上にあるか。 is_intersected_ls()→線分の交差判定。 inside()→点が多角形の内部にあるか。関数 inside(point p, vector ps) 点pが多角形psの内部…

#include<iostream> #include<algorithm> using namespace std; int main(void){ int x,y,a,b,n[31]; char s; cin >> y >> x; for(int i=1; i<=y; i++)n[i]=i; for(int i=0; i<x; i++){ cin >> a >> s >> b; swap(n[a],n[b]); } for(int i=1; i<=y; i++)cout << n[i] << endl; return 0; }</x;></algorithm></iostream>

circumscribed_circle()→３点を通る円を求める関数。 #include<iostream> #include<cmath> #include<cstdio> using namespace std; struct point{ double x, y; }; struct circle{ point p; double r; }; circle circumscribed_circle(point p, point q, point r){ double a[2],b[2],c</cstdio></cmath></iostream>…

エラトステネスの篩。 prime→素数なら0,それ以外は1の配列。 ans→i番目までの素数の個数。 #include<iostream> using namespace std; int main(void){ int n,prime[1000000],ans[1000000]; for(int i=0;i<1000000;i++)prime[i]=ans[i]=0; prime[0]=prime[1]=1; for(int</iostream>…

#include<iostream> using namespace std; int main(void){ int n; while(cin >> n){ int cnt=0; for(int a=0;a<10;a++) for(int b=0;b<10;b++) for(int c=0;c<10;c++) for(int d=0;d<10;d++) if(a+b+c+d==n)cnt++; cout << cnt << endl; } return 0; }</iostream>

#include<iostream> using namespace std; int main(void){ int n,a=100000; cin >> n; while(n--){ a=a*5/100+a; if(a%1000){ a/=1000; a=a*1000+1000; } } cout << a << endl; return 0; }</iostream>

#include<iostream> #include<string> #include<algorithm> using namespace std; int main(void){ string str; cin >> str; reverse(str.begin(),str.end()); cout << str << endl; return 0; }</algorithm></string></iostream>

a,bの最大公約数 GCD(a,b)→ユークリッドの互除法 a,bの最小公倍数 LCM(a,b)→LCM(a,b)=a*b/GCD(a,b) #include<iostream> using namespace std; int GCD(int a, int b){ return !b ? a : GCD(b, a%b); } int main(void){ long long a,b,gcd,lcm; while(cin >> a >> b){ g</iostream>…

#include<iostream> #include<cstdio> using namespace std; int main(void){ double x,y; double a,b,c,d,e,f; while(cin >> a >> b >> c >> d >> e >> f){ x=(c*e-b*f)/(a*e-b*d); y=(c*d-a*f)/(b*d-a*e); if(x==-0)x=0; if(y==-0)y=0; printf("%.3f %.3f\n",x,y); } return </cstdio></iostream>…

ピタゴラスの定理。 #include<iostream> using namespace std; int main(void){ int n,a,b,c; cin >> n; while(n--){ cin >> a >> b >> c; if(a*a+b*b==c*c||a*a+c*c==b*b||b*b+c*c==a*a)cout << "YES" << endl; else cout << "NO" << endl; } return 0; }</iostream>

#include<iostream> using namespace std; int main(void){ int a,b; while(cin >> a >> b){ int sum=a+b,ans=1; for(; sum>=10 ; sum/=10,ans++); cout << ans << endl;; } return 0; }</iostream>

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ int h; vector<int>hill; for(int i=0;i<10;i++){ cin >> h; hill.push_back(h); } sort(hill.begin(),hill.end(),greater<int>()); for(int i=0;i<3;i++) cout << hill[i] << endl; return 0; }</int></int></algorithm></vector></iostream>

#include<iostream> using namespace std; int main(void){ for(int i=1;i<10;i++) for(int j=1;j<10;j++) cout << i << "x" << j << "=" << i*j << endl; return 0; }</iostream>