110. 微分積分学の基本定理の離散類似
微分積分学における基本定理とは、関数の微分と積分の関係を表すものです。この基本定理には、第一基本定理と第二基本定理があります。
離散的な場合でも、基本定理に類似した公式が存在します。具体的には、離散的な場合の微分と積分に相当するものとして、差分と和があります。
差分とは、離散的な場合における微分のようなものであり、f(x+1)-f(x)のように、隣り合う要素の差をとることで定義されます。
和とは、離散的な場合における積分のようなものであり、Σ f(x) のように、区間 [a,b] での関数値の総和を表します。
この差分と和に関する基本的な性質として、以下のような離散的な基本定理があります。
・差分の和は、元の関数の値の差に等しい。
Δ Σ f(x) = f(b) - f(a)
・和の差分は、元の関数の値に等しい。
Σ Δ f(x) = f(b) - f(a)
これらの式は、微分積分学の基本定理と同様に、関数の微分と積分の関係を表しています。ただし、離散的な場合には微分と積分の概念が存在しないため、差分と和がそれぞれ代わりになっています。
【問題概要】
関数f(x)の離散積分g(x)を以下のように定義する。
g(0) = 0
g(n+1) = g(n) + f(n)
このとき、f(x)の差分列a(x)を以下のように定義する。
a(0) = f(0)
a(n) = f(n) - f(n-1) (n≧1)
このとき、g(n)を用いてa(n)を表す関数b(n)を求めよ。
また、a(n)が与えられたとき、f(n)を求め、g(n)を求めよ。
【解説】
まず、a(n)とg(n)の関係を考えると、a(n) = g(n) - g(n-1)が成り立つ。
したがって、b(n)を求めるには、a(n) = g(n) - g(n-1)を解いてg(n)を求め、g(n)からb(n)を求めることができる。
また、a(n)が与えられたとき、f(n)を求めるには、f(n) = a(0) + a(1) + ... + a(n)が成り立つので、この式を用いてf(n)を求めることができる。
【関連するAtcoderの問題例】
「Integral Points」
レーティング難易度(★): 1200
ACした回答者に絞った場合のレーティング帯の範囲(数値): 967-1702
レーティング難易度(%): 48.4%
レーティング(数値): 1294
AC率(%): 30.2%
ACしたスコアの高い回答者: https://atcoder.jp/users/deltix
解説ブログ: https://atcoder.jp/contests/arc059/editorial/1232
「区間加算」「https://atcoder.jp/contests/abc165/tasks/abc165_d」: レーティング難易度(★★)：1100~1400：レーティング難易度(88.3%)：1293：AC率(40.7%)：20,000点以上：https://atcoder.jp/users/ksn_ma：https://ksnma.hatenablog.com/entry/2020/05/24/152851
この問題は、与えられた区間[l,r]に対して、配列aの[l,r]に加算するクエリがq個与えられるとき、配列aの各要素の値を求める問題である。この問題は、区間[l,r]の幅を求めている本問題のように、離散的な範囲に対して処理を行う問題であるため、関連性があると考えられる。
Discussion