問題 英語でなんかいろいろ書かれているが、ようは中央値をもとめよということ 解法 ソートして真ん中の値を取り出すだけ。 #include <cstdio> #include <algorithm> using namespace std; const int MAX = 10001; int d[MAX]; int N; int main(){ scanf("%d", &N); for(int i =</algorithm></cstdio>…

問題 解法 動的計画法をつかうA(t,p) := (時間tに木pからりんごが落ちてくる) ? 1 : 0 dp[t][p][w] := 時間tで,木pの下にいて,移動回数w以下のときの最大のりんごの数と定義すると、漸化式はdp[t][p][w] := max(dp[t][p][w+1], max(dp[t-1][p][w] + A(t,p), …

問題 解法 グラフの2彩色判定をすればいい。深さ優先探索を用いるとできた。 コードに無駄ありすぎぃな感がある。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 2000; int T, N, M; bool interact[MAX_N][MAX_N]; bool used[MAX_N]; char co</algorithm></cstdio>…

問題 辞書データとクエリが与えられるので、翻訳した結果を表示せよ。 辞書に載っていない場合"eh"と表示せよ 解法 辞書データはmapで管理した。 入力の処理に少し工夫が必要。 #include <cstdio> #include <cstring> #include <string> #include <map> #include <algorithm> using namespace std; typ</algorithm></map></string></cstring></cstdio>…

問題 '@'から縦横に進んでいけるマスの個数をもとめよ 解法 深さ優先探索をしてもとめる #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>…

問題 解法 動的計画法を使う。 三角形を高さ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>…

問題 解法 カンニングした 配列を作って、コピペする。 配列作成用 #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>…

問題 解法 動的計画法をつかえば解ける。 詳しくはソース中のコメントみてください。 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>…

問題 数字と表示サイズがあたえられるので、電卓とかのディスプレイ風にして出力せよ。 例) INPUT: 2 12345 3 67890 0 0 OUTPUT: -- -- -- | | | | | | | | | | | | -- -- -- -- | | | | | | | | | | -- -- -- --- --- --- --- --- | | | | | | | | | | | | …

問題 N このとき、1 #include <cstdio> using namespace std; int n; int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i){ int i3 = i * i * i; int a3, b3, c3; for(int a = 2; a < i; ++a){ a3 = a*a*a; for(int b = a + 1; b < i; ++b){ b3 = b*b*b; if(i</cstdio>…

勉強する気がおきない。問題 単語が与えられる。辞書式配列で、並び替えたものをすべて列挙せよ。 重複はだめ。 解法 やるだけ。 辞書の順序が AaBbCc...Zzとなっているのでこれに注意し、文字数値の変換用配列を作っておくと便利。 重複がダメなので、使っ…

英語読めるようになってきた。 そんなことより、Haskellできるようになりたい 問題 1からnまでのn個の部屋があり、すべて閉まっている。次の操作をn回行う。 [操作]現在i回目で、iで割りきれる部屋番号の部屋が、 開いている ->閉める 閉まっている->開ける …

問題 うわさを広げたい。ある人から他の人へうわさが伝わるのにかかる時間がそれぞれあたえられる。 この時、一番はじめに誰にうわさを吹き込めば一番早くうわさが全体に広がるかを 計算し、さらにかかる時間を求めるプログラムを作れ。解法 重み付き有向グ…

問題 座標が整数の点がN個(1解法 点を2個決め、その２点を通る直線は何個の点を通るか調べていけばいい。3点 p1(x1,y1), p2(x2,y2), p3(x3,y3)が一直線上にある時、次の式が成立する。 (x2 - x1) * (y3 - y1) = (x3 - x1) * (y2 - y1) [証明] p1,p2を通る直…