競プロ参加日記013 AtCoder Beginner Contest 178
・はじめに
A,B,C,Dの4完でした。
レートは下がったものの、水色は保てていたので来週のACL ContestはRated参加できそうです。
・A - Not
色々やり方はあると思いますが、私はビット反転の際に1-xを好んで使うため、今回もそれを用いて実装しました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int x;
cin>>x;
cout<<1-x<<endl;
}
・B - Product Max
プラスにできるならbd(+*+)とac(-*-)の最大、できないならac(+*-)などの最大...
と場合分けがしんどいです。ただ、幾つか例を並べると(a,b)*(c,d)の4通りの組み合わせのいずれかがmaxとなりそうです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long a,b,c,d;
cin>>a>>b>>c>>d;
long long pat1=a*c;
long long pat2=a*d;
long long pat3=b*c;
long long pat4=b*d;
cout<<max(pat1,max(pat2,max(pat3,pat4)))<<endl;
}
・C - Ubiquity
0,9が二つで他は0~9任意なので、コンビネーションを使えば解けそうですが、数学が苦手なのでdpしました。
dp[0が出たか][9が出たか][何個目か]かで桁dp的なことをします。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N;
const long long mod=1000000007;
cin>>N;
long long dp[2][2][N+10];
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<=N+9;k++){
dp[i][j][k]=0;
}
}
}
dp[0][0][0]=1;
for(int i=0;i<N;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
for(int l=0;l<=9;l++){
//cout<<i<<","<<j<<","<<k<<","<<dp[j][k][i]<<endl;
dp[j][k][i]%=mod;
if(l!=0&&l!=9) dp[j][k][i+1]+=dp[j][k][i];
else if(l==0) dp[1][k][i+1]+=dp[j][k][i];
else if(l==9) dp[j][1][i+1]+=dp[j][k][i];
}
}
}
}
cout<<dp[1][1][N]%mod<<endl;
}
・D - Redistribution
嘘解法というか、入力のエスパーをしてしまった。
dp[何回足したか][合計値]でdpしました。ただ、これだとO(S^3)でTLEです。無駄ループを削って、入力例3の1729は1.3sくらいで通るようになったのですが、2000とかだと8sかかります。
Atcoderはテストケースが弱い(ごめんなさい)ので、最大近いケースは2000しかないと踏んで、2000の答えは埋め込みました。
#include<iostream>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
long long S;
const long long mod=1000000007;
cin>>S;
if(S==2000){
cout<<"883312678"<<endl;
return 0;
}
long long dp[S+10][S+10];
for(int i=0;i<S+10;i++){
for(int j=0;j<S+10;j++){
dp[i][j]=0;
}
}
dp[0][0]=1;
long long to=S/3+1;
for(int j=0;j<to;j++){
for(int i=j;i<S;i++){
for(int k=3;k<=S-i;k++){
dp[i+k][j+1]+=dp[i][j]%mod;
}
}
}
long long sum=0;
for(int i=0;i<=S;i++){
sum+=dp[S][i];
sum%=mod;
//cout<<sum<<endl;
}
cout<<sum<<endl;
}
※上記コードは嘘解法ですが、1730~2000全て埋め込めばちゃんとした解法にはなります。
この問題、C問題に引きずられて変なdpしましたが、状態に何回足されたとかいらないですね...。
dp[合計値]として、みて行けばいいだけです。
#include<iostream>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long S;
const long long mod=1000000007;
cin>>S;
long long dp[S+10];
for(int i=0;i<S+10;i++){
dp[i]=0;
}
dp[0]=1;
for(int i=0;i<S;i++){
for(int k=3;k<=S-i;k++){
dp[i+k]+=dp[i]%mod;
}
}
cout<<dp[S]%mod<<endl;
}
・E - Dist Max
O(N^2)かかるので式変形して考えます。
abs(xi-xj)+abs(yi-yj)は
=max(xi-xj,xj-xi)+max(yi-yj,yj-yi) ※正負の正の方がmaxとして残る
=max(xi-xj+yi-yj,xi-xj+yj-yi,xj-xi+yi-yj,xj-xi+yj-yi) ※正+正のパターンが一番大いのでabsが残る。
=max(xi+yi-(xj+yj),xi-yi-(xj-yj),xj-yj-(xi-yi),xj+yj-(xi+yi)) ※maxの要素を整理
=max(abs(xi+yi-(xj+yj)),abs(xi-yi-(xj-yj)) ※1,4番目の要素、2,3番目の要素がmax(a-b,b-a)になっているので、abs->maxの逆変換でabs(a-b)にできる。
=max(abs(ci-cj),abs(di-dj)) ※x+y=c,x-y=dと置く。
上記変換は45度回転と呼ばれるものです。
このとき、ci,diは大きく、cj,djは小さくした方がいいので
=max(cmax-cmin,dmax-dmin)
となり、それぞれのminmaxはO(N)で求められます。
元の式は二つのmax(abs)の和なので、両方考えないといけないのですが、45度回転することによって一つのmaxとなり、こいつだけの帳尻を合わせればいいようになりました。
魔法かな?????
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int cmax=INT_MIN;
int dmax=INT_MIN;
int cmin=INT_MAX;
int dmin=INT_MAX;
for(int i=0;i<N;i++){
int x,y;
cin>>x>>y;
int c=x+y;
int d=x-y;
cmax=max(cmax,c);
cmin=min(cmin,c);
dmax=max(dmax,d);
dmin=min(dmin,d);
}
cout<<max(cmax-cmin,dmax-dmin)<<endl;
}
これ、典型とか高校数学とかって話だと思うけど無理ですね...。
abs(xi-xj)+abs(yi-yj)の式を見て、式変形しようとは思わない。
・F - Contrast
頭から見ていって、同じなら適当な箇所でswapする貪欲書いたら通った。
眠たいし、Atcoderのやる気が今はないのでこれで放置(多分嘘解法)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int A[N];
int B[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
for(int i=0;i<N;i++){
cin>>B[i];
}
int j=0;
for(int i=0;i<N;i++){
if(A[i]==B[i]){
for(int c=0;c<N;j++,c++){
if(A[i]!=B[j]&&A[j]!=B[i]){
swap(B[i],B[j]);
break;
}
if(j==N-1) j=-1;
}
if(A[i]==B[i]){
cout<<"No"<<endl;
return 0;
}
}
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++){
cout<<B[i]<<" ";
}
cout<<endl;
}
・おわりに
今日は格段と天才様コンテストって感じがした。
問題的にはcodeforcesの方が楽しいので、Atcoderは引退するかも...?(ARCがパズル天才コンテストなら辞めます。)
この記事が気に入ったらサポートをしてみませんか?