Kickstart 2020 RoundC: Perfect Subarray
問題
N個のinteger(negative valueの場合もあり)を含む配列が与えられたとき、perfect subarrayが幾つあるかを求める問題。
連続するsubarrayの合計値がperfect squareである時、perfect subarrayであると定義。perfect squareは、non negativeなintegerのそれ自身との積である数のことを言う。例えば、0, 1, 4, 9, 16など。
アルゴリズム
全てのsubarrayを求めて、各subarrayがperfectであることを確認すれば、答えを求めることはできます。subarrayは開始位置と終了位置で決まるので、開始位置が0,1,2,...,N-1のときに、終了位置はN-1個,N-2個,...,1個となり、それぞれのsubarrayについてsumを計算すると、全体で
与えられたarrayをAとして、Aの中の位置iについて累積和
従って、Aの各位置iについて累積和を求めながら、上記の計算を行い、求めた値と等しい累積和となる位置kの個数をカウントに加えていく。累積和を求めていく時には、累積和をキー、同じ累積和を持つ位置kの数を値としてもつハッシュテーブルを作成して参照するようにし、またperfect squareを用いた上記の計算は、累積和の最小値より小さくなったら計算を打ち切って、次の位置へ移動する。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
ll T, N;
cin >> T;
for (ll t = 1; t <= T; ++t)
{
cin >> N;
vector<ll> arr;
for (ll i = 0; i < N; ++i)
{
int d;
cin >> d;
arr.push_back(d);
}
ll res = 0;
ll sum = 0;
ll min_sum = 0;
unordered_map<ll, ll> m;
m[0] = 1;
for (ll i = 0; i < arr.size(); ++i)
{
sum += arr[i];
min_sum = min(sum, min_sum);
for (ll j = 0; sum - (j * j) >= min_sum; ++j)
{
if (m.count(sum - (j * j)) == 1)
{
res += m[sum - (j * j)];
}
}
m[sum] += 1;
}
cout
<< "Case #" << t << ": " << res << endl;
}
}
計算量は、Aの各要素のループと、累積和を用いた計算のループで、後者のループでは累積和の最大値はN*MAX_Aで、またその時のsquareの個数は
参考
こちらを参考にしました。
Discussion