競プロ参加日記013 AtCoder Beginner Contest 178

2020年9月14日 00:57

・はじめに

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がパズル天才コンテストなら辞めます。)

この記事が気に入ったらサポートをしてみませんか？