競プロ参加日記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なる良さそうなサイトがあったので、ここでセグ木の素振りをしていこうかなぁと思います。