競プロ参加日記010 Codeforces Round #668 (Div. 2)

ぬるから

ぬるからです。
二回目のcodeforces参加となりました。

・はじめに

3完で1355位でした。
レートが上がった(603->1011)ので、まずは良しとしたいです。

・A. Permutation Forgery

各Aiを並び替えて、隣り合った要素を足してできた数をソートしてできた配列を元と同じようにする問題。
ちょっとややこしそうですが、配列を逆順にすれば隣り合う要素を変えずに配列を変えられます。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.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 Blong long = mp::cpp_long long;
*/
using namespace std;
#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 main(){
   int t;
   cin>>t;
   for(int i=0;i<t;i++){
       int n;
       cin>>n;
       int ans[n];
       for(int j=0;j<n;j++){
           int a;
           cin>>a;
           ans[n-j-1]=a;
       }
       for(int j=0;j<n;j++){
           cout<<ans[j];
           if(j==n-1) cout<<endl;
           else cout<<" ";
       }
       /*for(int j=1;j<n;j++){
           cout<<ans[j]+ans[j-1];
           if(j==n-1) cout<<endl;
           else cout<<" ";
       }*/
   }
}

・B. Array Cancellation

iとjを任意に選んで、aiを1減らしてajを1増やして配列の全要素を0にする。このとき、j<iならコストが1かかるので、なるたけコストを最小にする問題。
コスト0でどれだけ減らせるかを考える。前からみて行って、プラスの値の和を取っていき、マイナスが来たらなるたけ減らす。
幾つかプラスやマイナスが残るが、それがコスト1かけて減らさないといけない分になる。(マイナスの値の前にあるプラスの値では、どうしようもない値)

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.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 Blong long = mp::cpp_long long;
*/
using namespace std;
#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 main(){
   long long t;
   cin>>t;
   for(long long i=0;i<t;i++){
       long long n;
       cin>>n;
       long long plus=0;
       long long nokori=0;
       for(long long j=0;j<n;j++){
           long long a;
           cin>>a;
           if(a>0) {
               plus+=a;
           }
           else{
               a=abs(a);
               if(a>plus){
                   nokori+=a-plus;
                   plus=0;
               }
               else{
                   plus-=a;
               }
           }
       }
       cout<<nokori<<endl;
   }
}

・C. Balanced Bitstring

0,1,?で構成されたbit列がある。?に0or1を入れたとき、k文字の部分文字列に出現する0と1の数が同じになるか求めよ。
N=20、k=6で題意に合うbit列を列挙すると
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0
0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0
0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0
0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1
0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1
0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1
0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1
1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0
1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0
1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0
1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0
1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1
1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1
1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1
となる。眺めていると、長さk=6でbit列がループしているため、題意を満たす文字列はそんな感じっぽさそうに感じる。
実験結果を信じて実装。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.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 Blong long = mp::cpp_long long;
*/
using namespace std;
#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
void test(){
   int N=20;
   for(int i=0;i<pow(2,N);i++){
       int n=i;
       int c=N;
       int a[N];
       int k=6;
       while(c--){
           a[c]=n%2;
           n/=2;
       }
       int z=0;
       int o=0;
       for(int j=0;j<k;j++){
           if(a[j]==0) z++;
           else o++;
       }
       if(o!=z) continue;
       for(int j=k;j<N;j++){
           if(a[j]==0) z++;
           else o++;
           if(a[j-k]==0) z--;
           else o--;
           if(o!=z) break;;
       }
       if(o!=z) continue;
       for(int j=0;j<N;j++){
           cout<<a[j]<<" ";
       }
       cout<<endl;
   }
}
int main(){
   long long t;
   //test();
   cin>>t;
   for(long long i=0;i<t;i++){
       int n,k;
       cin>>n>>k;
       string s;
       cin>>s;
       int c[k];
       bool f=true;
       for(int j=0;j<n;j++){
           if(j<k) c[j]=0;
           if(s[j]=='0'){
               if(c[j%k]==2){
                   f=false;
                   break;
               }
               c[j%k]=1;
           }
           else if(s[j]=='1'){
               if(c[j%k]==1){
                   f=false;
                   break;
               }
               c[j%k]=2;
           }
       }
       if(f) {
           int zc=0,oc=0;
           for(int j=0;j<k;j++){
               if(c[j]==1) zc++;
               if(c[j]==2) oc++;
           }
           //cout<<zc<<","<<oc<<endl;
           if(zc>k/2||oc>k/2) cout<<"NO"<<endl;
           else cout<<"YES"<<endl;
       }
       else cout<<"NO"<<endl;
   }
}

test()が実験用のコードになります。

・D. Tree Tag

頂点数nの木にAliceとBobがいる。Aliceは初期aにいて距離daまで動ける。Bobは初期bにいて距離dbまで動ける。Aliceから交互に動き、10^100ターン後までに、AliceがBobと同じ頂点にいればAliceの勝ち。いなければBobの勝ち。
初手でdaの範囲内にbがあれば、Aliceの勝ちは明白です。
Exampleの二つ目のテストケース
6 6 1 2 5
1 2
6 5
2 3
3 4
4 5
を見てみると、dbがdaより幾分早ければBobが勝ちそうです。直線状の端にBobがいて、Bobのdaマス先にAliceがいる場合、BobはAliceを飛び越えて2*da+1マス先に行かないといけないです。つまり、db<=da*2であればAliceが勝てます。
Exampleの一つ目のテストケース
4
4 3 2 1 2
1 2
1 3
1 4
を見てみると、仮にdb=1000000000だったとしても、Aliceが勝ちそうです。これは、木の直径(頂点間の距離の最大)がda*2以下なので、BobがAliceの移動範囲外に出る前に端にぶつかるからです。つまり、直径<=da*2であればAliceが勝てます。
上記3つの条件を確かめることで解が得られます。
なお、直径は1回適当にダイクストラをやって出た最大距離の頂点から、再びダイクストラをした時の最大の距離となります。
※任意の頂点からの最大距離は必ず、直径の端の頂点を結ぶそうです。
　https://algo-logic.info/tree-diameter/

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>
/*
#include<boost/multiprecision/cpp_long long.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 Blong long = mp::cpp_long long;
*/
using namespace std;
#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 main(){
   int t;
   cin>>t;
   for(int i=0;i<t;i++){
       int n,a,b,da,db;
       cin>>n>>a>>b>>da>>db;
       vector<int> e[n+1],l;
       for(int i=0;i<n-1;i++){
           int u,v;
           cin>>u>>v;
           e[u].push_back(v);
           e[v].push_back(u);
           l.push_back(-1);
       }
       l.push_back(-1);
       l.push_back(-1);
       l.push_back(-1);
       for(int p=0;p<2;p++){
           queue<int> q,q2;
           if(p==0){
               q.push(a);
               q2.push(0);
           }
           else{
               int mxi=1;
               int mx=l[1];
               l[1]=-1;
               for(int j=2;j<=n;j++){
                   if(mx<l[j]){
                       mx=l[j];
                       mxi=j;
                   }
                   l[j]=-1;
               }
               q.push(mxi);
               q2.push(0);
           }
           while(!q.empty()){
               int qn=q.front();
               q.pop();
               int nn=q2.front();
               q2.pop();
               l[qn]=nn;
               for(int j=0;j<(int)e[qn].size();j++){
                   if(l[e[qn][j]]==-1){
                       q.push(e[qn][j]);
                       q2.push(nn+1);
                   }
               }
           }
           /*for(int i=1;i<=n;i++){
               cout<<l[i]<<",";
           }
           cout<<endl;*/
           if(p==0&&l[b]<=da){
               cout<<"Alice"<<endl;
               da=-10;
               break;
           }
       }
       int mxi=1;
       int mx=l[1];
       for(int j=2;j<=n;j++){
           if(mx<l[j]){
               mx=l[j];
               mxi=j;
           }
       }
       if(da==-10) continue;
       if(mx<=da*2||db<=da*2) cout<<"Alice"<<endl;
       else cout<<"Bob"<<endl;
   }
}

・E. Fixed Point Removal

まだ解けてません！！
本当は解いてから書きたかったけど、徹夜しても無理でした。
解法をTwitter等で見ましたが、セグ木に二分探索でごにょごにょするとか。
まだ見えてないので、自分のセグ木をもう少し育てたら挑戦します。

・おわりに

今週はDPをやりたかった
(ABC029-Dの桁DPに苦戦したため)
のですが、ABC177-Fや今回のEを解くために、もう少しセグ木を育てていこうかと思います。
Twitterを見てると
https://judge.yosupo.jp/
Library Checkerなる良さそうなサイトがあったので、ここでセグ木の素振りをしていこうかなぁと思います。

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