競プロ参加日記012 Codeforces Round #670 (Div. 2)
・はじめに
A,Bの2完でした。
レートは1377まで上がりました。次回、入水しそうですね。
・A. Subset Mex
配列aを2つのグループA,Bに分ける。mex(A)+mex(B)を最大化せよ。
ただし、mexとはグループの中に存在しない、0以上の整数の中で最も小さいものとなる。
0,1,2,3...と連続して入れれば入れるほど大きくなります。
配列aの各数字の出現回数をカウントし、0から線形探索し、カウント0の最小値をansに加えることを二回やれば良いです。
ただ、二回目はカウント1以下の最小値にするとか、一回目の探索でカウントを減らすとかする必要があります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
int ac[1000]={0};
cin>>n;
for(int j=0;j<n;j++){
int a;
cin>>a;
ac[a]++;
}
int ans=0;
int idx=0;
while(ac[idx]!=0){
ac[idx]--;
idx++;
}
ans+=idx;
idx=0;
while(ac[idx]!=0){
ac[idx]--;
idx++;
}
ans+=idx;
cout<<ans<<endl;
}
}・B. Maximum Product
配列から選んだ5つの数字(重複なし)の積を最大化する問題。
場合分けがしんどそうなので、正の数を0～5個選ぶ場合の6パターン試し最大値取りました。こうした場合、場合分けは以下のようになり幾分か楽です(多分)。
正の数の個数+負の数の個数が5個未満の場合は答え0 (0を含まなければいけない)
→探索値の初期値は0がある場合は0、ない場合は-INF
→正の数を0～5個選ぶパターンを探す。
正の数が選びたい数ない場合は探索しない。
ある場合は、正の数が偶数なら絶対値を小さくするよう選ぶ(答えがマイナス)。正の数が奇数なら絶対値を大きくするよう選ぶ(答えがプラス)。
探索値より大きければ更新する。
探索値が答え。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long t;
cin>>t;
for(long long i=0;i<t;i++){
long long n;
multiset<long long> sp,sm;
cin>>n;
for(long long i=0;i<n;i++){
long long in;
cin>>in;
if(in>0) sp.insert(in);
if(in<0) sm.insert(in);
}
if((long long)sp.size()+(long long)sm.size()<5){
cout<<"0"<<endl;
continue;
}
long long ans=LLONG_MIN;
if((long long)sp.size()+(long long)sm.size()!=n){
ans=0;
}
//cout<<ans<<endl;
for(long long j=0;j<=5;j++){
long long pc=j;
long long mc=5-j;
long long c=1;
if((long long)sp.size()<pc||(long long)sm.size()<mc) continue;
if(mc%2==0){
multiset<long long>::reverse_iterator it=sp.rbegin();
for(long long k=0;k<pc;k++){
c*=*it;
it++;
}
multiset<long long>::iterator it2=sm.begin();
for(long long k=0;k<mc;k++){
c*=*it2;
it2++;
}
}
else{
multiset<long long>::iterator it=sp.begin();
for(long long k=0;k<pc;k++){
c*=*it;
it++;
}
multiset<long long>::reverse_iterator it2=sm.rbegin();
for(long long k=0;k<mc;k++){
c*=*it2;
it2++;
}
}
//cout<<pc<<","<<mc<<","<<c<<endl;
ans=max(ans,c);
}
cout<<ans<<endl;
}
}・C. Link Cut Centroids
Centroids=重心(多分)で、題名の通り木の重心に関する問題。
辺を一つ消して、一つ追加することによって重心を一つにする。
重心が一つの時は、適当な辺を消して復活させれば良いです。
細かい説明は省きますが、重心は1,2個のどちらかになります。また、二個ある場合は重心同士は辺でつながっています。さらに、その繋がっている辺を切ることでサイズがN/2で二分割されます。
そのため、二分割される片方の頂点集合から、適当な辺を削除して二分割し(A.重心を持つN/2の木,B.重心を持つN/2より小さい木,C.重心を持たない木)の3つにし、Cの頂点から->Aの頂点に辺を伸ばすと、N/2で二分割できなくなり重心が一つになります。
木の重心は、再帰的にみて行くことで求まります。
(適当な頂点から探って、葉か全ての辺を探索し終えたらサイズを返すようにしてやると、ある頂点が伸ばしている辺の先に幾つの頂点がぶら下がっているか分かる。重心はそれが全てN/2以下になるので、重心が判明する。)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
vector<vector<int>> v;
vector<int> ans;
int Centroids(int n,int bef,int N){
//cout<<n<<","<<bef<<","<<N<<endl;
bool flag=true;
int s=1;
for(int i=0;i<v[n].size();i++){
int t=v[n][i];
if(bef==t) continue;
int egs=Centroids(t,n,N);
if(egs>N/2) flag=false;
s+=egs;
}
if(N-s>N/2) flag=false;
if(flag) {
ans.push_back(n);
}
return s;
}
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
v.clear();
ans.clear();
for(int j=0;j<=n;j++){
vector<int> vtmp;
v.push_back(vtmp);
}
for(int j=0;j<n-1;j++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
Centroids(1,INT_MAX,n);
/*cout<<ans.size()<<endl;
for(int j=0;j<ans.size();j++){
cout<<ans[j]<<" ";
}
cout<<endl;*/
if(ans.size()==1){
cout<<"1 "<<v[1][0]<<endl;
cout<<v[1][0]<<" 1"<<endl;
}
else{
int ed=ans[0];
for(int i=0;i<v[ed].size();i++){
int t=v[ed][i];
if(t!=ans[1]){
cout<<t<<" "<<ans[0]<<endl;
cout<<t<<" "<<ans[1]<<endl;
break;
}
}
}
}
}実は重心という概念を始めて知りました。前のCodeForcesの直径のように、グラフの用語は一度整理したいですね。
・D. Three Sequences
ai=bi+ciとしたときの各iのmax(bi,ci)が最小になるようにする。また、biはbi-1以上で、ciはci-1以下でないといけない。
クエリ抜きで、最小がいくつになるかを考えます。
4:2 -1 7 3
の場合、b0=0とすると以下のようになりそうです。
b:0 0 8 8
c:2 -1 -1 -5
書いてみると分かるのですが、ai+1がaiより大きい場合、ci+1は増やせないため、bi+1を大きくするしかありません。
逆に減らす方にも言えるので、biの最大値は初期値+各iの(ai+1)と(ai)の差が正の時の和(bsumとする)となりそうです。(biの初期値から増える分を足した値)
なので、biをうんと小さくすれば答えも小さくなるようですが、ciが大きくなります。
a0=4の時、b0=0ならc0=4ですが、b0=-100ならc0=104となり、答えが大きくなります。この辺りの塩梅を上手くする必要があります。
この塩梅はb,cについて纏めるとO(1)で分かったりします。
・bはb0+aiとbsumの和が最大
・cはc0が最大(cはこれ以上増えない)
・b0をx減らすと、c0はx増える
b0=a0-c0と考えると
bの最大はa0- c0+bsum-x
cの最大は c0 +x
となります。xを傾きとしてグラフを考えた場合、bとcの線は×のようになり、maxの最小は×の真ん中の交点になります。
また、この交点は傾きの絶対値が等しいため、b+cの平均=(a0+bsum)/2となります。(小数となる場合の切り上げ切り捨てに注意です。)
クエリの区間更新について考えたいのですが、上記求めた式により答えに関係するのはa0とbsumです。
なので、クエリの範囲にa0がある場合は更新が必要です。
0 0 0 0 0 0 0 0
の2,4区間に1を加えたとき
0 1 1 1 0 0 0 0
となります。それぞれのbsumを計算すると分かるのですが、区間の端と端しか差が変わりません。(区間の中は、両方の数字が増減するため差に影響はない)
そのため、bsumは区間の両方しか影響がなく、2点を見て更新すれば良いです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N;
cin>>N;
long long a[N+1];
long long diff[N+1];
long long ps=0;
for(long long i=1;i<=N;i++){
cin>>a[i];
if(i>=2){
diff[i-1]=a[i]-a[i-1];
if(diff[i-1]>0) ps+=diff[i-1];
}
//cout<<ps<<endl;
}
long long sum=ps+a[1];
cout<<sum/2+(sum%2==1)<<endl;
long long q;
cin>>q;
for(long long i=0;i<q;i++){
long long l,r,x;
cin>>l>>r>>x;
if(l==1) a[1]+=x;
if(l!=1){
if(diff[l-1]>0) ps-=diff[l-1];
diff[l-1]+=x;
if(diff[l-1]>0) ps+=diff[l-1];
}
if(r!=N){
if(diff[r]>0) ps-=diff[r];
diff[r]-=x;
if(diff[r]>0) ps+=diff[r];
}
long long sum=ps+a[1];
cout<<sum/2+(sum%2==1)<<endl;
}
}区間更新->遅延セグ木
最大の最小->二分探索
と思って、方針を固めたのが失敗でした。正しい方針に気付いたのが、コンテスト終了3分前とかでした。
この辺り、上手くやりたいですね。
・おわりに
解説が上手く書ける人、すごい！！ってなっています。
何度かこのnoteに載せているセグ木の方とか、とても分かりやすいですよね。
noteを書くことによって、こういった力も付けばなぁと考えています。