AOJ
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0556 解法 座標x,yを次のように変換する nx = min(x, N+1-x) ny = min(y, N+1-y) するとタイルの左上の4分の1の範囲だけで考えることができて、 場合分けしなくてよいので楽 あとは適当にmod…
三角関数を使うだけ 出力形式を間違えていて、WA量産しまくった。 問題文をよく読もう(小学生並) #include <cstdio> #include <cmath> using namespace std; const double PI2 = 3.1415926535 * 2; int main(){ double x=0, y=0; double r = 0.0; int N; double d; while(sc</cmath></cstdio>…
解法 外接円は辺の垂直二等分線だから、適当に方程式作って解かせるだけ。 0で割り算しないように、分母が0になるときは適当な小さい値を足してしまえばいい #include <cstdio> #include <cmath> #include <algorithm> using namespace std; double jijo(double a){ return a*a; } int </algorithm></cmath></cstdio>…
解法 やるだけ #include <cstdio> #include <algorithm> using namespace std; const int MAX = 10; int a[MAX+4][MAX+4]; int lx[13]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2}; int ly[13]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0}; int mx[9]={-1,-1,-1,0,0,0,1,1,1}; int my[9]={-1,0,1,-1,</algorithm></cstdio>…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114解法 (x,y,z) = (1,1,1) を {x' = a1*x mod m1 {y' = a2*y mod m2 {z' = a3*z mod m3 で計算していくと、再び(1,1,1)になるという条件から xだけでみたとき、xが再び1になるまでの計算回…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011解法 T日にスケジュールのあいている子孫の集合をCtとする 子孫cがT日に持っている地図の集合をMctとするMct = Mc(t-1) (c ∈ Ct でない) ∪{Md(t-1) | d ∈ Ct} (c ∈ Ct) を計算していって…
じりきで解けなかった。 漸化式作るのむずかしすぎ(頭悪い) #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 15; int N, M; int cup[MAX_N]; int main(){ while(scanf("%d %d",&N,&M)&&N!=0){ for(int i=0; i<3; i++){ int K; scanf("%d", &K);</algorithm></cstdio>…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 100; int N,M,S,G0,G1; int cost[MAX_N][MAX_N]; int min_cost[MAX_N][MAX_N]; int wf(){ for(in</algorithm></cstdio>…
地道にシミュレーションする。 時間ギリギリだった #include <cstdio> #include <algorithm> using namespace std; int main(){ int N; while(scanf("%d",&N) && N!=0){ int stone[N]; for(int i=1; i<=N; i++){ int t; scanf("%d", &t); if(i%2==1) stone[i-1] = t; else{ for(</algorithm></cstdio>…
yarudake #include <cstdio> #include <cstring> using namespace std; int main(){ char str[11], c; int N, len; char ring[11]; scanf("%s", str); scanf("%d", &N); int ans=0; for(int i =0; i</cstring></cstdio>
明日テスト…… 簡単なやつをやったテーブルを作るだけの簡単なお仕事 #include <cstdio> using namespace std; const int d[11][7]={ {0,1,1,1,1,1,1}, {0,0,0,0,1,1,0}, {1,0,1,1,0,1,1}, {1,0,0,1,1,1,1}, {1,1,0,0,1,1,0}, {1,1,0,1,1,0,1}, {1,1,1,1,1,0,1}, {0,1</cstdio>…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213解法 全探索すればいいらしい。実装キツい。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; const int MAX_N = 15; const int MAX_XY = 10; int N, X, Y; int memo[MAX_N];</int,int></algorithm></cstdio>…
PCK本選に向けての練習 1日1ACを目標にしている。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0211解法 d[i], v[i] のときの周回数を m[i] 回とし、周回時間 d[i]/v[i]*m[i]=T 時間とする(Tは一定の値) このとき (m[i]=) T*(v[i]/d[i]) …
JOI予選のとき、動的計画法ということには気づいたけど頭悪いのでどうすればよいか分からなかった問題。 教訓：とりあえず再帰関数 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 解法 動的計画法またはメモ化再帰をつかう。 メモ化…
JOI予選のとき、問題文を読む前からあきらめてしまった問題。 今回やってみたら20分でできた。成長したなー。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569解法 六角形の移動先配列を持ちながら深さ優先探索 #include <cstdio> #include <algorithm> usi</algorithm></cstdio>…
解法 座標圧縮+DFS はじめて座標圧縮した。 解説を参考にして解いた #include <cstdio> #include <algorithm> #include <set> using namespace std; const int MAX_N = 1000; int N, h, w; bool a[MAX_N * 2 + 3][MAX_N * 2 + 3]; int dx[4] = { 1, -1, 0, 0}; int dy[4] = { 0, 0, 1</set></algorithm></cstdio>…
PCKに参加することになったので練習しています。 まだまだ先ですけどね問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113解法 筆算をするようにやっていく。 余りを配列に記憶しておいて、 以前と同じ余りが存在している⇔循環している を…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202以前問題を見たとき「あ、これ無理なやつだ」と思ったもの。 できるようになっていた。解法 素数の金額が作れるかを調べるのに動的計画法を用いる。 ↑この発想がむりだった。 k[i] := 品物iの…
PKUが死んでた http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0139解法 地道にチェックするコードを書く もっとスマートにできないかなぁ。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[250]; bool cA(){ int l = 0, i; for(i </algorithm></cstring></cstdio>…
高校生活というものが分かってきた問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0133解法 やるだけ #include <cstdio> #include <algorithm> using namespace std; char a[8][8]; void turn(){ char b[8][8]; for(int w = 0; w < 8; w++){ for(int h = 7; h </algorithm></cstdio>…
問題 解法 駅は番号で管理するとやりやすい。駅名と駅番号を対応付けるためにmapをつかう。 あとはダイクストラかワーシャルフロイドすればいい。 #include <iostream> #include <cstdio> #include <vector> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; const int I</algorithm></queue></map></string></vector></cstdio></iostream>…
問題 解法 構文解析するだけ。 しなくてもできそう。 解析したあとは、再帰で一番上のパネルを求めることができる #include <cstdio> #include <string> #include <vector> #include <algorithm> using namespace std; //タグ class T{ public: string name; int x1, y1, x2, y2; vector<T> ko; //</t></algorithm></vector></string></cstdio>…
問題 解法 代金をpとすると,実際に払う金額Pは p だから,全部ためしていくといい. #include <cstdio> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i</algorithm></cstdio>
問題(AOJ) 問題(POJ) 解法 エラトステネスの篩をつかうだけ。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char prime[1000000]; int a, d, n; int main(){ memset(prime, sizeof(prime), 0); prime[1] = 1; for(int i = 2; i <= 1000; i++){ if(pr</algorithm></cstring></cstdio>…
問題 解法 テーブル作ってやるだけ。 #include <cstdio> using namespace std; const char table[10][9] = { "* = ****", "* =* ***", "* =** **", "* =*** *", "* =**** ", " *= ****", " *=* ***", " *=** **", " *=*** *", " *=**** ", }; int main(){ int n; boo</cstdio>…
問題 解法 普通に2進数に変換すればいい。 #include <cstdio> #include <algorithm> using namespace std; const double EPS = 1e-9; const double bit[] = {128.0, 64.0, 32.0, 16.0, 8.0, 4.0, 2.0, 1.0, 0.5, 0.25, 0.125, 0.0625}; int main(){ double r; while(scanf("%lf"</algorithm></cstdio>…
問題 解法 ダイクストラ法を使って、ああでもないこうでもないとやっている うちになぜか解けてしまったのでよくわからない。 動的計画法も使っているような気がする…だけかもしれない。 割引券の枚数に対する最短距離？みたいなのを計算していく？というよ…
問題 getlineの使い方がわからないのでコードが変になった↓恐ろしく非効率なコード #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char text[3][5] = { "this", "the", "that", }; char S[100]; char A[100]; int len; void solve(){ char </algorithm></cstring></cstdio></iostream>…
問題 解法 △ABC = △PAB + △PBC + △+PCA がなりたてば内部にある。 面積はベクトルの外積を使えば求まるらしい。 #include <cstdio> #include <algorithm> #define EPS 1e-9 class P{ public: double x, y; double cross(P p){ //外積を求める return (x * p.y - y * p.x); } P o</algorithm></cstdio>…
問題 解法 は0点の的に当たったとしてあつかえばいい。n回目に投げたダーツの得点をPnとすると、 P1 + p2 + P3 + p4 が成り立つようにしなければならない。このまま計算すると、計算量は O(N^4) となりN ここで、式を変形して、 P3 + P4 これを計算する 2つ…
