今回の記事
ABC169に参加しました。
今回はとうとうA問題までしか解けず。。
解説や他の方のソース、TwitterでB問題とC問題についても理解できたので
今回はC問題まで解説も合わせて記載します。
◆私のAtcoderアカウント
https://atcoder.jp/users/MakotoMM?lang=ja
◆Twitterアカウント
https://twitter.com/Makoto_M_coder
その前に
ついにAtCoder社長のChokudaiさんにTwitterフォローしてもらいました(笑)
またその他にも勉強しながら様々な人にフォローしてもらえました。ありがとうございます。
当日の解答結果
冒頭にも記載したのですが、今回はA問題しか解けなかったです。
B問題とC問題は気を付ける点は気づけてたのですが、
実際のコードで何が問題かわからず、、
パフォーマンスについて
ぐぬぬ、、、
振り返りと反省
1.プログラミング時間が確保できなかった
外出自粛も緩和されつつある状況なのもあるのか
仕事が急に忙しく、前みたいに勉強の時間をとることができませんでした。。
とはいえ勉強してたら今回解けたのかというと別問題かな。。
2.ジャッジシステムの表示変更
これは本当に困った。。。
すでに戻っていますが、通常だとどのサンプルがAC(正解)、WA(不正解)がわかるのですが、
今回のコンテスト中は全部合わせてAC(正解)、WA(不正解)ってしか表示されませんでした。
特にBもC問題もサンプルが1つNGだっただけだったにもかかわらず、
考え方違うのかなと思って全部書き直したりしてた(そしてより不正解になるコードになってた)ので苦しかったです。。
問題解説
今回は冒頭にも記載しましたがC問題まで解説します！！
A問題：Multiplication 1
問題文抜粋
解説
AとBを入力として受け取って、掛け合わせた結果を出力します。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main(void) {
int A,B;
cin >> A >> B;
cout << A*B << endl; //A*Bを出力
return 0;
}
B問題：Multiplication 2
問題文抜粋
解説
この問題が非常に難しいと言う話に解説でもなっていました。
入力値$A1、A2....An$を全て掛け算します。
ただし入力値の取りうる値が$10^{18}$以下です。
そのためlong long intの最大値である$9×10^{18}$程度を超える可能性があり
オーバーフローしてしまうので、丁寧に処理する必要があります。
掛け算した結果が$10^{18}$を超えたタイミングで−１を出力してあげればいいです。
A[i]<=1000000000000000000/ans
//A[i]*ans <= 1000000000000000000はA[i]*ansが
//オーバーフローしてしまうので式展開してあげる
これらをまとめて以下のように記載しました。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main(void) {
int N;
cin >> N;
ll A[N];
rep(i,N){
cin >> A[i];
if(A[i]==0){ //0があるとどれだけ掛けても0なので0を出力しておわる
cout << 0 << endl;
return 0;
}
}
ll ans=1;
for(int i=0; i<N; i++){
if(A[i]<=1000000000000000000/ans ) //A[i]*ansが10^18を超えないと
ans *= A[i]; //A[i]の値をかける
else{ //A[i]*ansが10^18を超えたら
cout << -1 << endl; //-1を出力し終了する
return 0;
}
}
cout << ans << endl;
return 0;
}
C問題：Multiplication 3
問題文抜粋
解説
この問題も同じく難しいねという話になっていました。
解説でも記載がありましたが、double型で扱うデータのサイズを超える状態になるため
ただ掛け算するだけではオーバーフローになってしまいます。
この問題についてはコンテスト終了後、非常にわかりやすいページがあったのでそちらを参照ください。
(こんな高い品質をすぐに出せるなんてすごい。。)
◆◆けんちょんの競プロ精進記録◆◆
私は文字列で受け取るやり方でコンテスト終了後にACしました。
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main(void) {
ll A;
string B;
cin >> A >> B;
ll i,d,dd;
i = B[0] - '0';
d = B[2] - '0';
dd = B[3] - '0';
ll ans;
ans = (A*(i*100+d*10+dd))/100;
cout <<ans << endl;
return 0;
}
今後に向けて
うーんなかなか厳しい。。。
そういえば螺旋本を買ってみました！
こちらも勉強して共有できそうな内容があれば記事にしたいと思います。
最後に
いかがだったでしょうか？
見ても解らないやもう少しこうすると良いのではないか？といった暖かい言葉ドシドシお待ちしています。
またTwitterも是非お気軽にフォローしてください。
https://twitter.com/Makoto_M_coder