beet's soil

競プロのことなど

Codeforces Round #402 (Div. 2)

どふぉどふぉw

【A. Pupils Redistribution】

2で割り切れなかったら-1、そうじゃなかったら全体の差分/2。
indexに気をつけてはい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  int c[2][5]={};
  for(int i=0;i<n;i++) c[0][a[i]-1]++;
  for(int i=0;i<n;i++) c[1][b[i]-1]++;
  int ans=0;
  for(int i=0;i<5;i++){
    if((c[0][i]+c[1][i])%2){
      cout<<-1<<endl;
      return 0;
    }
    ans+=abs(c[0][i]-(c[0][i]+c[1][i])/2);
  }
  cout<<ans/2<<endl;
  return 0;
}
【B. Weird Rounding】

0が足りなかったら文字列長-1、そうじゃなかったら後ろから貪欲。
0が一個もない文字列は与えられない(制約に書いてあるので。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string s;
  int k;
  cin>>s>>k;
  reverse(s.begin(),s.end());
  int t=0,ans=0;
  for(int i=0;i<(int)s.size();i++){
    ans+=s[i]!='0';
    t+=s[i]=='0';
    if(t==k) break;
  }
  if(t<k) cout<<s.size()-1<<endl;
  else cout<<ans<<endl;
  return 0;
}
【C. Dishonest Sellers】

とりあえず全部Aを買って差分をpriority_queueに突っ込んでn-k個以下入れ替える。
こういうのよくあるよね〜って感じではい。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  int a[n],b[n];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  int ans=0;
  priority_queue<int> q;
  for(int i=0;i<n;i++){
    q.push(a[i]-b[i]);
    ans+=a[i];
  }
  for(int i=0;i<n-k;i++){
    int p=q.top();q.pop();
    if(p<=0) break;
    ans-=p;
  }
  cout<<ans<<endl;
  return 0;
}
【D. String Game】

ある場所まで構築できるならそこより前でも構築できる。
一回のチェックは線形でできるので後ろから見て二分探索。
別に前からでもよかった(ア。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string t,p;
  cin>>t>>p;
  int n=t.length(),q=p.length();
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  reverse(a,a+n);
  int l=0,r=n;
  while(l+1<r){
    int b[n];
    memset(b,0,sizeof(b));
    int m=(l+r)/2;
    for(int i=0;i<m;i++) b[a[i]-1]=1;
    int pos=0;
    for(int i=0;i<n;i++){
      if(b[i]&&pos<q&&t[i]==p[pos]) pos++; 
    }
    if(pos==q) r=m;
    else l=m;
  }
  cout<<n-r<<endl;
  return 0;
}
【E. Bitwise Formula】

XORの交換法則とか色々考えたけどそもそもAND,OR,XORだけなら他のビットに影響しない。
ビットごとに独立なのでそれぞれ01を試して大きい方を選ぶ。同じなら0。
2.9secで危なかった。通ったのでセーフ。
":="を読み飛ばすの忘れて焦ったのは内緒。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m;
  cin>>n>>m;
  string s[n],v[n],a[n],o[n],b[n];
  bool t[n];
  string buf;
  for(int i=0;i<n;i++){
    cin>>s[i];
    cin>>buf;
    cin>>buf;
    t[i]=isdigit(buf[0]);
    if(t[i]) v[i]=buf;
    else{
      a[i]=buf;
      cin>>o[i]>>b[i];
    }
  }
  /*
  for(int i=0;i<n;i++){
    cout<<s[i]<<" ";
    if(t[i]) cout<<v[i]<<" ";
    else cout<<a[i]<<" "<<o[i]<<" "<<b[i];
    cout<<endl;
  }
  */
  map<string,int> ms;
  for(int i=0;i<n;i++) ms[s[i]]=i;
  ms["?"]=n;
  
  string ans,ans2;
  for(int i=0;i<m;i++){
    int tmp[2]={};
    int res[n+1];
    memset(res,0,sizeof(res));
    for(int k=0;k<2;k++){
      res[n]=k;
      for(int j=0;j<n;j++){
	if(t[j]){
	  res[j]=v[j][i]-'0';
	  continue;
	}
	int ba=res[ms[a[j]]],bb=res[ms[b[j]]];
	//cout<<j<<":"<<ba<<" "<<bb<<endl;
	if(o[j]=="AND") res[j]=ba&bb;
	if(o[j]=="OR" ) res[j]=ba|bb;
	if(o[j]=="XOR") res[j]=ba^bb;
      }
      for(int j=0;j<n;j++) tmp[k]+=res[j];
    }
    //cout<<tmp[0]<<" "<<tmp[1]<<endl;
    if(tmp[0]<=tmp[1]) ans+='0';
    else ans+='1';
    if(tmp[0]>=tmp[1]) ans2+='0';
    else ans2+='1';
  }
  cout<<ans<<endl<<ans2<<endl;
  return 0;
}
【全体】

ooooo- 4714pts 65th
1829 -> 1914 (+85) highest!!
初candidate master、うれしい。
大体ad-hocだったので得意セットだった。Fは知らん(知らないので)。
こんなん笑うやろというグラフになった。ガヴドロはいいぞ。
f:id:beet_aizu:20170227120419p:plain