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

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

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

７．５は 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>…

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

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

「パーティション処理を行うと何が嬉しいのか？」が書かれてないため、あまり達成感がないですが、とりあえず。 #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>…

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

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

再帰と計算結果をうまく組み合わる、この発想がなかなか出てきません。 #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>…

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

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

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

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

まずは「ハッシュ」という言葉をスルーしてそのまま書いた場合。これは時間切れになります。 #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>…

いわゆるバイナリサーチですね。知識で知っているのと自分で書くのとは大違いで大変です。 #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>…

番兵の説明があったのでそのまま入れてみます。 #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 linearSearch(int A[], int sentinel) { int i = 0; f</array></iostream>…

まずはそのまま書いてみます。内側ループを抜ける条件が微妙ですが、関数化するのを忘れていたためです。もっと丁寧にやらないといけませんね。 #include <iostream> #include <array> using namespace std; static void inputArray(int A[], int num) { for (int i = 0; i < </array></iostream>…

これは面積のマージ部分のロジックが全然思いつかなくてダメでした。。解説を読みつつ書いたものがコレ。 #include <iostream> #include <string> #include <vector> #include <stack> using namespace std; static const char DOWN = '\\'; static const char EVEN = '_'; static const char </stack></vector></string></iostream>…

では、連結リストを手動で・・・と思いましたが、昔自分で作ったことがあるので割愛します。なお、一つ前の記事で「stdin 周りで苦労した」というのは、cin と fgets と scanf を混ぜて使ったら、改行コードの処理が想定しない動きをしてくれたので、仕方な…

これは苦労しました。。主に stdin 周りで無駄に苦労しました。。かなり汚いコードですが清書は後日。 #include <iostream> #include <string> #include <list> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; enum COMMAND_TYPE { INSERT, DELETE, DELETE_FIRST, DE</cstring></cstdlib></cstdio></algorithm></list></string></iostream>…

queue も書いてみます。初めはランタイムエラーが出て「？」となりましたが、head とtail の初期化をサボってたからでした。AIZU のコンパイラはきっちりと不定値を入れてくるのですね。なお初期化については下記の記事が参考になります。 プログラミングの…