競プロ参加日記008 AtCoder Beginner Contest 177 参加(ABC177)

2020年8月29日 22:44

ぬるからです。
https://atcoder.jp/contests/abc177
ABC117に参加しました。

・はじめに

A,B,C,D,Eの5完でした。
順位的にも青パフォが何とか出そうなくらいで、満足です。

・A問題　Don't be late

D÷S分がT分より大きいか小さいかを見ればいいです。
D÷Sを計算した際に小数が発生することがあります。intで計算してそのまま切り捨てるとだめなので、doubleにするなり切り上げるなり、処置が必要です。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#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 D,T,S;
   cin>>D>>T>>S;
   int d=D/S+(D%S!=0);
   if(d<=T) cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
}

・B問題　Substring

Sのいくつかを書き換えて、TがSの部分文字列になるようにした際の、最小の書き換え数を求める問題です。
制約が1000文字以下と弱いので、部分文字列がSの先頭にある場合～末尾にある場合の全パターンに対して、幾つ変更する必要があるかを見ればよいです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#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(){
   string S,T;
   cin>>S;
   cin>>T;
   int ans=LLONG_MAX;
   for(int i=0;i<S.size();i++){
       int c=0;
       for(int j=0;j<T.size();j++){
           if(i+j>=S.size()){
               c=LLONG_MAX;
               break;
           }
           if(S[i+j]!=T[j]) c++;
       }
       ans=min(ans,c);
   }
   cout<<ans<<endl;
}

・C　Sum of product of pairs

Σ(J=i+1→N)AiAj=AiA0+AiA1+AiA2+....=Ai(A0+A1+A2+...)となります。
括弧内のAiは外側のiのシグマが一つ増えるごとに一つ増えます。
なので、内側のシグマの計算はN-i+1回する必要がなく、括弧内の数字を更新していけばO(1)で済ませれます。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#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;
   int A[200000];
   int sum=0;
   cin>>N;
   for(int i=0;i<N;i++){
       cin>>A[i];
       sum+=A[i];
       sum%=MOD;
   }
   int ans=0;
   for(int i=0;i<N;i++){
       sum-=A[i];
       sum%=MOD;
       ans+=sum*A[i];
       ans%=MOD;
   }
   while(ans<0) ans+=MOD;
   cout<<ans<<endl;
}

・D　Friends

友人関係を線でつないでツリーにした時、同じツリーにいる人間が友人関係になっているといえます。
こういう状態の場合、Union-Findを使うと上手くいきます。
Union-Findはある要素とある要素が同じ木構造かどうかを高速で計算できるデータ構造です。

同じツリーにいる人間は別々のグループにする必要があるため、答えは各ツリーのサイズの最大値になります。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#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
//https://drken1215.hatenablog.com/entry/2020/03/02/022900
struct UnionFind {
   vector<int> par;
   UnionFind(int n) : par(n, -1) { }
   int root(int x) {
       if (par[x] < 0) return x;
       else return par[x] = root(par[x]);
   }
   bool issame(int x, int y) {
       return root(x) == root(y);
   }
   bool merge(int x, int y) {
       x = root(x); y = root(y);
       if (x == y) return false;
       if (par[x] > par[y]) swap(x, y); // merge technique
       par[x] += par[y];
       par[y] = x;
       return true;
   }
   int size(int x) {
       return -par[root(x)];
   }
};
signed main(){
   int N,M;
   cin>>N>>M;
   UnionFind uf(N+1);
   for(int i=0;i<M;i++){
       int A,B;
       cin>>A>>B;
       uf.merge(A,B);
   }
   int ans=0;
   for(int i=1;i<=N;i++){
       ans=max(uf.size(i),ans);
   }
   cout<<ans<<endl;
}

※https://drken1215.hatenablog.com/entry/2020/03/02/022900
　けんちょんさんの上記の記事のUnion-Findをお借りしました。

・E　Coprime

GCD(A1,....AN)=.GCD(...GCD(GCD(A1,A2),A3)...,AN)なので、簡単に計算できますが、各ijのGCD(AiAj)が厄介です。普通に計算するとO(NN)かかります。
GCDが1になるということはどういうことかを考えると、高速化できます。
GCD1になる=共通の約数を持たない。ということです。
なので、各Aiの約数を調べて重複があるかどうかを考えればいいです。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#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
int gcd(int a,int b){
   if(a<b) return gcd(b,a);
   if(b==0) return a;
   return gcd(b,a%b);
}
#define MAX 1001000
signed main(){
   int sosuu[MAX]={0};
   vector<int> pri;
   for(int i=2;i<sqrt(MAX)+10;i++){
       if(sosuu[i]==0){
           pri.push_back(i);
           for(int j=i;j<sqrt(MAX)+10;j+=i){
               sosuu[j]=1;
           }
       }
   }
   int N;
   int A[MAX];
   cin>>N;
   for(int i=0;i<N;i++){
       cin>>A[i];
   }
   \
   //pairwise coprime
   bool f=true;
   set<int> s;
   set<int> s2;
   s.insert(-1);
   for(int i=0;i<N;i++){
       int n=A[i];
       for(int j=0;j<pri.size();j++){
           if(pri[j]==-1) continue;
           if(n%pri[j]==0){
               if(s2.find(pri[j])!=s2.end()){
                   n=-1;
                   break;
               }
               while(n%pri[j]==0) n/=pri[j];
               s2.insert(pri[j]);
           }
       }
       //cout<<n<<endl;
       if(n!=1&&s.find(n)!=s.end()){
           f=false;
           break;
       }
       s.insert(n);
   }
   if(f){
       cout<<"pairwise coprime"<<endl;
       return 0;
   }
   int g=A[0];
   for(int i=1;i<N;i++){
       g=gcd(g,A[i]);
   }
   if(g==1){
       cout<<"setwise coprime"<<endl;
       return 0;
   }
   cout<<"not coprime"<<endl;
}

・F　I hate Shortest Path Problem

O(HW)から縮められなかったです。
AiBiの入力からスタート地点を絞るのかな～と考えていましたが、上手い案が思い浮かびませんでした。

・最後に

F問題が解きたい！！
あと、Union-Findを探すのに時間がかかったのでライブラリ整備も進めたいです。

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

競プロ参加日記008 AtCoder Beginner Contest 177 参加(ABC177)

・はじめに

・A問題 Don't be late

・B問題 Substring

・C Sum of product of pairs

・D Friends

・E Coprime

・F I hate Shortest Path Problem