読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

CODE FESTIVAL 2016 qual B

学園祭で二日間働いた後満身創痍で出ました。最後の方テンションおかしかった。

【A - Signboard】
元の文字列と違うところの数を数える。

#include<bits/stdc++.h>
using namespace std;
int main(){
  string b="CODEFESTIVAL2016",s;
  int i,ans=0;
  cin>>s;
  for(i=0;i<16;i++) if(b[i]!=s[i]) ans++;
  cout << ans << endl;
  return 0;
}

【B - Qualification simulator】
カウンタを二つ持って日本なら片方海外なら両方を使って判定と加算をする。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,i,j,k;
  string s;
  cin>>n>>a>>b>>s;
  int x=0,y=0;
  for(i=0;i<n;i++){
    if(s[i]=='a') {
      if(x<a+b){
	x++;
	cout << "Yes" << endl;
      }else cout << "No" << endl;
    }
    if(s[i]=='b') {
      if(x<a+b&&y<b){
	x++;
	y++;
	cout << "Yes" << endl;
      }else cout << "No" << endl;
    }
    if(s[i]=='c') {
      cout << "No" << endl;
    }
  }
  return 0;
}

【C - Gr-idian MST】
最初プリムやるだけだと思ってw*hの配列を持とうとした(脳死)。
辺のコストが小さい方から繋ぐだけなら数がいっぱいあっても変わらないことに気づいておしまい。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
  ll w,h;cin>>w>>h;
  ll i,j,k;
  ll p[w],q[h];
  priority_queue<P,vector<P>,greater<P> > qu;
  ll ans=0;
  for(i=0;i<w;i++){
    cin>>p[i];
    qu.push(P(p[i],0));
  }
  for(i=0;i<h;i++){
    cin>>q[i];
    qu.push(P(q[i],1));
  }
  while(!qu.empty()){
    P p=qu.top();qu.pop();
    if(p.second){
      ans+=p.first*(w+1);
      h--;
    }else{
      ans+=p.first*(h+1);
      w--;
    }
  }
  cout << ans << endl;
  return 0;
}

この辺で68位とかで勝利を確信していた。

【D - Greedy customers】
範囲の最大値出すならSeg木かな?と思って無限に時間を溶かした。
一回でも買わせられるなら最大値は変化しないことに気づいて貪欲を書くがサンプル1が合わない。
絶望しながらやけくそで条件式に最初だけうにょるのを追加したらACしてびっくりした。
(あとから冷静に考えたら自明だった。つらい。)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;cin>>n;
  ll i,j,k,a[n],ans=0;
  for(i=0;i<n;i++) cin>>a[i];
  k=1;
  for(i=0;i<n;i++){
    j=(a[i]-1)/k;
    if(j<=0){
      k=max(k,a[i]+1);
      continue;
    }
    ans+=j;
    a[i]-=j*k;
    if(a[i]==k&&k==1) k++;
    //cout << i << ":" << k << ":" << ans << endl;
  }
  cout << ans << endl;
  return 0;
}

Eをみて察したのでatcoderjsonをゴリゴリするなどしていた。
A通過者除いて77位だったのですごくもやもやしていた。

【全体】
タイトルがネタバレってことにもっと早く気づければ楽だった。
考察が少し重い分コードが短くて作問者天才かなって感じた。


【結果】
4完189位でなんとか(もしかしたらボーダー)通過しました!
本戦で座ってるだけにならないよう頑張りたいです。