競プロ参加日記017 Codeforces Round #672 (Div. 2)

ぬるから

2020年9月26日 00:35

参加しました。

・結果

A,B,C1,Dの4完でした。
レートもかなり上がり、Atcoderより先に青色になっちゃいましたね...。

・A. Cubes Sorting

配列aの各要素の隣同士を交換して降順にするとき、最低手順がn⋅(n−1)/2-1以下になる場合は"YES"をそうでない場合は"NO"を出力せよ。

かなり適当に説明すると、バブルソートの交換を何回行うかという話です。

上記WIKIに記載のある通り、

「比較回数」は、高々n(n-1)/2回。

となっており、毎比較ごとに交換することを考えると交換回数は最高でn⋅(n−1)/2回です。
つまり、最高回数の比較ケース以外はYESになるといえます。

この最高比較回数になるときは、ソート後の各要素とソート前の各要素の距離が一番遠い=逆順ソートであるときです。
つまり、ai>ai+1の降順ソートであるときにNoになります。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   int t;
   cin>>t;
   while(t-->0){
       int n;
       cin>>n;
       int a,befa;
       cin>>befa;
       bool f=true;
       for(int i=0;i<n-1;i++){
           cin>>a;
           if(befa<=a) f=false;
           befa=a;
       }
       if(f) cout<<"NO"<<endl;
       else cout<<"YES"<<endl;
   }
}

※こういう交換回数のことを『転倒数』というらしいです。

・B. Rock and Lever

ai and aj >= ai xor aj(i<j) となる(i,j)の組み合わせの数を答えよ。

最上位ビットが違う(2進数の桁数が違う)場合、xorだけ最上位ビットが立つため、数えたい不等式が成り立ちません。
そのため、最上位ビットは同じで無ければいけません。この時、最上位ビットのxorは0になるため、最上位より下のビットは何であろうと数えたい不等式を満たします。
なので、与えられた数字から最上位ビットが同じものを数えて、そこから2つを選ぶ組み合わせの数を計算すればよいです。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   int t;
   cin>>t;
   while(t-->0){
       long long n;
       cin>>n;
       long long a[n];
       for(int i=0;i<n;i++){
           cin>>a[i];
       }
       sort(a,a+n);
       long long mn=1,mx=2;
       long long c=0;
       long long ans=0;
       for(int i=0;i<n;i++){
           if(a[i]>=mn&&a[i]<mx){
               c++;
           }
           else{
               if(c>=2) ans+=c*(c-1)/2;
               c=0;
               mn*=2;
               mx*=2;
               i--;
           }
       }
       if(c>=2) ans+=c*(c-1)/2;
       //cout<<"-----";
       cout<<ans<<endl;
   }
}

・C1. Pokémon Army (easy version)

著作権的に大丈夫？？？？
配列aから任意個数選び、配列bとします。
このとき、b1-b2+b3-b4...のように足し引きを交互に行った時の和を最大化する。

ex.1 2 5 4 3 6 7
1 5 3 7を選んだ場合、1-5+3-7=-8
(最大は、5 3 7と選んで5-3+7=9)

次に選ぶ数字を正として迎え入れるか、負として迎え入れるかの2通りを状態に持ちながらDPすればいいです。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
   int t;
   cin>>t;
   while(t-->0){
       long long n,q;
       cin>>n>>q;
       long long a[n];
       for(int i=0;i<n;i++){
           cin>>a[i];
       }
       long long dp[n+2][2];
       for(int i=0;i<=n;i++){
           for(int j=0;j<2;j++){
               dp[i][j]=-1;
           }
       }
       dp[0][0]=0;
       for(int i=1;i<=n;i++){
           for(int j=0;j<2;j++){
               if(dp[i-1][j]!=-1){
                   dp[i][j]=max(dp[i-1][j],dp[i][j]);
                   if(j==0) dp[i][1]=max(dp[i-1][j]+a[i-1],dp[i][1]);
                   else dp[i][0]=max(dp[i-1][j]-a[i-1],dp[i][0]);
               }
           }
       }
       /*for(int i=0;i<=n;i++){
           for(int j=0;j<2;j++){
               cout<<dp[i][j]<<" ";
           }
           cout<<endl;
       }*/
       cout<<max(dp[n][0],dp[n][1])<<endl;
   }
}

・C2. Pokémon Army (hard version)

C1に加えて、q個のクエリが渡されalとarの要素が交換されます。毎クエリごとのbの和の最大を求めよ。

毎スワップごとにDPしてはO(NQ)になるためTLEです。
コンテスト後にTwitterで解法を見たのですが、セグ木を用いることで解けるようです。

具体的には、+で始まって+で終わる区間の和、+で始まって-で終わる区間の和、-で始まって+で終わる区間の和、-で始まって-で終わる区間の和の4通りを状態に持ちます。
+～+区間に-～+区間を足すか、+～-区間に+～+区間を足すことによって、新たな+～+区間を作れます。(+-+-...-+ に-+-+...+-+を足すことで、+-+-...-+-+-+...+-+と長い+～+区間になる)
こういった区間の更新を行うことで、問題の題意を満たす答えがセグ木で求まります。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//0-index
struct S{
   long long p_p,m_m,p_m,m_p;
};
vector<S> seqv;
long long seqv_n;
void seg_init(long long N){
  seqv.clear();
  long long n=1;
  while(n<N) n*=2;
  seqv_n=n-1;
  n*=2;
  n=n-1;
  for(long long i=0;i<n;i++){
      S tmps;
      tmps.m_m=0;
      tmps.p_m=0;
      tmps.m_p=0;
      tmps.p_p=0;
      seqv.push_back(tmps);
  }
}
void seg_update(long long n,long long a){
  long long k=n+seqv_n;
  S tmps;
  tmps.m_m=-a;
  tmps.p_m=0;
  tmps.m_p=0;
  tmps.p_p=a;
  seqv[k]=tmps;
  while(k>0){
      k=(k-1)/2;
      long long m_mp_m=seqv[k*2+1].m_m+seqv[k*2+2].p_m;
      long long m_mp_p=seqv[k*2+1].m_m+seqv[k*2+2].p_p;
      long long m_pm_m=seqv[k*2+1].m_p+seqv[k*2+2].m_m;
      long long m_pm_p=seqv[k*2+1].m_p+seqv[k*2+2].m_p;
      long long p_mp_m=seqv[k*2+1].p_m+seqv[k*2+2].p_m;
      long long p_mp_p=seqv[k*2+1].p_m+seqv[k*2+2].p_p;
      long long p_pm_m=seqv[k*2+1].p_p+seqv[k*2+2].m_m;
      long long p_pm_p=seqv[k*2+1].p_p+seqv[k*2+2].m_p;
      seqv[k].m_m=max(m_mp_m,m_pm_m);
      seqv[k].m_p=max(m_mp_p,m_pm_p);
      seqv[k].p_m=max(p_mp_m,p_pm_m);
      seqv[k].p_p=max(p_mp_p,p_pm_p);
  }
}
long long seg_find(){
  return seqv[0].p_p;
}
int main(){
   long long t;
   scanf("%lld",&t);
   while(t-->0){
       long long n,q;
       scanf("%lld %lld",&n,&q);
       seg_init(n);
       long long a[n];
       for(long long i=0;i<n;i++){
           cin>>a[i];
           seg_update(i,a[i]);
       }
       printf("%lld\n",seg_find());
       for(int i=0;i<q;i++){
           int l,r;
           scanf("%d %d",&l,&r);
           l--,r--;
           swap(a[l],a[r]);
           seg_update(l,a[l]);
           seg_update(r,a[r]);
           printf("%lld\n",seg_find());
       }
   }
}

※i番目の葉に入れる値は+～+区間にai、-～-区間に-aiを入れます。
　要素が一つしかないので、-と+が混在する区間はあり得ないため0を入れます。(足していくため、計算に影響のない値)
※cin,coutだとTLEするため、scanf,printfを使っています。

・D. Rescue Nibel!

k個選んだ時に、l～r区間のどこかがk個重なっているような区間の組み合わせは何通りあるか。mod 998244353 で答えよ。

この手の問題は、lやrでソートすると上手くいきます。
ex.Sample 1をlでソートする
　1 7
　1 3
　3 8 →前二つのrが3と7なので3つとも重なりそう
　4 5 →1 3のrが3なので重ならないが、1 7や3 8は重なる
　5 10 →...
　6 7
　8 9
といったように、rを管理していけば今見ているlの位置と重なるかが分かりそうです。
このとき、今見ている区間と、重なるrを持つ区間k-1個の合わせてk個を選ぶ通りが組み合わせの個数になるため、(重なるr区間の個数)C(k-1)でコンビネーションを計算すればOKです。

なお、コンビネーションの計算に割り算があるため、そのままだとMODの計算で異常な値になります。
フェルマーの小定理などから割り算を掛け算等に変換する必要があります。

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-%E5%89%B2%E3%82%8A%E7%AE%97-a--b
const long long MAX = 310000;
const long long MOD = 998244353 ;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
   fac[0] = fac[1] = 1;
   finv[0] = finv[1] = 1;
   inv[1] = 1;
   for (long long i = 2; i < MAX; i++){
       fac[i] = fac[i - 1] * i % MOD;
       inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
       finv[i] = finv[i - 1] * inv[i] % MOD;
   }
}
long long COM(long long n, long long k){
   if (n < k) return 0;
   if (n < 0 || k < 0) return 0;
   return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(){
   long long n,k;
   cin>>n>>k;
   vector<pair<long long,long long>> v;
   COMinit();
   for(long long i=0;i<n;i++){
       long long l,r;
       cin>>l>>r;
       pair<long long,long long> p;
       p.first=l;
       p.second=r;
       v.push_back(p);
   }
   sort(v.begin(),v.end());
   multiset<long long> rs;
   long long ans=0;
   if(k==1){
       cout<<n<<endl;
       return 0;
   }
   for(long long i=0;i<n;i++){
       long long vr=v[i].second;
       long long vl=v[i].first;
       //cout<<vl<<","<<vr<<endl;
       if(i==0) rs.insert(vr);
       else{
           set<long long>::iterator ub=rs.upper_bound(vl-1);
           set<long long>::iterator it=rs.begin();
           while(it!=ub) it=rs.erase(it);
           long long num=rs.size();
           //cout<<num<<endl;
           if(num>=k-1){
               ans+=COM(num,k-1);
           }
           ans%=MOD;
           rs.insert(vr);
       }
   }
   cout<<ans%MOD<<endl;
}

※https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-%E5%89%B2%E3%82%8A%E7%AE%97-a--b
　「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜　からコンビネーションのMOD計算のアルゴリズムをコピーしました。

・おわりに

Atcoder的にはCodeforcesと色の難易度が同じになるよう調整しているらしいですが...。codeforcesの方が簡単に思えます。
よっぽどAtcoderの問題が苦手なようです。

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