接頭和と差分配列の応用
接頭和 & 差分配列
計算量最適化のための基本技術
接頭和は複数回の区間クエリを高速化する手法。配列arr[N]に対してpre_sum[N]を構築し、
pre_sum[i] = pre_sum[i-1] + arr[i]と定義する。インデックスは1から始める必要がある。
実践問題
N都市を結ぶ道路があり、各セグメントの移動コストが与えられる。伝送装置を使って最大kセグメント飛躍可能。ただし1回の ...
7月24日 18:21 投稿
牛客周赛 Round 69 問題解説
Cの構築問題
解法
AとBの絶対差と最大値の和を取ることで、第三項を構築できます。
コード
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b;
cin >> a >> b;
int d = abs(a - b);
cout << max(a, b) + d << &q ...
7月20日 03:34 投稿
二次元配列における最大部分行列和の計算
解法の概要
本課題は行列内の全ての部分行列の和の中で最大値を求めることを要求します。全ての部分行列を総当たりで列挙し和を計算する方法では、計算量がO(n^4)となり、nが大きい場合に効率が悪くなります。ここでは二次元累積和の技法を用いて計算プロセスを最適化します。
二次元累積和の基本概念
二次元累積和は前処理技術の一つで、任意の部分行列の和をO(1)時間 ...
7月17日 02:58 投稿
Codeforces Edu Contest 161 解法と分析
問題A: 文字列照合判定
この問題では、文字列cの各文字が対応する位置の文字列aまたは文字列bのいずれかと一致するかを判定する必要があります。すべての文字が一致する場合は"NO"、そうでない場合は"YES"を出力します。
#include
#include
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases ...
7月7日 20:03 投稿
ABC367 回顾：典型アルゴリズム問題の解法と実装
A問題: 時間帯の重なり判定
この問題は、ある時間が指定された時間範囲に含まれるかを判定するものである。注意点として、時間帯が翌日にまたがるケースがある。これを処理するために、終了時刻が開始時刻より小さい場合は終了時刻に24を加算し、範囲を正しく表現する。
次に、基準となる時刻（国王が叫ぶ時刻）がその範囲内にあるか、または24時間を加えたバージョンが範 ...
7月3日 23:27 投稿
LeetCode 560. 和がKの連続部分配列の個数を数える方法
LeetCode 560. 和がKの連続部分配列
この記事では、整数配列から和がKである連続部分配列の個数を数える方法を説明します。
1. 問題の理解
与えられた整数配列`nums`と整数`k`から、和が`k`である連続部分配列の個数を返す必要があります。
例
入力: nums = [1, 1, 1], k = 2
出力: 2
説明: [1,1]が2回出現（インデックス0~1と1~2）
2. 暴力的な解法
2.1 最も単純 ...
7月1日 16:49 投稿
牛客冬季アルゴリズム基礎訓練キャンプ2 解答解説
問題 A
解法の考え方
入力値7個が全て{1,2,3,5,6}のいずれかであるかを検証する。無効な値が1つでもあれば即時判定する。
コード例
#include <iostream>
using namespace std;
bool isValid(int val) {
return val == 1 || val == 2 || val == 3 || val == 5 || val == 6;
}
int main() {
int tmp;
for (int i = 0; i < 7; i++) {
cin > ...
6月30日 18:41 投稿
AtCoderコンテスト328の問題解説
A: 閾値以下の合計
数値リストから指定された閾値以下の要素の合計を算出します。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int num, threshold;
cin >> num >> threshold;
vector<int> values(num);
int total = 0;
for (int &val : values) {
cin >> val;
if (val days[i];
int base = i ...
6月25日 22:30 投稿
部分配列の絶対値和の最大値 (DP)
与えられた配列から、部分配列の和の絶対値の最大値を求めます。部分配列は空でも構いません。
方法1
最大部分配列の和と最小部分配列の和を別々に動的計画法で計算します。その後、これらの値の絶対値の最大値を求めます。
考え方
max_sum_ending_at[i]: nums[i]で終わる部分配列の中で最大の和
min_sum_ending_at[i]: nums[i]で終わる部分配列の中で最小の和
コード
co ...
6月7日 18:55 投稿
連続部分列の最大和を求めるときの主要3つのアルゴリズム
整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。
手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）
あるインデックス i で終了する連続部分配列の最大 ...
6月3日 22:26 投稿