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 投稿
AtCoder Beginner Contest 389 解法解説
A - 9x9
問題概要
1桁の数字同士の乗算結果を求める。
解法
入力文字列から数値を抽出して掛け算する実装を行えばよい。
実装コード
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve() {
string input;
cin >> input;
int a = input[0] - '0';
...
5月28日 14:34 投稿
差分配列と累積和のアルゴリズム
差分配列と累積和
テンプレート（疑似コード）
// 元データの読み込み: n, m, a
n, m = 入力()
for i = 0 to n-1:
a[i] = 入力() // 元の配列
// 差分配列の構築
for i = 0 to n-1:
diff[i] = a[i] - a[i-1]
// 区間操作
while m > 0:
m = m - 1
l, r, value = 入力()
diff[l] = diff[l] + value
diff[r+1] = diff[r+1] - value
// 累積和で ...
5月18日 12:33 投稿
2次元差分配列を用いたカーペット問題の解法
問題の説明
n x n のグリッド上に m 枚のカーペットが置かれています。これらのカーペットの情報が与えられたとき、各マスが何枚のカーペットで覆われているかを求めてください。
入力形式
第一行に、2つの正の整数 n, m が与えられます。
続く m 行に、それぞれ 2 つの座標 (x1, y1) と (x2, y2) が与えられます。これは、左上のマスが (x1, y1)、右下のマスが ( ...
5月14日 09:46 投稿