FINAL FANTASY XIV 漆黒の反逆者

もう先週のことですが、FF14パッチ5.0の部分がようやく終わりましたので、一旦感想を書いておきます。本記事の内容は、漆黒の反逆者(パッチ5.0) までのネタバレを大いに含みます。十分にご注意ください。 改行 改行 改行 改行 改行 改行 改行 改行 改行 改…

自分的年代別最高のゲームを挙げる

あくまでも「自分にとって最高のゲーム」という観点です。 1980 年代 自分の趣味嗜好を決定づけた時期。 ゼビウス(AC,FC) 自分にとって「ゲームにハマる」「STG を好む」きっかけとなった、重要な作品。映像の美麗さ、(当時としては)奥深いストーリー性を…

II魂2019 RECITAL

2018 2016(リサイクル2) 2015 2014 2013 2012 2011 2010 2009 諸事情により、今回から Markdown で記述します(書き手の都合であり読み手の方には一切影響ありません)。それにしても、ココログはもっと真面目に Markdown をサポートしやがれ!と言いたい。 *…

ゲーム音楽の沼

これは 沼 Advent Calendar 2018 の 16 日目の記事です。 こんにちは!!最近、ゲーム音楽が流行ってますね!!!ね!!!??? 私はファミコン世代ど真ん中で、いわゆるピコピコ音からのゲーム音楽を、その変遷とともに今日まで聴き続けてきました。自分と…

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 を増やしていく部分です。最大値が入らない積載量の探索…