Hatena::Grouptopcoder

敗戦記

2011-03-28

ITRIX 11 OPC

| 11:55

SPOJで行われていたコンテストに参加しました。

5問あったのですが、2問解いたあと、3問目以降が分からずに寝ました。

せっかくなので書いたコードを貼り付けます。

A

  • ヒットアンドブローを文字列に拡張したような問題。
  • 書く。サーバーが非常に重くてなかなか提出できない。
  • やっとつながった。提出。

8分24秒

main(){
  int t;
  cin>>t;
  while(t--){
    string in;
    cin>>in;
    set<int> app;
    rep(i,in.size())app.insert(in[i]);
    int m;
    cin>>m;
    while(m--){
      string a;
      cin>>a;
      int g=0,b=0;
      rep(i,a.size()){
	if(app.count(a[i]))++g;
	if(a[i]==in[i])++b;
      }
      cout<<g<<' '<<b<<endl;
    }
  }
}

B

  • 0のみ、又は2,3,5,7のみからなる数字を小さい順に並べたときに、n番目に来る数を答える問題。
  • AOJにあったPC甲子園の過去問に似たような問題があったので、それを思い出しながら書く。
  • 微妙に数字の変換に戸惑いながら書き切る。
  • 0が来る場合があるかどうかは分からないのですが、一応0がきた場合は"0"を返すようにしてみました。

17分23秒

string luck(ll n){
  if(n==0)return "0";
  string ret;
  do{
    n--;
    ret+=n%4;
    n/=4;
  }while(n);
  rep(i,ret.size()){
    switch(ret[i]){
    case 0:ret[i]='2';break;
    case 1:ret[i]='3';break;
    case 2:ret[i]='5';break;
    case 3:ret[i]='7';break;
    }
  }
  reverse(ALL(ret));
  return ret;
}

main(){
  int t;
  cin>>t;
  while(t--){
    ll n;
    cin>>n;
    cout<<luck(n)<<endl;
  }
}

C

  • 超要約すると、m*m以下の正方行列から縦横にかぶらないようにm個の要素を選び出し、その和を最大化する。というような問題。
  • 愚直にやると15!とかになって終わらない。なんとなく幅優先とかを書いたりしましたが、無理でした。
  • 次に訪れる場所と訪れた場所を持ってdpするというようなことも考えましたが、訪れた場所とその次の状態をうまく生成する方法が分からずに、あきらめました。
  • あとで蟻本を見たら集合の順列の作り方が書いてあったので、練習で通しました。
ll dp[15][1<<15];
ll a[15][15],b[15][15],c[15][15];

main(){
  int t;
  cin>>t;
  while(t--){
    memset(dp,0,sizeof(dp));
    int m;
    cin>>m;
    rep(i,m)rep(j,m)cin>>a[i][j];
    rep(i,m)rep(j,m)cin>>b[i][j];
    rep(i,m)rep(j,m){
      cin>>c[i][j];
      c[i][j]*=min(a[i][j],b[i][j]);
    }

    ll ans=0;
    rep(i,m){
      dp[0][1<<i]=c[i][0];
      ans=max(ans,dp[0][1<<i]);
    }


    for(int i=1;i<m;i++){
      rep(j,m){
	int comb=(1<<i)-1;
	while(comb< (1<<m) ){
	  if(((comb>>j) &1)==0){
	    dp[i][comb|1<<j]=max(dp[i][comb|1<<j],dp[i-1][comb]+c[j][i]);
	    ans=max(dp[i][comb|1<<j],ans);
	  }
	  int x=comb&-comb,y=comb+x;
	  comb=((comb&~y)/x>>1)|y;
	}
      }
    }
    cout<<ans<<endl;
  }
}