競プロ参加日記005 AtCoder Beginner Contest 173(ABC173) 参加

ぬるから

https://atcoder.jp/contests/abc173

・全体的な感想
A,B,C,D,Eの5完でした。
今回みたいなE問題好き。
今回みたいなD問題嫌い。

・A問題 Payment
A問題にしては、結構ややこしい気がします。
N%1000が、1000円札ではぴったり払えない金額なので、1000からそれを引けばお釣りになります。N%1000==0の時は要注意。入力例が強くて助かった。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#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 N;
   cin>>N;
   int md=N%1000;
   if(md==0) cout<<"0"<<endl;
   else cout<<1000-md<<endl;
}

・B問題 Judge Status Summary
問題文通り実装するだけです。
この手の出力は手打ちすると、タイポでWAを取ることがあるのでコピペしましょう。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#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 N;
   cin>>N;
   int a=0,w=0,t=0,r=0;
   for(int i=0;i<N;i++){
       string in;
       cin>>in;
       if(in=="AC") a++;
       else if(in=="WA") w++;
       else if(in=="TLE") t++;
       else r++;
   }
   cout<<"AC x "<<a<<endl;
   cout<<"WA x "<<w<<endl;
   cout<<"TLE x "<<t<<endl;
   cout<<"RE x "<<r<<endl;
}

・C問題 H and V
難しそうですが、制約がよわよわ(H,W<=6)です。
全パターン試しても2^12＝4096パターンで、かなり余裕があります。
bit全探索で問題なしです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#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 H,W,K;
   string c[10];
   cin>>H>>W>>K;
   for(int i=0;i<H;i++){
       cin>>c[i];
   }
   int ans=0;
   for(int i=0;i<1<<(W+H);i++){
       int w[10]={0};
       int h[10]={0};
       for(int j=0;j<W;j++){
           w[j]=(i>>j)%2;
       }
       for(int j=0;j<H;j++){
           h[j]=(i>>(W+j))%2;
       }
       int ct=0;
       for(int j=0;j<H;j++){
           for(int k=0;k<W;k++){
               if(c[j][k]=='#'&&h[j]==0&&w[k]==0){
                   ct++;
               }
           }
       }
       if(ct==K){
           ans++;
       }
   }
   cout<<ans<<endl;
}

・D問題 Chat in a Circle
未証明で感覚で解きました(ごめんなさい)
大きい値から順に並べたほうが、大きい値を取り込める機会が多そうに見えます。(小さい値に邪魔されない)
また、大きい値が取れるならとっとと取ってしまったほうが良いほうに思えます。(これも、後々小さい値で邪魔されないように)
上記の感覚をもとに、貪欲しました。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#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(){
   multiset<int> s;
   int N;
   vector<int> A;
   cin>>N;
   for(int i=0;i<N;i++){
       int in;
       cin>>in;
       A.push_back(in);
   }
   sort(A.begin(),A.end());
   int ans=0;
   for(int i=A.size()-1;i>=0;i--){
       int n=A[i];
       if(s.size()==0){
           s.insert(n);
       }
       else{
           int k=*(s.rbegin());
           ans+=k;
           s.erase(s.find(k));
           s.insert(n);
           s.insert(n);
       }
   }
   cout<<ans<<endl;
}

この貪欲の場合、一人並ぶごとに大きい値の場所が一つ減って、並んだ値の場所が2つ増えます。なので、実装もset等で管理するだけで書けますね。

・E問題 Multiplication 4
Eにしては簡単というか、そこまで高度なアルゴリズムがいらないので個人的に得意でした。
答えが絶対にマイナスになる場合は、絶対値が低くなるに、プラスにできる可能性がある場合は絶対値が大きくなるようにすればいいです。
ゼロがある場合に気を付けながら丁寧に場合分けすれば解けます。

問題のMODとC++のMOD(%)はマイナスの場合の挙動が違うようです。
なので、MODを取る際は問題文の通りになるように気を付ける必要があります。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#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 N,K;
   vector<int> p,m,z;
   cin>>N>>K;
   for(int i=0;i<N;i++){
       int in;
       cin>>in;
       if(in>0) p.push_back(in);
       else if(in<0) m.push_back(in);
       else z.push_back(in);
   }
   int ans=1;
   sort(p.begin(),p.end());
   sort(m.begin(),m.end());
   //allplus
   if(m.size()==0){
       if(p.size()>=K){
           for(int i=0;i<K;i++){
               ans*=p[p.size()-1-i];
               ans%=MOD;
               while(ans<0) ans+=MOD;
           }
           ans%=MOD;
           while(ans<0) ans+=MOD;
           cout<<ans%MOD<<endl;
       }
       else{
           cout<<"0"<<endl;
       }
   }
   //allminus
   else if(p.size()==0){
       if(m.size()>=K){
           if(K%2==1){
               if(z.size()>0){
                   cout<<"0"<<endl;
               }
               else{
                   for(int i=0;i<K;i++){
                       ans*=m[m.size()-1-i];
                       ans%=MOD;
                       while(ans<0) ans+=MOD;
                   }
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
                   cout<<ans%MOD<<endl;
               }
           }
           else{
               for(int i=0;i<K;i++){
                   ans*=m[i];
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
               }
               ans%=MOD;
               while(ans<0) ans+=MOD;
               cout<<ans%MOD<<endl;
           }
       }
       else{
           cout<<"0"<<endl;
       }
   }
   //all
   else if(N==K){
       for(int i=0;i<p.size();i++){
           ans*=p[i];
           ans%=MOD;
           while(ans<0) ans+=MOD;
       }
       for(int i=0;i<m.size();i++){
           ans*=m[i];
           ans%=MOD;
           while(ans<0) ans+=MOD;
       }
       for(int i=0;i<z.size();i++){
           ans*=z[i];
           ans%=MOD;
           while(ans<0) ans+=MOD;
       }
       ans%=MOD;
       while(ans<0) ans+=MOD;
       cout<<ans%MOD<<endl;
   }
   //other
   else
   {
       if(p.size()+m.size()>=K){
           int ps=p.size()-1;
           int ms=0;
           int n=K;
           if(n%2==1){
               ans*=p[ps--];
               n--;
               ans%=MOD;
               while(ans<0) ans+=MOD;
           }
           while(n!=0){
               if(ps-1<0){
                   ans*=m[ms++];
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
                   ans*=m[ms++];
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
               }
               else if(ms+1>=m.size()){
                   ans*=p[ps--];
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
                   ans*=p[ps--];
                   ans%=MOD;
                   while(ans<0) ans+=MOD;
               }
               else{
                   if(m[ms]*m[ms+1]>p[ps]*p[ps-1]){
                       ans*=m[ms++];
                       ans%=MOD;
                       while(ans<0) ans+=MOD;
                       ans*=m[ms++];
                       ans%=MOD;
                       while(ans<0) ans+=MOD;
                   }
                   else{
                       ans*=p[ps--];
                       ans%=MOD;
                       while(ans<0) ans+=MOD;
                       ans*=p[ps--];
                       ans%=MOD;
                       while(ans<0) ans+=MOD;
                   }
               }
               n-=2;
           }
           ans%=MOD;
           while(ans<0) ans+=MOD;
           cout<<ans%MOD<<endl;;
       }
       else{
          cout<<"0"<<endl;
       }
   }
}

boostの多倍長を使うとTLEしました。
桁数が爆発的に増えるため、計算量が余裕っぽくても危ないみたいです...。

・F問題 Intervals on Tree
全通りの、頂点のあるなしの独立したグラフの個数の和を求める問題。
UnionFind使えば通りそうだなぁと思いながら、全通りをいい感じに早くする方法が思い浮かばずでした。

・まとめ
久々にいい感じに解けた気がします。
そろそろ水色コーダーになりそうです！！

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