AtCoder Beginner Contest 037 - C - 総和
愚直にやったらTLEなるかと思ったけど普通に通った。
考えたこと
愚直にやるなら、2重ループでいいかな。ただこれだと, $ N=10^5, $ K=10^3とかの時の計算量が$ O(10^{8})なので間に合わないかなーと思い出したら普通に通った(重そうなテストケースで1300msくらいはかかっているけど)、ただ、これは正規解じゃない気がするのでもう少し考える
新しい部分列を見る時に全てを見る必要はないはず(前の部分列とかぶってるのがあるので)
https://gyazo.com/d5d3b6198985f8b851189ffc7c554dc1
汚い図だけど、1,2,3,4,5,9,2,3...というaで、K=4として、部分列を見ると1つ目は1,2,3,4, 2つ目は2,3,4,5この時真ん中の2,3,4は共通だということが言える、となれば新しい部分列を見るときは、今の部分列の先頭を抜いた後に、新しい1つを追加してあげればいい、これなら$ O(N)で求めれるはず
提出したコード
code: 計算量を落とした版.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
ll n,k; cin >> n >> k;
vector<ll> a(n);
ll ans = 0;
// 先頭からkまでの合計を求める
ll tmp = 0;
ans += tmp;
for(int i=1; i < n-k+1; i++) {
// 変わるのは、新しく追加されるところと、1つ前のとこだけ
ans += tmp;
}
cout << ans << endl;
return 0;
}
code: 最初に出したやつ.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
ll n,k; cin >> n >> k;
vector<ll> a(n);
ll ans = 0;
rep(i, n-k+1) {
for(int j=i; j<k+i; j++) {
}
}
cout << ans << endl;
return 0;
}