兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

12.4 幅優先探索(写経編)

本業でいろいろとやられてまして久しぶりの更新です。まあ写経ですが。。 d という変数名が分かりづらいので distance という名前にしたのですが、iterator の distance と ambiguous(曖昧だ)ってコンパイラに怒られました。 #include <iostream> #include <vector> #include <queue> </queue></vector></iostream>…

12.3 深さ優先探索(写経編)

間が空いた上に写経という。書籍内の回答例は変数名の意味が分かりづらくて辛いので、そこだけ修正しました。 #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; enum COLOR { WHITE, GRAY, BLACK, }; static const int NIL = -1; static const</algorithm></stack></vector></iostream>…

12.2 グラフの表現

これは特に悩むところはなく。これから難しくなると思うので小休憩ですね。 #include <iostream> using namespace std; static const int N = 100; static int M[N + 1][N + 1] = {}, p[N + 1] = {}; int main() { int n; cin >> n; int number, count, value; for (in</iostream>…

11.4 連鎖行列積(写経編)

これも写経です。線形代数の確かな知識がないと、手も足も出ませんね。。 写経だけだとアレなので、boost の matrix を使おうと思いましたが、オンラインジャッジで boost が使えるのかがよく分からなかったのでそのままにしておきました。 #include <iostream> #inclu</iostream>…

11.3 最長共通部分列

またもや写経です。 2つの文字列の最大長を二次元配列で記憶する 文字一致ループの中で1つ前の最大長と比較していく ということですが、この発想が出てこない。。 #include <iostream> #include <string> #include <algorithm> using namespace std; static const int N = 1000; static </algorithm></string></iostream>…

11.2 フィボナッチ数列

動的計画法の基本とのことです。特に難しいところはなし。 #include <iostream> #include <vector> using namespace std; static vector<int> M(44, 0); static inline int fibonacci(int n) { if (n == 0 || n == 1) { return 1; } if (M[n] != 0) { return M[n]; } M[n] = fibonac</int></vector></iostream>…

10.4 優先度付きキュー(写経編)

insert/extract ともに難しいので写経。完全二分木を使いこなすには程遠い理解度、ということがわかりました。 #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; const static int INFTY = (1<<30); static vector<int> A(2000000 + 1); static int</int></cstdio></algorithm></vector></iostream>…

10.3 最大・最小ヒープ

buildMaxHeap() と maxHeapify() が問題文に書いてあり、そのままの実装となります。 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; static inline int left(int i) { return 2 * i; } static inline int right(int i) { return 2 * i + 1;</algorithm></vector></cstdio></iostream>…

10.2 完全二分木

ヒープ編に突入。今回は問題文通りの実装です。parent, left, right が単純な計算で決定するのが面白いですね。なお、解説の実装では、木の実装が int の配列になっており、自分の実装は無駄な箇所が多々あります。 #include <iostream> #include <cstdio> #include <vector> using nam</vector></cstdio></iostream>…

9.4 二分探索木(写経編)

これはアカンかったです。次節点の探索のところ、ややこしすぎませんか? あっそういえばポインタの参照を久しぶりに使いました。(rootの入れ替えのところ) #include <iostream> #include <cstdio> #include <memory> using namespace std; struct Node { int key; Node* parent; Nod</memory></cstdio></iostream>…

9.3 二分探索木:探索

お仕事でいろいろとやられているので間が空いてしまいました。 今回のお題は前回の内容を引き継いでいるので、あとは探索機能を入れるだけでした。 ※20180417追記:巡回出力のところがバグっていたので直しました #include <iostream> #include <cstdio> #include <memory> using names</memory></cstdio></iostream>…

9.2 二分探索木:挿入

問題に書いてあった解説どおりの実装です。delete を呼んでないのが気持ち悪いですが、まあ良いでしょう。良くないか。 #include <iostream> #include <cstdio> #include <memory> using namespace std; struct Node { int key; Node* parent; Node* left; Node* right; Node(int key =</memory></cstdio></iostream>…

8.5 木巡回の応用:木の復元

ちょっと間が空いてしまいました。自力で考えたとっkは、すべての木を復元しようとしたのですが、NGでした。ということでこちらは写経となっております。シンプルな再帰とアルゴリズムを思いつくにはどうしたら良いんでしょうねえ。。 #include <iostream> #include <vector> #</vector></iostream>…

8.4 木の巡回(手動編)

詳細は端折りますが、いろいろと難しく考えすぎて失敗しました。こんなシンプルな方法で巡回になるんですね。。 #include <iostream> #include <vector> using namespace std; struct Node { int id; int parent; int left; int right; Node() : id(), parent(-1), left(-1), r</vector></iostream>…

8.3 二分木の表現(手動編)

高さの算出が前回と違うところですね。構造体にメソッドがつけられることを忘れていたので若干処理を移動しました。あまりキレイではないですがこれくらいで。。 #include <iostream> #include <vector> #include <string> #include <cstdio> #include <algorithm> using namespace std; static const stri</algorithm></cstdio></string></vector></iostream>…

8.2 根付き木の表現(手動編)

解説を見ないで書いた版です。構造体 Node の子の表現を vector にしました。しかし解説では「左右の子のみでも解ける方法」となっており、vector は仰々しかったかなと。。深さの算出は再帰です。子の数が0になるまで回します。 節の入力時の番号が、0か…

7.7 最小コストソート

最小値を使って交換し、その上で計算式の算出と反例まで考えないと解けない難問。とても難しいので今回は写経です。本書内の回答例は変数名がかなり分かりづらいので、ちょっと直してはいます。また、ソート済のテーブルの先頭の値が最小値なので、そのまま…

7.6 反転数

7.5は STL のソートの話だったので、基本的にはスルーですが、std::stable_sort が使えることを知りました。 #include <iostream> #include <vector> #include <algorithm> #include <cstdint> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) </cstdint></algorithm></vector></iostream>…

7.4 計数ソート

配列 A,B を 1 オリジンにしないといけない理由を理解しないままコーディングし、その途中でインデックスがずれまくったために答えが合わず、無駄な時間を費やしてしまいました。また、A, B の配列のサイズを間違えていたため、Runtime Error を頻発させてし…

7.3 クィックソート

悩んだのは stable の判定ってどうするの?という部分です。過去の安定ソートと比較する、というのは思いつきませんでした。余計な時間がかかりそうですし。 #include <iostream> #include <vector> #include <algorithm> #include <cstdint> using namespace std; struct Card { char suit; int va</cstdint></algorithm></vector></iostream>…

7.2 パーティション

「パーティション処理を行うと何が嬉しいのか?」が書かれてないため、あまり達成感がないですが、とりあえず。 #include <iostream> #include <vector> #include <algorithm> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) { cin >> A</algorithm></vector></iostream>…

7.1 マージソート

解説どおりの実装です。「Runtime Error」が頻発して悩みましたが、配列LRをスタックメモリに確保していたのが原因でした。再帰だからあっという間にスタックを食い尽くすんですね。 #include <iostream> #include <vector> #include <cstdint> using namespace std; static void inputA</cstdint></vector></iostream>…

6.3 コッホ曲線

なかなか再帰脳になれず。。なお座標計算は本書を参照しました。プログラミングコンテストって、ここまで数学の知識を問われるんですかね? #include <iostream> #include <vector> #include <cmath> using namespace std; struct P { double x; double y; P(double x, double y) : x(</cmath></vector></iostream>…

6.2 全検索

再帰と計算結果をうまく組み合わる、この発想がなかなか出てきません。 #include <iostream> #include <vector> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) { cin >> A[i]; } } static inline bool solve(int A[], int i</vector></iostream>…

5.6 探索の応用(バイナリサーチ版)

ということで、バイナリサーチを使う版です。積載量の絞り込みをバイナリサーチで行っていくのですね。数が大きくなると劇的な効果が出ますね。検索回数は log2(1000000000) = 約 30 回でした。 #include <iostream> #include <vector> //#include <cstdio> using namespace std; stati</cstdio></vector></iostream>…

5.6 探索の応用(時間切れ版)

解説そのままやってみて、時間切れのパターン。ここまでは様式美です。ここからバイナリサーチをどう使うのだろう? 現時点でひとつだけ工夫したところは、入力時の最大値を覚えておいて、そこから P を増やしていく部分です。最大値が入らない積載量の探索…

5.4 ハッシュ(解説版)

解説(というか答え)の写経版です。ハッシュ関数は、自力では思いつかないので、研究している人たちにおまかせするしかない感じです。 #include <iostream> #include <string> #include <vector> using namespace std; static inline int charToInt(char c) { switch(c) { case 'A': r</vector></string></iostream>…

5.4 ハッシュ(自力版)

「ハッシュ」という言葉と、問題の図を参考に、自分なりに考えたのがこちら。「文字の種類は4つ」ということで、文字列を4進数とみなして、全部の組み合わせ分の bool 配列を持ち、insert 時に組み合わせを int 値にして、配列の index に読み替えてそこを…

5.4 ハッシュ(時間切れ版)

まずは「ハッシュ」という言葉をスルーしてそのまま書いた場合。これは時間切れになります。 #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<string> dictionary; dictionary.reserve(1000000); string comman</string></algorithm></string></vector></iostream>…

5.3 二分探索

いわゆるバイナリサーチですね。知識で知っているのと自分で書くのとは大違いで大変です。 #include <iostream> #include <array> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < num; i++) { cin >> A[i]; } } static int binarySear</array></iostream>…