公式

D - Distance Table 解説 by en_translator


For each pair of integers \((i,j)\), the distance between station \(i\) and station \(j\) can be found as \(D_i+D_{i+1}+\cdots+D_{j-1}\), which can be computed with a for statement.
A naive implementation will require a triple loop, which is fast enough under the constraints of this problem.

The algorithm can be made faster by reducing it to a double loop, using the fact that the distance between stations \(i\) and \(j\) can be calculated as \(S_j-S_i\), where \(S_k=D_1+D_2+\cdots+D_{k-1}\) is the distance between station \(1\) and station \(k\).

Sample code in C++ (triple loop):

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	
	vector<int>d(n-1);
	for(int i=0;i<n-1;i++){
		cin>>d[i];
	}

	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			int ans = 0;
			for(int k=i;k<j;k++)ans+=d[k];
			cout << ans;
			if(j<(n-1))cout << " ";
			else cout << endl;
		}
	}

	return 0;
}

Sample code in C++ (double loop):

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	
	vector<int>s(n);
	for(int i=1;i<n;i++){
		cin>>s[i];
		s[i]+=s[i-1];
	}

	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			cout<<(s[j]-s[i]);
			if(j<(n-1))cout<<" ";
			else cout<<endl;
		}
	}

	return 0;
}

Sample code in Python (triple loop):

n=int(input())
d=list(map(int, input().split()))

for i in range(n-1):
    for j in range(i+1,n):
        if j<n-1:
            print(sum(d[i:j]),end=' ')
        else:
             print(sum(d[i:j]))

投稿日時:
最終更新: