問題 '@'から縦横に進んでいけるマスの個数をもとめよ 解法 深さ優先探索をしてもとめる #include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 20; char a[MAX_HW + 2][MAX_HW + 2]; int H, W, sx, sy; const int dx[] = { -1, 0, 0, 1}; const int</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> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef pair<int, int> P; //最小コスト、位置 const int INF = 1 << 30; const</int,></queue></vector></algorithm></cstdio>…

問題 グラフの頂点1からNまでの経路のうち、二番目に短いものの長さを求めよ。 解法 蟻本を参考にした。 ダイクストラ法を使って最短路と二番目の最短路を更新しながら計算していく。 #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef</vector></queue></algorithm></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つ…

問題 解法 対話型プログラムを書く変わった問題。おもしろい。AIの単語をsetを使って記録しておく。 自分の言う言葉の生成方法はいろいろあるが、bitで管理することにした。 具体的には以下変数iを用意して0で初期化する。 (1) i++; (2) 単語生成 1文字め…AI…

問題 解法 解説みた。 縦の列はたかだか10列しかないので縦の反転をすべて試していく。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_R = 10, MAX_C = 10000; int R, C; int senbei[MAX_R][MAX_C]; int count(){ int f, b; int res = 0; for(int</algorithm></cstdio>…

問題 解法 ダイクストラ法で解いた。 うろ覚えで書いて正直通ると思っていなかったのに、通ってうれしい。 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; typedef pair<int ,int> P; //first 距離 second 位置 const int MAX_N = 100, INF = 1 << 30;</int></algorithm></vector></queue></cstdio>…

問題 解法 動的計画法を使う。 三角形を高さiの二次元配列に入れたとき、漸化式は dp[i][j] = triabgle[i][j] + max(dp[i-1][j], dp[i-1][j-1]) #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 101; int tri[MAX_N][MAX_N]; int dp[MAX_N][MAX</algorithm></cstdio>…

問題 解法 STLゲー。 map を使って単語と出現ページの情報を管理する。 #include <cstdio> #include <iostream> #include <map> #include <queue> #include <string> #include <vector> #include <algorithm> using namespace std; typedef priority_queue<int, vector<int>, greater<int> > PAGE; typedef map<string, PAGE> INDEX; int main(){ char b…</string,></int></int,></algorithm></vector></string></queue></map></iostream></cstdio>

問題 解法 STLゲー。mapをアイテムの値段用とレシピ用に2つ使う。 再帰で最小の金額を求めていく。 #include <cstdio> #include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; typedef map<string, int> ITEM; typedef map<string, vector<string> > RECIPE; ITEM item; RECIPE recipe; int solve</string,></string,></algorithm></vector></map></iostream></cstdio>…

問題なんか前にも解いたことがあるような気がするが、きっと気のせい。 #include <cstdio> using namespace std; int main(){ int a[4], b[4]; while(true){ for(int i = 0; i < 4; i++){ if(scanf("%d", &a[i]) == EOF) return 0; } for(int i = 0; i < 4; i++){ sc</cstdio>…

問題 解法 優先順位付きキューを使って橋にかかる重さの変化を管理するとやりやすい。 体重Mの人が時刻Aに橋を渡り始めた---> (A, M)をプッシュ 体重Mの人が時刻Bに橋を渡り終えた---> (B, -M)をプッシュ すべてキューにつっこんだあと、時刻の小さいほうか…

問題 解法 貪欲法を使って、値段の高いものから順に袋に入れていけばいい。 つまり、値段の高い順にソートして、mで割りきれる番号の値段以外の合計を求める。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 1000; int yasai[MAX_N]; int mai</algorithm></cstdio>…

問題 解法 2つの数字を読み込んでから、文字列に変換するとやりやすい。 #include <cstdio> using namespace std; char r[5], a[5]; int main(){ int rd, ad; while(scanf("%d %d", &rd, &ad) && rd){ sprintf(r, "%04d", rd); sprintf(a, "%04d", ad); int hit = 0,</cstdio>…

問題 解法 1年1月1日から何日経過しているかを計算するといい。 この時、フェアフィールドの公式を使うと便利。 #include <cstdio> using namespace std; int dc(int y, int m, int d){ if(m <= 2){ y--; m += 12; } return 365*y+y/4-y/100+y/400+306*(m+1)/10+d-42</cstdio>…

問題 解法 カンニングした 配列を作って、コピペする。 配列作成用 #include <cstdio> using namespace std; int a[14]; bool c(int k, int m){ int i = 0, p; for(p = 2 * k; p > k; p--){ i = (i + m - 1) % p; if(i < k) return false; } return true; } int main</cstdio>…

問題 カードを台に積み上げていく。 台からカードがはみでた部分の長さ(A)が与えられるので、その長さのはみ出しを つくれる最小のカード枚数を出力せよ。 カードがn枚のとき、作れるはみ出しの長さLは次の式で求められる。 L = 1/2 + 1/3 + 1/4 + ... + 1/(…

蟻本を参考にした。 二分法で解の存在する幅を狭めていく。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int N, K; double L[MAX_N]; bool c(double t){ int s = 0; for(int i = 0; i < N; i++){ s += (int)(L[i] / t); } return s </algorithm></cstdio>…

問題 解法 全部足して、(k-1)で割ればいい。 #include <cstdio> using namespace std; int main(){ int k,t,s,i; while(scanf("%d",&k)&&k){ s = 0; for(i=0;i < k*(k-1)/2;++i){ scanf("%d", &t); s += t; } printf("%d\n",s/(k-1)); } return 0; }</cstdio>

問題 やるだけ。 はじめ、与えられる整数が100以下という条件をよみ忘れていて、へんなことをしていた。 #include <cstdio> #include <algorithm> using namespace std; int n[101]; int main(){ int i,m=0; while(scanf("%d", &i) != EOF)n[i]++; for(i=0;i<101;i++)m=max(m,n[</algorithm></cstdio>…

問題 解法 動的計画法をつかえば解ける。 詳しくはソース中のコメントみてください。 O(F*V)だからはやい。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_F = 100, MAX_V = 100, MINF = -(1<<29); int F, V; int table[MAX_F + 1][MAX_V + 1]; i</algorithm></cstdio>…

あしたじゅけーーん 問題 解法 筆算するみたいにやっていけばいい。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_K = 80; char num1[MAX_K + 1]; char num2[MAX_K + 1]; char numS[MAX_K + 1]; int k1, k2; bool plus(){ int t = 0, </algorithm></cstring></cstdio>…

問題 解法 問題文にかかれている通りにやるだけ。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 12; int S[MAX_N], T[MAX_N], N; int main(){ while(scanf("%d", &N) &&N){ int ans; for(int i = 0; i < N; i++) scanf("%d", &S[i]); for(an</algorithm></cstdio>…

問題 解法 直方体の3種類の大きさの面のうち、いづれかが穴の中に収まるなら、 その直方体は穴を通り抜けられる。 穴の半径をR,面の縦の長さをa,面の横の長さをbとすると 面が穴に収まるかの判定は、三平方の定理を用いて、 (2R)^2 > a^2 + b^2 をみたすかど…