[BOJ/C+]13900次順序対の積の和

6741 ワード
boj cpp テキストリンク
最初は単純にBrute Forceで解くだけでした.
  • と入力します.
  • for文を使用して、外部for文をi=0からi=n-1に繰り返し、内部for文をj=i+1からj=nに繰り返します.
  • arr[i]*arr[j]の値を加算します.
    • こうやって解くとタイムアウト.△これは予想された結果です.
    n=4,arr={1,2,3,4}の場合を考える.
    sum=(1 x 2)+(1 x 3)+(1 x 4)+(2 x 3)+(2 x 4)+(3 x 4)についてまとめる
    sum=1 x(2+3+4)+2 x(3+4)+3 x(4)が見られます.
    googlingの結果,この形式の問題は部分和で解決したほうがよいことが分かった.

    Code

    #include <iostream>
#define MAX 100001
using namespace std;

int n;
long long arr[MAX];
long long psum[MAX];
long long sum=0;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        if(i==0){
            psum[i]=arr[i];
        }
        else{
            psum[i]=psum[i-1]+arr[i];
        }
    }
}

long long Solution(){
    for(int i=0; i<n-1; i++){
        sum+=arr[i]*(psum[n-1]-psum[i]);
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution();
    return 0;
}
    部と再解を用いた場合,数の範囲が正確に決定されず,配列をint型と宣言したため,エラー処理される.
    問題を解く前に、よく確認数の範囲を練習します.
    [アルゴリズム/Programmers]文字列基本
    前処理スレッドの問題解決策