異端開発室

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

問題概要 n 個の要素があり、それぞれに整数値の属性 a と b が割り当てられています。いくつかの要素を選択して、選ばれた要素の a 属性の合計 と b 属性の合計 の総和を最大化したいと考えます。ただし、以下の条件を満たす必要があります： a 属性の合計 ≥ 0 b 属性の合計 ≥ 0 この条件下で、(aの合計) + (bの合計) を最大にするプログラムを作成します。 アプロ ...

コンテスト参加後の復習と解法の整理を行います。問題AからDまでのアプローチとコードをまとめました。 A. Fibonacciness 5要素の数列における最大の「フィボナッチ度」を求める問題です。数列の長さが5であるため、最大でも度は3となります。各位置で成立するフィボナッチ関係の式を検討します。 具体的には、a0+a1 = a2、a1+a2 = a3、a2+a3 = a4の3つの条件が考えら ...

可能な限り簡潔にします。 CF679E 直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。 既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。 したがって、加算操作は次のように記述 ...

A. カエルのジャンプ 問題の条件に従って直接シミュレーションを行います。データ範囲に注意し、long long型を使用します。 void solve(){ long long a, b, k; cin >> a >> b >> k; cout n; vector<int> arr(n); for(int i = 0; i < n; i++) cin >> arr[i]; int result = 0; for(int i = 0; i < n - 2; i++){ if(arr[i] = ...

円周率日チャレンジ 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++における演算子の優 ...

配列操作と最適化アルゴリズムの応用 A. 順序逆転検出 要素順を変更して、新しい配列を作成し、その配列が元の配列と異なる順序になるようにする問題です。 #include <vector> #include <iostream> using namespace std; void findDisorder(vector<int>& arr) { for (int i = 0; i < arr.size() - 1; ++i) { if (arr[i] > arr[i + 1]) ...

部分文字列と部分配列 目的は、文字列 a と b を部分配列として含む最短の文字列を見つけることです。その長さは a と b の長さの合計から、両方で共通する文字数を引いたものです。a は必ず含まれるため、b の各文字が a で順番に現れるかをチェックします。 注意: 部分文字列は連続した文字列ですが、部分配列は順序を保ちつつ連続性は必要ありません。 #include <bit ...