AtCoder ABC 169 反省

atcoder.jp

結果

A問題のみAC。B問題とC問題、F問題には挑戦したが駄目だった。悔しい。とりあえずコンテスト後にツイッターを見るなどしてB問題とC問題は理解したのでいろいろメモする。

B問題

問題概要

個の整数 ～ が与えられる。これらの積を計算して出力せよ。ただし答えが を超える場合は を出力せよ。

制約

,

解法

罠が二つあるので注意する必要がある。

1つ目は積が を超える場合である。これは単に積を計算していって、積が を超えた時に を出力するように場合分けすればよい。ただし積を格納する変数の型にint64_tなどを用いている場合は などを計算した時にオーバーフローしてしまうことがある。なので を取り除くような形で場合分けの処理を行うとよい。

2つ目は入力 に 0 が含まれる場合。このとき答えは問答無用で 0 になるため場合分けしておく必要がある。例えば という入力が与えられた時、あらかじめ 0 が入力で与えられる場合を取り除いておかないとWAとなる。

ACしたコード

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

int main() {
  ll n;cin>>n;
  vector<ll>a(n);
  for(int i=0;i<n;i++){
    cin >>a.at(i);
    if(a.at(i)==0){
      cout <<0<<endl;
      return 0;
    }
  }
  ll seki=1;
  for(int i=0;i<n;i++){
    if(1000000000000000000/seki<a.at(i)){
      cout <<-1<<endl;
      return 0;
    }
    seki*=a.at(i);
  }
  cout <<seki<<endl;
}

感想

積が を超える場合の処理の仕方を思いつかなかったのが悔しい。

C問題

問題概要

整数 と実数 が与えられる。小数点以下を切り捨てて を出力せよ。

制約

Bは小数第二位まで与えられる。

解法

double型の精度が 程度なので愚直に掛け算を行うと精度が足りない。なので を100倍して整数型として計算した後に100で割ることにする。
ただしここでも少し気を付ける必要がある。仮に の入力を double 型の変数に格納してからそれを100倍し整数型に格納するという方法をとるとする。この場合、小数をコンピュータで扱う際にどうしても出てしまう小さな誤差によって計算がうまくいかないことがある。例えば のときそれをdouble 型の変数に格納して100倍すると となってしまう。なので の入力は文字列として受け取ってしまうのが安全かもしれない。

ACしたコード

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

int main() {
  ll a;
  string b;
  cin >>a>>b;
  ll tmp1,tmp2,tmp3;
  tmp1=(ll)(b.at(0)-'0')*100;
  tmp2=(ll)(b.at(2)-'0')*10;
  tmp3=(ll)(b.at(3)-'0');
  ll b100=tmp1+tmp2+tmp3;
  ll ans=a*b100/100;
  cout <<ans<<endl;
}

感想

double型の誤差を考えずに b(double型)*100 という演算をやってしまったのが悔やまれる。

総括

次頑張ろう