競プロ参加日記002 ABC169 参加
●全体的な感想
こういうA,B,C問題はやめて！！
結果はA,B,C,Dの4完で2240位でした。(4WAはやばい)
●A問題 Multiplication 1
制約もよわよわなので脳死で問題文に従いましょう
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//cpp_int 多倍長
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
int A,B;
cin>>A>>B;
cout<<A*B<<endl;
}●B問題 Multiplication 2
10^18検知が地味にややこしい問題です。
私は多倍長ライブラリを使いました。
https://note.com/nullkara/n/n7ca680f3fc7b
オーバーフロー怖いよねって感じで逃げました。
0が途中にあれば、関係なく0になるのでそれも忘れずに
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//cpp_int 多倍長
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
cpp_int A[100000];
cpp_int sum;
int N;
bool zf=false;
cin>>N;
for(int i=0;i<N;i++){
cin>>A[i];
if(A[i]==0) zf=true;
}
if(zf){
cout<<"0"<<endl;
return 0;
}
sum=A[0];
for(int i=1;i<N;i++){
sum*=A[i];
if(sum>1000000000000000000){
cout<<"-1"<<endl;
return 0;
}
}
cout<<sum<<endl;
}
●C問題 Multiplication 3
SNSで若干話題になってそうな問題です。
小数同士の計算は誤差が怖いので、整数に直すのが王道です。
ただ、今回の場合B*100みたいな戻し方でも誤差が発生するそうです。
なので、文字列として受け取って整数にする方法で解きました。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
int A;
string B;
cin>>A>>B;
int Bint;
Bint=(B[0]-'0')*100+(B[2]-'0')*10+(B[3]-'0')*1;
int sum=A*Bint;
cout<<(int)(sum/100)<<endl;
}※doubleは64bitフルに使えない(指数部分とかがあるため)ので、15桁くらいしか精度がないそうです。
A=15桁、B=3桁なので、18桁の計算になります。よってdoubleの演算を行うとWAをくらいます。
※B*100でも誤差が生じるのは以下のぬるからのツイートを参照してね
https://twitter.com/NullKara/status/1267096737740550145
多分だけど、0.29は内部的には0.29じゃない(2進で表現できない)ため、若干の誤差が生じてるっぽい。
●D問題 Div Game
異なる(素数^N)で何回割れるかゲームです。
篩で素数を出して、素直に実装します。
この手の問題の篩は、√Nくらいまでで十分です。
Nを√Nまでの素数で割っていって、1にならない場合、その時のN自身が素数になります。
(√N以上同士の掛け算の場合、Nを超えてしまいます。また、素数で割っていっているため√N以下の素数は約数ではありません。)
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define MAX 1000100
signed main(){
vector<int> v;
int pr[MAX+1]={0};
int N;
cin>>N;
for(int i=2;i<=MAX;i++){
if(pr[i]==0){
v.push_back(i);
for(int j=i;j<=MAX;j+=i){
pr[i]=1;
}
}
}
int ans=0;
for(int i=0;i<v.size();i++){
int sum=0;
while(N%v[i]==0){
sum++;
N/=v[i];
}
int add=0;
int mnus=1;
while(1){
sum-=mnus;
if(sum<0) break;
add++;
mnus++;
}
ans+=add;
}
if(N!=1) ans++;
cout<<ans<<endl;
}
●E問題 Count Median
コンテスト終了後に解説PDFを見て解きました。
絵を書いて実際に求めれば、奇数の場合はAの真ん中～Bの真ん中までが中央値になります。
ここまでは、コンテスト中に分かったのですが、奇数の場合が分かりませんでした。
ただ、奇数の場合も同様で中央値の最小値はA[]の中央値、中央値の最大値はB[]の最大値だと分かります。
この時、A[],B[]の中央値の元となった2つの値を±1してやると、中央値が0.5ずつ変動します。
この変動は中央値の最小値と中央値の最大値の間があくことなく、動かすことができます。
なので、この問題はA[]の中央値とB[]の中央値の差を求める問題(偶数の場合、0.5ずつ進むので2倍する)といえます。
(詳しくは、解説PDFやyoutubeを見てください> <)
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define MAX 300000
struct S{
int A;
int B;
int sortnum;
bool operator<(const S s) const{
if(sortnum==0){
return B>s.B;
}
else{
return A<s.A;
}
}
};
signed main(){
int N;
S AB[MAX];
cin>>N;
for(int i=0;i<N;i++){
int A,B;
cin>>A;
cin>>B;
S tmps;
tmps.A=A;
tmps.B=B;
tmps.sortnum=0;
AB[i]=tmps;
}
sort(AB,AB+N);
int rl,ll,r2,l2;
int num=(N-1)/2;
rl=AB[num].B;
r2=AB[num+1].B;
for(int i=0;i<N;i++){
AB[i].sortnum=1;
}
sort(AB,AB+N);
ll=AB[num].A;
l2=AB[num+1].A;
int ln=ll;
int rn=rl;
if(N%2==0){
cout<<rl+r2-ll-l2+1<<endl;
}
else{
cout<<rn-ln+1<<endl;
}
}
●まとめ
マクロの整備がしたい。
※REPとか入れてる割に仕えてない
※#define int long long をそろそろ封印したい(さすがの私もこれはダメだと思う)
Atcoderさん、問題に小数絡ませるのやめませんか？(N回くらい誤差で泣いてる)