beet's soil

競プロのことなど

CODE FESTIVAL 2016 qual C

イノシシのせいで電車が遅れたりしたけどギリギリ間に合ったので出た


【A - CF】
Cの後にFが出て来ればYes、それ以外はNo。
コドフェスはペナルティないからコンパイルしないで出したけど通ってよかった

#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;cin>>s;
  bool c=false,f=false;
  for(int i=0;i<s.size();i++){
    if(s[i]=='C') c=true;
    if(c&&s[i]=='F') f=true;
  }
  if(c&&f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

【B - K個のケーキ / K Cakes】
プライオリティーキューに最初に全部入れて取り出しながら一回使ったものを遅らせて入れる。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
  int k,t,i,j,ans=0;
  cin>>k>>t;
  int a[t];
  P p,b;
  priority_queue<P> q;
  for(i=0;i<t;i++) {
    cin>>a[i];
    q.push(P(a[i],i));
  }
  for(i=0;i<k;i++){
    if(q.empty()) {
      ans++;
      continue;
    }
    p=q.top();q.pop();
    if(b.first) q.push(b);
    a[p.second]--;
    b=P(a[p.second],p.second);
  }
  cout << ans << endl;
  return 0;
}

【C - 二人のアルピニスト / Two Alpinists】
t[l]!=a[r]のところをa[l]!=a[r]にしてしまってつらかった。
左右と真ん中に分けてそれまでの最大値をかけていく。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m=0,i,j,k,ans=1,MOD=1000000007;
  cin>>n;
  ll t[n],a[n];
  for(i=0;i<n;i++) cin>>t[i];
  for(i=0;i<n;i++) cin>>a[i];
  ll l=n-1,r=0;
  for(i=n-1;i>=0;i--){
    if(t[i]==t[l]) l=i;
  }
  for(i=0;i<n;i++){
    if(a[i]==a[r]) r=i;
  }
  //cout << l <<":"<<a[l]<<"/"<<r<<":"<<a[r]<<endl;
  if(r<l) ans*=0;
  if(t[l]!=a[r]) ans*=0;
  else m=a[l];

  k=-1;
  for(i=0;i<l;i++){
    if(k==t[i]) ans=(ans*k)%MOD;
    k=t[i];
  }
  for(i=l+1;i<r;i++){
    ans=(ans*m)%MOD;
  }
  k=-1;
  for(i=n-1;i>r;i--){
    if(k==a[i]) ans=(ans*k)%MOD;
    k=a[i];
  }
  cout << ans%MOD << endl;
  return 0;
}

【D - Friction】
800だし無理かなと思ったけど部分点があったのでやった。
最初グローバル変数の上限10^7個ぐらいまでだと思っていて嘘貪欲投げたりしてもったいなかった。
計算量の見積もりをしっかりせねば。

#include<bits/stdc++.h>
using namespace std;
int dp[305][305][305];
int main(){
  int h,w,i,j,k,l;
  cin>>h>>w;
  if(w!=3) return 0;
  char c[w][h];
  for(i=h;i>0;i--){
    for(j=0;j<w;j++){
      cin>>c[j][i-1];
    }
  }
  int co[2][350][350]={};
  for(i=0;i<w-1;i++){
    for(j=0;j<=h;j++){
      for(k=0;k<=h;k++){
	for(l=0;l<h;l++){
	  if(max(j,k)+l>=h) break;
	  //cout << c[i][j+l] << c[i+1][k+l] << endl;
	  if(c[i][j+l]==c[i+1][k+l]) co[i][j][k]++;
	}
	//cout << i << j << k << ":" << co[i][j][k] << endl;
      }
    }
  }
  memset(dp,-1,sizeof(dp));
  dp[0][0][0] = 0;
  for(i=0;i<=h;i++){
    for(j=0;j<=h;j++){
      for(k=0;k<=h;k++){
	
	if(~dp[i+1][j][k]) dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]+co[0][i][j]);
	else dp[i+1][j][k]=dp[i][j][k]+co[0][i][j];
	
	if(~dp[i][j+1][k]) dp[i][j+1][k]=min(dp[i][j+1][k],dp[i][j][k]+co[0][i][j]+co[1][j][k]);
	else dp[i][j+1][k]=dp[i][j][k]+co[0][i][j]+co[1][j][k];
	
	if(~dp[i][j][k+1]) dp[i][j][k+1]=min(dp[i][j][k+1],dp[i][j][k]+co[1][j][k]);
	else dp[i][j][k+1]=dp[i][j][k]+co[1][j][k];
      }
    }
  }
  
  cout << dp[h][h][h] << endl;
  return 0;
}

前計算を落とせれば満点取れそうだなーと思ったけど思いつかなかった。

【全体】
161位 1779 -> 1833 (+54)
ブランクがあった割には解けたのでよかった。
もっとコンテストに出ないといけないなーって感じだ。