問題 解法 幅優先探索する。ジャンプ先の配列を用意しておくと便利。 領域外に出てしまったときの処理を書き忘れていて、すこし手間取った。コード #include <cstdio> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; //座標 typedef pair<int, P> Q; //噴水の番</int,></int,></algorithm></queue></cstdio>…

問題 解法 テーブルを作る。 数字を読んで変な数字がないか確認。 文字列出力。で解ける。 コード #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char i2a[5][7] = { "afkpuz", "bglqv.", "chmrw?", "dinsx!", "ejoty " }; int main(){ char s[300]; </algorithm></cstring></cstdio>…

ものずごく実装問題。 さらに変な解き方をしたため、どこで何をしているコードなのか自分でも分からなくなった。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<bool, int> P; int num[9][9]; //書いてある数字 int map[9][9]; bool b[9][9]; //書いてある数</bool,></algorithm></cstdio>…

解くためには、国語を勉強して作者の気持ちを読みとる能力をつける必要のある問題。 書かれるべき条件がいろいろと足りない。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 4000; long long p[MAX_N]; //売上金額 long long num[MAX_N]; //</algorithm></cstdio>…

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

雪がかなり降っている。寒いいいい 実装がかなり難しかった。実装力ないのをどうにかしたい。 問題 略 解法 色ごとにカードをわけ、3枚ずつ選ぶ選び方をすべて試すというやり方をした。 カード1セットあたり最悪でも3*9C3*6C3=5040の計算しかしないので間に…

アルゴリズムデザインにのっていたので、c++で実装してみた。 系列アライメントとは、Googleの「もしかして:」の機能のような似ている文字列を探すやつのこと。 二つの文字列で動的計画法を使って類似度を計算する。入力単語(辞書) ... # チェックする単語 .…

アルゴリズムデザインにのっていた問題。 本当は動的計画法を使うらしいけど、よく分からないので、BFSした。問題 木が与えられる。この木の根から情報を発信する。情報は、時間１の間に各ノードから そのノードの１つの子ノードにしか送ることができない。 …

英語読めるようになってきた。 そんなことより、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を通る直…

Haskellで2分探索をつかい入力された値の平方根を求めるプログラムを作ってみた。 EPSで精度を変えられる。 inf = 1000000000 eps = 0.0000001 main = getContents >>= putStrLn . show . root 0.0 inf . read root l h n = let ave = (l + h) / 2.0 in if (…

haskellの練習のために、フィボナッチ数を計算するプログラムを作った。 nを入力すると第n番目のフィボナッチ数を返す。 O(n)で計算できるようにした。 モナドはあまり理解できていないが、かっこよさそうなので利用してみた。(>>=) f :: Int -> Int -> Int …

問題 略解法 計算量はどんなに悪くても n^2 * m^2 * 4 = 10000 * 250 * 4 = 10000000 より少ないので、 全探索すれば大丈夫。正確な計算をすると、もっと小さくなる。回転させた図形の作り方 １、回転させる二次元配列(p[x][y])に、 (下から上に一列とりpn[x…

問題 略 解法 一番大きいのを選ぶだけ。 C++ と Haskell で書いてみた Haskellはまだ勉強中なので、もっといいやり方があったら誰か教えてください。 実装 c++ #include <cstdio> #include <algorithm> using namespace std; int main(){ int n, ans, d; while(scanf("%d", &n) </algorithm></cstdio>…

haskellという関数型言語の勉強を始めました。 まだよく分かっていませんが、おもしろい言語だとおもいます。 標準入力から数列を読み取りクイックソートするプログラムを書いてみました。 import Char main = do cs <- getContents putStrLn $ unwords $ ma…

「アルゴリズムデザイン」にのっている演習問題。 ストーリーが、某主人公が救世主になってマシンと戦争する映画にとてもにている。がその辺は省略。 問題 n秒間に渡りロボットがくる。i秒目にはXi台のロボットがくることが分かっている。 ロボットを倒すた…

問題 略解法 携帯電話のボタンごとの文字の割り当てを配列にしておくとやりやすい。実装 #include <cstdio> #include <cstring> using namespace std; char c[10][6] = { "", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", }; int buf[1024]; void mes</cstring></cstdio>…

問題 略解法 線形合同法を使って疑似乱数を実際に生成しシミュレーションするだけでいい。実装 #include <cstdio> #include <algorithm> using namespace std; int A, B, C; int nX; const int MAX_N = 100; int N, num[MAX_N]; void rng(){ nX = ((A * nX) % C + B) % C; } int</algorithm></cstdio>…

問題 M(N, P) = Nより大きい2つの素数の和をとることで得られる数を，小さいほうから順に並べたとき，P 番目の数 M(N, P)を求めよ。 0 ≤ N ≤ 100,000 1 ≤ P ≤ 100解法 はじめにエラストテネスの篩で素数をたくさん求めておく。 Nより大きいP個の素数をみつけ…

やるだけ。 一番枚数の少ない文字の数が、作れる看板の数の最大値である。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[310]; int main(){ int K, U, P, C; K = U = P = C = 0; scanf("%s", s); for(int i = 0; i < strlen(s); i++){ if(s[i</algorithm></cstring></cstdio>…

完全数か不足数か過剰数かを判定する問題。約数の和をどうやって求めるかが重要。 n=100000000だからすべての数を調べるのは困難。調べたら、 √n = 10000 回のループで できるそうです。 1 if(n % i == 0){ S += i + n % i; if(i == n % i) S -= i; } これで…

グラフ理論の勉強によさげなのがあったのでリンクを貼っておく。 北海道大学 グラフ理論講義ノート

最短距離を、ループを回しどんどん更新して求めていく。 更新されなくなったら、最短距離が確定する。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 21; const int MAX_N = 100000; //d[i] := i番目のマスからゴールにつくまで最小の、サ</algorithm></cstdio>…

3をかけていくだけの簡単なお仕事です。 #include <cstdio> using namespace std; const int MAX_N = 20; long long table[MAX_N + 1]; int main(){ int n; table[1] = 3; for(int i = 2; i <= MAX_N; i++) table[i] = table[i-1]*3; scanf("%d", &n); for(int i = 1</cstdio>…

何人の友達と海にいけるか求める問題。table[i] := i人(自分をふくめて)で海にいくとき、ついてきてくれる友達の数table[i] + 1 >= i となるとき、i人で海にいけるから、自分を引いて(i-1)人が答え。 友達を誘うにはこんなことより、コミュニケーションが大…

有名な「僕は友達がいない」の問題 直接の友達の数を数える->友達の友達を数える の順番でプログラムをつくる。 直接の友達にしるしをつけておいて、友達の友達を判断する。 このとき、友達の友達にも、しるしを付けないと重複して数えてしまうので注意する…

あけましておめでとうございます 今年はよりいっそう競技プログラミング精進しようと思います。 今年もよろしくおねがいします。↓年賀状用にC言語で書いてみた #include <stdio.h> char tatu [9] [11] ; void tate (int x, int y , int n){ int ny; for (ny = 0; ny< </stdio.h>…