異端開発室

基本的な比較計算 二つの整数の積を比較する問題では、直接的な計算を用いる。 #include <iostream> int main() { long long w, x, y, z; std::cin >> w >> x >> y >> z; std::cout numA >> numB; std::cout 1) isCritical[node] = true; } int main() { int cols; cin >> cols; string rowA, rowB; cin >> rowA >> rowB; i ...

はじめに 本記事では、2023年中国大学コンピュータ大会-チームプログラミング天梯大会（GPLT）上海理工大学校内選手大会のA-D問題の解法を紹介します。大会では4問中2問を解き、その後残り2問を追加で解決しました。他の問題についても、一部は他の参加者のソースコードを参考に理解しました。 以下に解いた4つの問題の解法を記載します。 A問題: Xor B問題 問題文は長いで ...

線形リストは、同じ特性を持つデータ要素の有限シーケンスです。実際の応用で広く使用されるデータ構造であり、順序リスト、リンクリスト、スタック、キューなどが含まれます。 ここでは、連続リスト（順序リスト）をC言語で実装し、初期化、追加、削除、検索、更新といった基本操作を行います。 1. 連続リストの初期化 以下のように、連続リストの構造体と関数を定義 ...

問題の分析 この問題は、セグメント木のマージ操作を用いて木構造上の動的計画法を最適化する手法が鍵となります。 まず、値の範囲が最大で10^9まで及ぶため、離散化（座標圧縮）が必要です。各値の出現確率を管理する必要があるため、基本的な木DPを考えます。 動的計画法の設計 dp[v][j] を頂点vにおいて、j番目に小さい値が出現する確率と定義します。遷移は以下の3 ...

二分探索 × 復習時の重要ポイント midの計算時にint mid = left + (right - left) / 2;を使用して、int mid = (left + right) / 2;による整数オーバーフローを防ぐ必要がある 通常の検索、左境界、右境界はすべて左閉じ右閉じ区間を使用可能。閉区間のright = arr.length-1と開区間のright = arr.lengthの違い、およびwhileループでの<=と<の使い分けに注意 3種 ...

基本的な操作 1. 単一要素の追加 data_list = [10, 20, 30] data_list.append(40) print(data_list) # 出力: [10, 20, 30, 40] 2. 反復処理によるリスト構築 result = [] for j in range(1, 6): result.append(j) print(result) # 出力: [1, 2, 3, 4, 5] 3. ユーザ入力の動的収集 inputs = [] user_value = '' while user_value != 'exit': user_value = input ...

理想的な生成器の判定 正整数kが「理想生成器」であるとは、任意の整数n（n ≥ k）が、長さkの回文配列の要素和として表現可能な場合を指す。回文配列とは、配列aがa1からakまでとakからa1までが同一となる配列である。例として、k=1は理想生成器である（nは[n]で表現可能）が、k=2は非理想（3を表現不可能）。 解法: kが奇数の場合のみ理想生成器となる。偶数の場合、配列 ...

多分木データ構造は様々な応用分野で利用されますが、実装方法は使用目的によって大きく異なります。本実装は組み込みシステム向けに設計されたシンプルな多分木で、スレッド管理などの用途を想定しています。 データ構造定義 #define MAX_CHILDREN 32 #define NODE_NAME_LENGTH 32 typedef struct tree_node { long identifier; struct tree_node* parent_ptr; ...

概要 Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。 構造と原理 BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & - ...

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