異端開発室

桁DPとは何か？ 桁DP（Digit Dynamic Programming）は、通常ある区間[L, R]内で特定の制約を満たす数字の数を統計するために使用されます。LとRのデータ範囲が大きいため、DP（動的計画法）で統計する必要があることが多いです。 上限Rの処理テクニック 数値の比較ルールから、現在の桁の取りうる値の範囲は、前方の桁の値に依存することがわかります。 もし前方のすべて ...

きこりのミルコは、ある特殊な伐採機を用いて、要求される長さの木材を収集します。この伐採機は、設定された高さ H を基準に動作します。具体的には、伐採機は巨大な鋸刃を高さ H まで持ち上げ、その高さよりも高い部分を持つ全ての木から、H を超える部分を切り落とします。切り落とされた部分がミルコによって収集されます。H 以下の高さの木はそのまま残り、切り落とさ ...

動的プログラミング問題へのアプローチ 動的プログラミング問題を解決するための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 ...