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

beet's soil

競プロのことなど

Google Code Jam 2017 Round 1A

ABc 333rd Round1通過!

【Problem A. Alphabet Cake】

R*Cの長方形のケーキが与えられる。各マスにはアルファベットが書かれているかまだ書かれていない。
各アルファベットの領域が長方形になるような割り当てを1つ求める。

列ごとに考える。各列について1つでもアルファベットがあれば横に伸ばせば各列ごとは成り立つ。
ない場合は上か下の列をそのままコピーすればよい。
O(TRC)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    cout<<"Case #"<<t<<":"<<endl;
    int r,c;
    cin>>r>>c;
    string s[r];
    for(int i=0;i<r;i++) cin>>s[i];
    for(int i=0;i<r;i++){
      int f=0;
      for(int j=0;j<c;j++) f|=s[i][j]!='?';
      if(!f) continue;
      for(int j=0;j<c;j++){
	if(s[i][j]=='?') continue;
	int k=j-1;
	while(k>=0&&s[i][k]=='?') s[i][k--]=s[i][j];
	k=j+1;
	while(k<c&&s[i][k]=='?') s[i][k++]=s[i][j];
      }
    }
    for(int i=0;i<r;i++){
      int f=0;
      for(int j=0;j<c;j++) f|=s[i][j]!='?';
      if(!f) continue;
      int k=i-1;
      while(k>=0&&s[k][0]=='?'){
	for(int j=0;j<c;j++) s[k][j]=s[i][j];
	k--;
      }
      k=i+1;
      while(k<r&&s[k][0]=='?'){
	for(int j=0;j<c;j++) s[k][j]=s[i][j];
	k--;
      }
    }
    for(int i=0;i<r;i++) cout<<s[i]<<endl;
  }
  return 0;
}
【Problem B. Ratatouille】

n種類の食材がありそれぞれp個のパッケージがある。
それぞれの食材について1つの料理を作るための適正量s_iが決まっている
詰め合わせが作れる条件は
s_i*k*0.9<=p_ij<=s_i*k*1.1を満たすある自然数kが存在する。(i,j,kは適当)
なるべく多くの詰め合わせを作りたい。

smallはnext_permutationするだけ。
largeはなんか結局区間割り当て問題みたいになって
激ヤバ定数貪欲法の気配を感じたので解いたらあっさり通ってしまった。
オーダー忘れた。最悪10^9くらいだった気がする。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    int n,p;
    cin>>n>>p;
    int r[n],q[n][p];
    for(int i=0;i<n;i++) cin>>r[i];
    for(int i=0;i<n;i++)
      for(int j=0;j<p;j++)
	cin>>q[i][j];

    for(int i=0;i<n;i++) sort(q[i],q[i]+p);
    int ans=0;

    if(n==1){
      for(int i=0;i<p;i++){
	bool f=0;
	int k=(10*q[0][i])/(11*r[0])-1;
	while(9*r[0]*k<=10*q[0][i]){
	  f|=10*q[0][i]<=11*r[0]*k;
	  if(f) break;
	  k++;
	}
	ans+=f;
      }
      cout<<"Case #"<<t<<": "<<ans<<endl;
      continue;
    }
    
    int L[n][p],R[n][p];
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    
    for(int i=0;i<n;i++){
      for(int j=0;j<p;j++){
	bool f=0;
	int k=max((10*q[i][j])/(11*r[i])-1,1LL);
	while(9*r[i]*k<=10*q[i][j]){
	  f|=10*q[i][j]<=11*r[i]*k;
	  if(f) break;
	  k++;
	}
	if(!f){
	  if(j) R[i][j]=R[i][j-1];
	  continue;
	}
	L[i][j]=k;
	k=(10*q[i][j])/(9*r[i])+10;
	f=0;
	while(10*q[i][j]<=11*r[i]*k){
	  f|=9*r[i]*k<=10*q[i][j];
	  if(f) break;
	  k--;
	}
	R[i][j]=k;
	//if(t==66) cout<<i<<"-"<<j<<":"<<L[i][j]<<"/"<<R[i][j]<<endl;
      }
    }

    bool used[n][p];
    memset(used,0,sizeof(used));
    for(int j=0;j<p;j++){
      if(L[0][j]<0) continue;
      bool visit[n][p];
      memset(visit,0,sizeof(visit));
      for(int x=L[0][j];x<=R[0][j];x++){
	bool f=1;
	for(int i=1;i<n;i++){
	  int y=lower_bound(R[i],R[i]+p,x)-R[i];
	  //if(t==66) cout<<i<<":"<<x<<" "<<y<<endl;
	  while(y<p&&used[i][y]) y++;
	  //if(t==66) cout<<i<<":"<<x<<" "<<y<<endl;
	  
	  if(y==p||x<L[i][y]||x>R[i][y]){
	    f=0;
	    break;
	  }
	  visit[i][y]=1;
	}
	if(f){
	  ans++;
	  for(int i=0;i<n;i++)
	    for(int k=0;k<p;k++)
	      used[i][k]|=visit[i][k];
	  break;
	}
      }
    }
    cout<<"Case #"<<t<<": "<<ans<<endl;
  }
  return 0;
}
【Problem C. Play the Dragon】

ドラゴンと騎士がいる。
ドラゴンと騎士の最初のHPと攻撃力が与えられる。
戦闘はターン制で、ドラゴンが下の行動のうちどれかをしたあと、騎士が攻撃する。
攻撃 騎士に攻撃力分のダメージを与える
バフ 自分の攻撃力をB高める
デバフ 相手の攻撃力をD下げる(0未満になった場合は0になる
回復 自分のHPを全回復する
なるべく少ないターン数で騎士を倒したい。

smallはBFSして全探索。制約が小さいので愚直でもなんとかなる。
largeはデバフ->バフ->攻撃の順番でやることしかわかんなかった。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef tuple<int,int,int,int> P;
signed main(){
  int T;
  cin>>T;
  for(int t=1;t<=T;t++){
    cout<<"Case #"<<t<<": ";
    int hd,ad,hk,ak,b,d;
    cin>>hd>>ad>>hk>>ak>>b>>d;
    int ans=-1;
    queue<P> q;
    q.emplace(hd,ad,hk,ak);
    map<P,int> m;
    m[make_tuple(hd,ad,hk,ak)]=0;
    while(!q.empty()){
      P p=q.front();q.pop();
      int a[4];
      {
	a[0]=get<0>(p);a[1]=get<1>(p);
	a[2]=get<2>(p);a[3]=get<3>(p);
	a[2]-=a[1];
	if(a[2]<=0){
	  ans=m[p]+1;
	  break;
	}
	a[0]-=a[3];
	if(a[0]>0&&!m.count(make_tuple(a[0],a[1],a[2],a[3]))){
	  m[make_tuple(a[0],a[1],a[2],a[3])]=m[p]+1;
	  q.emplace(a[0],a[1],a[2],a[3]);
	}
      }
      {
	a[0]=get<0>(p);a[1]=get<1>(p);
	a[2]=get<2>(p);a[3]=get<3>(p);
	a[1]+=b;
	a[0]-=a[3];
	if(a[0]>0&&!m.count(make_tuple(a[0],a[1],a[2],a[3]))){
	  m[make_tuple(a[0],a[1],a[2],a[3])]=m[p]+1;
	  q.emplace(a[0],a[1],a[2],a[3]);
	}
      }
      {
	a[0]=get<0>(p);a[1]=get<1>(p);
	a[2]=get<2>(p);a[3]=get<3>(p);
	a[0]=hd;
	a[0]-=a[3];
	if(a[0]>0&&!m.count(make_tuple(a[0],a[1],a[2],a[3]))){
	  m[make_tuple(a[0],a[1],a[2],a[3])]=m[p]+1;
	  q.emplace(a[0],a[1],a[2],a[3]);
	}
      }
      {
	a[0]=get<0>(p);a[1]=get<1>(p);
	a[2]=get<2>(p);a[3]=get<3>(p);
	a[3]-=d;
	if(a[3]<0) a[3]=0;
	a[0]-=a[3];
	if(a[0]>0&&!m.count(make_tuple(a[0],a[1],a[2],a[3]))){
	  m[make_tuple(a[0],a[1],a[2],a[3])]=m[p]+1;
	  q.emplace(a[0],a[1],a[2],a[3]);
	}
      }
    }
    if(ans<0) cout<<"IMPOSSIBLE"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}

なんかあっさり通過してしまってびっくりしている。
FHCの反省を踏まえてTシャツを目指していきたい。