異端開発室

本日は配列を用いたスタックのC++実装について学習しました。これはポインタ方式と多くの点で異なります。 ポインタ方式では、スタックの初期化時にヘッドノードを確保し、プッシュ操作では新しいノードを割り当て、ポップ操作ではノードを解放します。これらのノードはすべて最初の位置に配置され、トップ要素を取得する際にはS->next->dataを参照します。 一方で配 ...

連結リストとは 連結リストは、配列とは異なり連続したメモリ領域を必要としないデータ構造です。各ノードが次のノードへの参照（ポインタ）を持つことで、離散的なメモリブロックを連結します。 この特性により、要素の検索は先頭から順次走査する必要がありますが、挿入や削除は参照の付け替えだけで完結します。その結果、配列と比較して検索のコストが高く、挿入・削 ...

C++イテレーターの仕組みと使い方 イテレーターが最も便利なのはアルゴリズムライブラリとの連携です。この仕組みを活用することで、アルゴリズムの実装に焦点を当てることができ、データ構造の詳細を気にする必要がありません。 イテレーターの基本的な使い方 例えば、std::copy_nは範囲内の要素をコピーするためのアルゴリズムです。この関数はさまざまなコンテナに ...

関連タグ 動的計画法、C言語 問題の説明 三段階の階段を登る問題です。ある子供が階段を登っているとします。階段はn段あり、その子供は一度に1段、2段、または3段を登ることができます。このとき、子供が階段を登る方法の総数を計算するアルゴリズムを実装してください。結果は非常に大きくなる可能性があるため、1000000007で剰余を取ってください。 解法の考察 これは基 ...

街路灯の消灯問題 問題の概要 ある村では、一本の道に \(n\) 基の街路灯が設置されています。各街路灯には異なる消費電力があります（つまり、同じ時間あたりに消費する電力量が異なります）。張さんはこの道の途中にある街路灯のそばに住んでおり、毎朝夜明けになると一つずつこれらの街路灯を消す仕事をしています。 村の電気代を節約するため、張さんは各街路灯の位置と ...

問題概要と考察 本稿では3つのアルゴリズム問題を解くための手法について説明します。各問題で異なる技術が要求されています。 第1問：骨牌配置の最適化 n枚の骨牌を並べるとき、ある位置から倒すことで連続して倒れる骨牌の数を最小化する問題です。 考え方 最終的な回答は、末尾のいくつかの骨牌を削除した後の状態から計算できます。任意の位置まで考えた時の最適値を ...

問題概要 整数配列 numbers が与えられたとき、異なる3つの要素 numbers[i] + numbers[j] + numbers[k] == 0 を満たすすべての一意な三元組 (i, j, k) を見つけて返します。ただし、i, j, k はすべて異なるインデックスを指す必要があります。 制約条件 配列の長さ: 3 ≤ numbers.length ≤ 3000 要素の範囲: -10⁵ ≤ numbers[i] ≤ 10⁵ 実行例 入力: numbers = [-1, 0, 1, ...

回文判定プログラム #include <iostream> #include <string> #include <algorithm> bool is_palindrome(const std::string& str) { auto front = str.begin(); auto back = str.rbegin(); size_t mid = str.length() / 2; for(size_t i = 0; i < mid; ++i) { if(*front != *back) return false; ++fr ...

セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。 木上のパスを線形構造に変換するアイデア 木は分岐構造を持つため ...

問題の説明： 総計 n 個のチームが存在し、0 から n - 1 までの番号が割り当てられています。 0から始まる n × n の二次元ブール行列 grid が与えられます。0 <= i, j <= n - 1 かつ i != j となるすべての i, j について、もし grid[i][j] == 1 であれば、チーム i はチーム j よりも強いとします。そうでなければ、チーム j はチーム i よりも強いとします。 この ...