異端開発室

D - パンライン問題 この問題は数学的に抽象化することで簡単に解くことができます。 #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll t; cin >> t; while (t--) { ll n, sum = 0; cin >> n; vector<ll> arr(n); for (auto &x : arr) { cin >> x; sum += x; ...

FWT高速ウォルシュ変換学習ノート 初見では理解困難ですが、そのコードの簡潔さには感銘を受けます。覚えるしかないかもしれません。 基本的な変換式 [FWT(A) = (FWT(A_0), FWT(A_1 + A_0)) ][IFWT(A) = (IFWT(A_0), IFWT(A_1 - A_0)) ]と [FWT(A) = (FWT(A_0 + A_1), FWT(A_1)) ][IFWT(A) = (IFWT(A_0 - A_1), IFWT(A_1)) ]論理和 [FWT(A) = (FWT(A_0 + A_1), FWT(A_0 - ...

回文部分文字列のカウント この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s ...

マージソートは分割統治法に基づく効率的なソートアルゴリズムです。この記事では、C言語での実装方法とパフォーマンス向上のためのテクニックを解説します。 マージソートの基本概念 マージソートは配列を2つの部分に分割し、それぞれをソートした後、結果をマージするアルゴリズムです。以下の特徴があります： 時間計算量：O(n log n) 空間計算量：O(n) 安定ソート ...

C言語における配列のメモリレイアウトの理解から、ソートアルゴリズム、進数変換、行列演算といった実用的なアルゴリズムの実装まで、いくつかの例を通して解説します。 1. 配列のメモリレイアウトとアドレス 配列はメモリ上で連続した領域を占有します。以下の例では、1次元配列および2次元配列のアドレスと要素の配置を確認できます。 #include <stdio.h> void i ...

二分探索木とは 二分探索木（Binary Search Tree: BST）は、以下の条件を満たす二分木構造です： 左部分木に含まれるノードの値は、常に親ノードの値より小さい 右部分木に含まれるノードの値は、常に親ノードの値より大きい 左右の部分木もまた二分探索木を満たす 基本操作 探索（Search） 探索操作は以下のように行われます： ルートノードから比較を開始します 探索 ...

1 #include<stdio.h> char evaluate_grade(int point); int main() { int input; char result; while (scanf("%d", &input) != EOF) { result = evaluate_grade(input); printf("点数：%d ", input); printf("評価：%c\n", result); } return 0; } char evaluate_grade(int point) ...

ガウスの日記 出典：第4回藍橋杯省選C++A/Bグループ アルゴリズムタグ：シミュレーション 問題説明： 大数学者ガウスには日記をつけるという良い習慣がありました。彼の日記は特別な点があり、年月日を書く代わりに整数を使用していました。例えば、4210という数字です。 後になって、その整数が日付を表していることが分かりました。それは、その日がガウスの誕生日から何 ...

A. 重複要素の削除 与えられた数列から重複要素を削除し、最初に出現した要素のみを保持するアルゴリズム。 #include <iostream> #include <vector> #include <unordered_map> using namespace std; vector<int> removeDuplicates(const vector<int>& nums) { unordered_map<int, int> countMap; vector<int> result ...

連結リストの基本概念とノード定義配列などのシーケンシャルなデータ構造では、要素の挿入や削除に伴うデータの移動コストが高くなる。この問題を解決するため、各要素をポインタで連結する連鎖構造（単方向連結リスト）が用いられる。単方向連結リストには以下の特徴がある。論理的に隣接する要素が物理的なメモリ上でも隣接している必要がない。ランダムアクセスが不可能 ...