C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

No.476 正しくない平均|yukicoder

No.476 正しくない平均 - yukicoder を解きました。
std::accumulateの戻り値の型 にはまったのでメモ。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( (double)accumulate( vc.begin(), vc.end(), 0LL ) / N == A ? "YES" : "NO" ) << endl;
    return 0;
}

accumulate *1で総和を正しく得られなかったのですが、
問題の制約を見ると、最大で  {10^9} を 10回 加算する事を想定しなくてはいけませんでした。
int型の数値表現可能な範囲は、  {-2,147,483,648 ~ 2,147,483,647} *2 なので、加算途中で桁あふれしてしまう事が判ります。

accumulate の計算途中および結果の型は、第3引数で指定します。
型を明示する為、サフィックス *3を初期値に付加します。
今回は long long にする為、第3引数0LLとしました。
(初期値の0とlong longのサフィックスであるLLを付加)
これでオーバーフローせず正しい戻り値を受け取れました!

std::accumulate の型
前項でも微妙に触れていますが、std::accumulate の戻り値の型は第三引数によって決まります。入力の範囲が long long 型だったとしても、初期値が int 型のリテラルである 0 であれば int 型として足し込んでいくのでオーバーフローしてしまいます。こういった場合は 0LL とサフィックスを付けて long long 型のリテラルにしてあげるとうまくいきます。

今すぐ使える C++ コーディングテクニック集 - torus711 のアレ
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( accumulate( vc.begin(), vc.end(), 0.0 ) / N == A ? "YES" : "NO" ) << endl;
    return 0;
}

最初のコードでは第3引数を0LLとしてlong long型を明示しましたが、
accumulateの戻り値の型は、初期値として渡した値の型になる事を踏まえると、
第3引数に最初から double0.0 を渡すと、オーバーフローもせず、更に総和をキャストする事が不要となる様でした(学び)。

double型の仮数部は  { 2^{53} } 個の数(  {= 9,007,199,254,740,991} )を表現出来る為、制約にも収まります。*4

ですが、浮動小数点数の演算に固有の誤差(丸め誤差、桁落ち、情報落ち)が常に生じる可能性がある *5 事を考慮すると、可能な限り整数での計算が好ましい様です。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    long long A;
    cin >> N >> A;
    vector<long long> vc( N );
    for( auto &x : vc )
    {
        cin >> x;
    }
    cout << ( accumulate( vc.begin(), vc.end(), 0LL ) == N * A ? "YES" : "NO" ) << endl;
    return 0;
}

なので結論としては、↑このコードが最適そう...(おわり)