異端開発室

循環キューとは 循環キューは線形データ構造の一種で、FIFO（先入れ先出し）原則に基づく操作を提供します。通常のキューと異なり、末尾要素が先頭要素に接続されて環状構造を形成するため、リングバッファとも呼ばれます。 循環キューの利点 従来のキューでは領域が満杯になると追加操作が不可能でしたが、循環キューでは先頭側の未使用領域を再利用できるため、メモリ効 ...

牛客週間コンテスト 第5回 A-游游の文字変換 #include <iostream> #include <string> using namespace std; int main() { string input; cin >> input; for (size_t i = 0; i < input.length(); ++i) { char current = input[i]; if (current >= 'A' && current < 'Z') { input[i] = cu ...

問題定義 n個の正の整数からなる配列と正の整数sが与えられたとき、要素の合計がs以上となる連続する部分配列のうち最小の長さを求める。条件を満たす部分配列が存在しない場合は0を返す。 例: 入力: s = 7, nums = [2,3,1,2,4,3] 出力: 2 説明: 部分配列[4,3]が条件を満たす最小長の連続部分配列 解法アプローチ 総当たり法 最も単純な方法は二重ループを用いた総当 ...

基本的な比較計算 二つの整数の積を比較する問題では、直接的な計算を用いる。 #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が奇数の場合のみ理想生成器となる。偶数の場合、配列 ...