異端開発室

動的プログラミング問題へのアプローチ 動的プログラミング問題を解決するための5つのステップ： DP配列（DPテーブル）とそのインデックスの意味を定義する 漸化式を決定する DP配列の初期化方法を決定する（配列オーバーフローに注意） 計算順序を決定する DP配列の具体例を導出する フィボナッチ数 フィボナッチ数列（通常 F(n) で表される）は、0 と 1 から始まり、そ ...

Pythonにおける木構造の実装と応用 木構造の基本概念 木構造は階層的な関係を模倣するデータ構造で、各要素はノードと呼ばれます。木の各ノードはゼロ個以上の子ノードを持つことができますが、各ノードは親ノードを一つしか持たない、という特徴があります。ルートノードだけは親ノードを持たない例外です。木構造の重要な特性は、循環がないことです。つまり、あるノー ...

文字列の反転 問題1：文字配列の反転 文字配列として与えられた入力文字列を反転する関数を実装してください。追加の配列を割り当てず、入力配列をその場で変更し、O(1)の追加スペースのみを使用してこの問題を解決する必要があります。 例1： 入力：s = ["h","e","l","l","o"] 出力：["o","l","l","e","h"] 例2： 入力：s = ["H","a","n","n","a","h"] 出力：["h","a","n ...

1. はじめに 再帰は、関数型言語のみならず、あらゆるプログラミングパラダイムにおいて極めて重要な概念である。本稿では、数学的帰納法との関連性を踏まえながら、再帰関数の設計手法について体系的解説していく。 2. 再帰と数学的帰納法 2.1 数学的帰納法の原理 数学的帰納法は、自然数に関する命題を証明するための手法である。その原理は以下の2つのステップから ...

クイックソートの基本概念 クイックソートは、分割統治法に基づく効率的なソートアルゴリズムです。これはバブルソートの改良版とも言え、バブルソートのO(n²)の計算量を改善します。クイックソートでは、ある基準値（ピボット）を選び、配列をそれより大きいグループと小さいグループに分割して再帰的に処理します。 問題設定 整数配列を受け取り、クイックソートを使っ ...

データ構造 単方向連結リストの操作 // 初期化 void initialize() { top = -1; // リストの先頭を-1に設定 counter = 0; // 使用中のインデックスカウンター } // 先頭に要素を挿入 void insert_at_top(int value) { elements[counter] = value; // 値をカレントノードに格納 next_pointers[counter] = top; // カレントノードの次を現在の先頭に ...

1. 要素を変更しないシーケンス操作 これらの関数は元データを改変せず、検索・集計・条件評価などの処理を行います。 1.1 検索系：find, find_if, find_end std::vector<int> data = {10, 20, 30, 40, 50}; // 値30を検索 auto pos = std::find(data.cbegin(), data.cend(), 30); if (pos != data.cend()) { std::cout << "見つかった値: " << *p ...

円周率日チャレンジ Pythonの高精度計算を活用する問題。浮動小数点数の精度問題を回避するため、整数演算で処理する。 n = int(input()) pi_value = 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 results = [] for _ in range(n): numerator, denominator = map(int, input().split()) approx = nume ...

問題リンク 問題A. 木を掘って火を起こす S * V >= n さえ満たせばよい #include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N = 2010,mod = 1e9 + 7; int n,s,v; void solve() { cin >> n >> s >> v; if(s * v >= n) cout << 1 << endl; else cout &lt ...

ビット演算の基本と応用 ビット演算とシフト演算は、コンピュータの基本的な操作であり、バイナリレベルでのデータ操作を可能にします。アルゴリズム競技において、これらの操作は特定のタスクを効率的に実行するための強力なツールとなります。その特性と応用例を理解することは、競技プログラミングにおいて非常に重要です。 1. 演算子の優先順位 C++における演算子の優 ...