ABC148 参加記録

atcoder.jp 1679->1673(-6) 厳しいですね

C. Snack

を求めればよいです。より、です。はC++であれば__gcd(組み込み関数?)を使って求められます。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

Lint lcm(int a,int b)
{
   return (Lint)a*b/__gcd(a,b);
}

int main()
{
   int a,b; cin>>a>>b;
   cout<<lcm(a,b)<<endl;
   return 0;
}

D. Brick Break

消す個数の最小値を求める代わりに、残す個数の最大値を求めることにします。そうすると求めるものは、「に部分列として含まれる、というような列のうち、長さが最大のものの長さ」です。要するに、左から順番にと選んでいったとき、最大でいくつ選べるかということです。これは、次の数を選べる範囲でもっとも左から選ぶことを繰り返せばよいです。なぜならば、最も左にあるものをとしたとき、を選ばないような最適解が存在するならば、を選ぶような最適解も存在するからです。直感的には、もっとも左にあるものを選んで損をすることはないからです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   int cur=0;
   for(int i=0;i<N;i++){
      if(a[i]==cur+1) cur++;
   }
   cout<<(cur==0? -1:N-cur)<<endl;
   return 0;
}

コンテスト中はDPを書きました。

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   if(count(a.begin(),a.end(),1)==0){
      cout<<-1<<endl;
      return 0;
   }

   const int MAX=*max_element(a.begin(),a.end());
   vector<bool> dp(MAX+1);
   // dp[i]:=(今見ているところまでで)1,2,...iを部分列として含んでいるか
   dp[0]=true;
   for(int i=0;i<N;i++){
      if(dp[a[i]-1]) dp[a[i]]=true;
   }
   int ans=0;
   for(int i=1;i<=MAX;i++) if(dp[i]) ans=i;
   cout<<N-ans<<endl;
   return 0;
}

E. Double Factorial

まず末尾のの個数というのは、を因数としていくつ持つかということです。因数のの個数はなので、これを数えればよいです。が素因数をいくつ持つかは以下の式で計算できます。

が持つ素因数の個数は

これはこの問題の解説動画で見た記憶があります。
もとの問題に戻ります。の偶奇で場合分けをします。

• が奇数の場合
  の個数がなので答えはです。
• が偶数の場合
  の個数はの場合と同じです(奇数はで割れないので、無くても変わらない)。の個数については、をで何度か割ることによっての場合に帰着できるので求まります。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

Lint calc(Lint N,Lint p)
{
   // N!が素因数pをいくつ含むか
   Lint res=0;
   while(N/p>0){ res+=N/p; N/=p; }
   return res;
}

Lint func(Lint N)
{
   if(N<=1) return 0;
   if(N%2==1) return 0;
   else{ return min(calc(N,2),calc(N/2,5)); }
}

int main()
{
   Lint N; cin>>N;
   cout<<func(N)<<endl;
   return 0;
}

上の実装ではをで割った結果と、をで回割った結果が等しいことを利用しています。これは進法で考えると分かります(前者が個右シフトしていて、後者は個の右シフトを回しているため)。実際にを計算してオーバーフローしたことがあるので、こうしています。

F. Playing Tag on Tree

めっちゃ解かれているのでおそらくdfsするだけでいいんだろうなぁと思いました(最悪)。直感的には追いつかれないところで一番遠いところに逃げるのが最適だろうと分かりますが、、、

#include<bits/stdc++.h>
using namespace std;

using Graph=vector<vector<int>>;

int main()
{
   int N,T,A; cin>>N>>T>>A;
   T--; A--;
   Graph G(N);
   for(int i=0;i<N-1;i++){
      int a,b; cin>>a>>b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
   }
   vector<int> dist(N);
   function<void(int,int)> dfs=[&](int v,int p)
   {
      for(int u:G[v]) if(u!=p){
         dist[u]=dist[v]+1;
         dfs(u,v);
      }
   };

   vector<int> distT(N);
   dist[T]=0; dfs(T,-1); distT=dist;
   vector<int> distA(N);
   dist[A]=0; dfs(A,-1); distA=dist;
   int ans=-1;
   for(int i=0;i<N;i++) if(distT[i]<distA[i]){
      ans=max(ans,distA[i]-1);
   }
   cout<<ans<<endl;
   return 0;
}

感想

ちゃんと理解したら別の記事に書こうと思います。今回はみんな速すぎてビックリしました。