beet's soil

競プロのことなど

AtCoder Beginner Contest 054

電磁気ェ…

【A - One Card Poker】

場合分けを頑張った。
1->14にする方法、天才かって感じ。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int a,b;
  cin>>a>>b;
  if(a==b){
    cout<<"Draw"<<endl;
    return 0;
  }
  if(a==1){
    cout<<"Alice"<<endl;
    return 0;
  }
  if(b==1){
    cout<<"Bob"<<endl;
    return 0;
  }

  if(b<a){
    cout<<"Alice"<<endl;
    return 0;
  }

  if(a<b){
    cout<<"Bob"<<endl;
    return 0;
  }
  
  return 0;
}
【B - Template Matching】

O(N^2M^2)を書くだけ。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  cin>>n>>m;
  string a[n],b[m];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<m;i++) cin>>b[i];
  bool f=0;
  for(int i=0;i<=n-m;i++){
    for(int j=0;j<=n-m;j++){
      bool ff=1;
      for(int k=0;k<m;k++)
	for(int l=0;l<m;l++)
	  ff&=a[i+k][j+l]==b[k][l];
      f|=ff;
    }
  }
  cout<<(f?"Yes":"No")<<endl;
  return 0;
}
【C - One-stroke Path】

使った辺と頂点をビットで持ってmap殴りメモ化再帰した。
next_permutationでいいじゃん(ア。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> G[10];
typedef pair<int,int> P;
map<P,int> S[10];
map<P,int> E;
int n,m,ans;
int dfs(int v,int eb=0,int vb=1){
  //cout<<v<<" "<<vb<<" "<<(1<<n)-1<<endl;
  if(vb+1==1<<n) return 1;
  if(S[v].count(P(eb,vb))) return S[v][P(eb,vb)];
  int res=0;
  for(int i=0;i<(int)G[v].size();i++){
    if(vb>>G[v][i]&1) continue;
    int k=E[P(v,G[v][i])];
    if(eb>>k&1) continue;
    res+=dfs(G[v][i],eb+(1<<k),vb+(1<<G[v][i]));
  }
  //cout<<v<<" "<<res<<endl;
  return S[v][P(eb,vb)]=res;
}
int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
    E[P(a,b)]=E[P(b,a)]=i;
  }
  cout<<dfs(0)<<endl;
  return 0;
}
【D - Mixing Experiment】

半分全列挙+DP。
冷静に考えてただのナップザック(ア。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,ma,mb;
  cin>>n>>ma>>mb;
  int a[n],b[n],c[n];
  for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
  int k=n/2,INF=1<<20;
  int dp[2][500][500];
  for(int i=0;i<500;i++)
    for(int j=0;j<500;j++)
      dp[0][i][j]=dp[1][i][j]=INF;
  for(int i=0;i<(1<<k);i++){
    int ta=0,tb=0,tc=0;
    for(int j=0;j<k;j++){
      if(i>>j&1){
	ta+=a[j];tb+=b[j];tc+=c[j];
      }
    }
    //cout<<ta<<" "<<tb<<" "<<tc<<endl;
    dp[0][ta][tb]=min(dp[0][ta][tb],tc);
  }
  for(int i=0;i<(1<<(n-k));i++){
    int ta=0,tb=0,tc=0;
    for(int j=k;j<n;j++){
      if(i>>(j-k)&1){
	ta+=a[j];tb+=b[j];tc+=c[j];
      }
    }
    //cout<<ta<<" "<<tb<<" "<<tc<<endl;
    dp[1][ta][tb]=min(dp[1][ta][tb],tc);
  }
  int ans=INF;
  for(int i=0;i<500;i++){
    for(int j=0;j<500;j++){
      if(dp[0][i][j]==INF) continue;
      for(int x=0;x<500;x++){
	if(i+x==0) continue;
	if((mb*(i+x)-ma*j)<0||(mb*(i+x)-ma*j)%ma) continue;
	int y=(mb*(i+x)-ma*j)/ma;
	if(y>=500) continue;
	//cout<<i+x<<" "<<j+y<<":"<<dp[0][i][j]+dp[1][x][y]<<endl;
	ans=min(ans,dp[0][i][j]+dp[1][x][y]);
      }
    }
  }
  cout<<(ans<INF?ans:-1)<<endl;
  return 0;
}
【全体】

oooo 61th
0WAなのはいいんだけどCDでオーバーキルして時間がかかってしまった。
n=40なら半分全列挙みたいに思い込むのやめないと、、