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回 加算する事を想定しなくてはいけませんでした。
int型の数値表現可能な範囲は、 *2 なので、加算途中で桁あふれしてしまう事が判ります。
accumulate の計算途中および結果の型は、第３引数で指定します。
型を明示する為、サフィックス *3を初期値に付加します。
今回は long long にする為、第3引数を 0LLとしました。
(初期値の0とlong longのサフィックスであるLLを付加)
これでオーバーフローせず正しい戻り値を受け取れました！
std::accumulate の型
今すぐ使える C++ コーディングテクニック集 - torus711 のアレ
前項でも微妙に触れていますが、std::accumulate の戻り値の型は第三引数によって決まります。入力の範囲が long long 型だったとしても、初期値が int 型のリテラルである 0 であれば int 型として足し込んでいくのでオーバーフローしてしまいます。こういった場合は 0LL とサフィックスを付けて long long 型のリテラルにしてあげるとうまくいきます。
#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引数に最初から double の 0.0 を渡すと、オーバーフローもせず、更に総和をキャストする事が不要となる様でした(学び)。
double型の仮数部は 個の数(
)を表現出来る為、制約にも収まります。*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; }
なので結論としては、↑このコードが最適そう...(おわり)
