問題

C - Splitting Pile

問題文

すぬけくんとアライグマは N 枚のカードの山を作りました。カードの山の上から i 番目のカードには整数 ai が書かれています。 N 枚のカードを分け合うことにしました。すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。このとき、すぬけくんもアライグマも 1 枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ x,y として、|x−y| を最小化したいです。|x−y| としてありうる値の最小値を求めなさい。

制約

* 2 ≤ N ≤ 2 × 10^5

* -10^9 ≤ ai ≤10^9

* aiは整数

とこんな感じ入力された合計を管理して、その値の時のアライグマとすぬけくんの差の絶対値と今までの差の最小を比べてどちらが小さいかを計算していけばいいと考えて和を管理するために累積和を使っていました。そんなこんなで、累積和を使って解いていたのですが、これ累積和いらないってわかり、変数で解きました。

考えたこと

数列の合計値と i までの和がわかれば、すぬけくんとアライグマの両方のカードの数字が算出することが可能になります。方程式の関係になり数式で考えるとわかりやすいです。

sum(合計値), sunuke(すぬけくんの数),arai(アライグマの数)
sum = sunuke - arai
arai = sum - sunuke
sunuke = sum - arai

と関係が成り立ちます。これが成り立つのですぬけくんとアライグマの減算は求められ、最小値の比較に対するものは一つ出来上がります。あとは答えを設定し、それぞれの要素に置いて差を求め最小値を算出すればO(N)時間で終わるため、問題が解けることになります。

フロー

* 入力受け取り
* 数列の和の計算
* 答えを10^18で設定
* すぬけくんとアライグマの数を0で設定
* 数列の各要素に対してループ
     * すぬけくんの数に該当要素を足す
     * アライグマの値を `総和 - すぬけくんの和` とする
     * もし、その要素が最終要素でない時に以下の処理をする
         * 答えに 今の答えとすぬけくんとアライグマの差の絶対値を取ったものの小さい方を代入
* 答えを出力

とこんな感じ答えを10¹⁸で設定しているのは初期に10⁹以上の数が10⁹個こないのが制約により保証されているからです

プログラム

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(void){
    long long N;
    cin >> N;
    vector<long long> a(N);
    vector<long long> resi(N);
    long long sum = 0;
    for(long long i = 0;i < N;i++){
        resi[i] = 0;
    }
    for(long long i = 0;i < N;i++){
        cin >> a[i];
        sum += a[i];
    }
    long long ans = 1000000000000000000;
    long long sunuke = 0;
    long long arai = 0;
    for(long long i = 0;i < N; i++){
        sunuke += a[i];
        arai = sum - sunuke;
        if(i < N - 1){
            ans = min(ans,abs(sunuke - arai));
        }
    }
    cout << ans << endl;
    return 0;
}

こんな感じでAC取れました。解答をみて気づいたのですが、最小値をとる時に abs(sum - 2 * sunuke) でも良さげですね等式変形をしたら辻褄が合います。でも、数弱にはデータ構造に落とし込んだ方がわかりやすい。。

xlkeiの日記

ABC-067 C Splitting Pile を解いてみた

問題

問題文

制約

考えたこと

フロー

プログラム