Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2265-dc5e7a25
この記事にトラックバックする(FC2ブログユーザー)

Round #115 E問題 - Power Defence (この記事を編集する[管理者用])

Source

RazMERiq 2012 E問題
Codeforces Round #115 E問題
Problem description

問題概要

タワーディフェンス系ゲーム.
敵が1匹,x軸を移動するので,与えることのできるダメージの最大値を求める問題.
タワーを建てれる場所は,y = -1, 1上の格子点のみで,同じ場所には2つ以上建てられない.
建てれるタワーの種類は以下3種類.
 タワー1,2 : 射程範囲内の敵に,毎秒いくらかのダメージを与える
 タワー3 : 射程範囲内の敵の移動スピードを遅くする
それぞれのタワーの種類に対して,射程範囲が与えられ,タワー1, 2に関しては攻撃力も与えられる.
敵の移動スピードは,1 / (1 + 影響を受けているタワー3の数).
それぞれの種類のタワーを何個まで建てることができるかが与えられる.建てられる合計数は20以下.

解法

本番では,以下で解いた.(おそらく想定解法ではない)
まず,タワーは一箇所に集中させた方が良い.
つまり,2m個置くなら (0, 1), (0, -1), (1, 1), (1, -1), ..., (m, 1), (m, -1) に置けばよいし,
2m+1個置くなら,追加で(m+1, 1)に置けば良い.
置き方は最悪で,20!/6!/7!/7!あるが,対称性を考えるとそんなに多くない.
つまり,(0, 1), (0, -1)を入れ替えても同じ置き方を満たせるし,左右反転しただけでも同じ置き方とみなせる.
対称なのを除去して,置き方を全部試すと,タイムリミットぎりぎりではあるけど通った.
その他の枝刈りとかは何も行なっていないので,枝刈ったりすると余裕を持って通るかもしれない.

おそらく想定解法は,タワー3の配置のみ全探索する.
これなら最大で20!/10!/10! = C(20, 10) < 2^20しかパターンはない.
タワー3の配置が決まれば,敵の移動スピードがわかるので,それぞれ空きマスにタワー1,2を置いたときのダメージ量が計算でき,DPにより最大ダメージが求められる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-10
void doubleIntSort(double d[],int m[],int s){int i,j,r;double k1,k2,t;if(s<=1)return;k1=(d[0]+d[s-1])/2.0;k2=k1+EPS;k1-=EPS;i=-1;j=s;for(;;){while(d[++i]<k1);while(d[--j]>k2);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;r=m[i];m[i]=m[j];m[j]=r;}doubleIntSort(d,m,i);doubleIntSort(d+j+1,m+j+1,s-j-1);}

int n;
int nf, ne, ns;
int rf, re, rs; double Rf, Re, Rs;
int df, de;
int h[21];
double res;

double x[100]; int ev[100];
int F, E, S;

void calc(void){
  int i,j,k;
  double w, tmp;

  if(n%2==0){
    i = h[0] + h[1]*10;
    j = h[n-2] + h[n-1]*10;
    if(i>j) return;
  }
  
  F = E = S = 0;
  rep(i,n){
    if(h[i]==0){
      x[2*i  ] = (i/2) - Rf;
      x[2*i+1] = (i/2) + Rf;
      ev[2*i  ] = 1;
      ev[2*i+1] = -1;
    }
    if(h[i]==1){
      x[2*i  ] = (i/2) - Re;
      x[2*i+1] = (i/2) + Re;
      ev[2*i  ] = 2;
      ev[2*i+1] = -2;
    }
    if(h[i]==2){
      x[2*i  ] = (i/2) - Rs;
      x[2*i+1] = (i/2) + Rs;
      ev[2*i  ] = 3;
      ev[2*i+1] = -3;
    }
  }
  doubleIntSort(x, ev, 2*n);

  tmp = 0;
  rep(i,2*n-1){
    w = x[i+1] - x[i];
    if(ev[i]==1) F++; if(ev[i]==-1) F--;
    if(ev[i]==2) E++; if(ev[i]==-2) E--;
    if(ev[i]==3) S++; if(ev[i]==-3) S--;
    tmp += (F*df + E*de) * (w * (S+1));
  }
  if(res < tmp) res = tmp;
}

void brute(int depth){
  if(depth==n) calc();
  
  if(nf > 0){
    h[depth] = 0;
    nf--;
    if(depth%2==0 || h[depth-1] <= h[depth]) brute(depth+1);
    nf++;
  }
  if(ne > 0){
    h[depth] = 1;
    ne--;
    if(depth%2==0 || h[depth-1] <= h[depth]) brute(depth+1);
    ne++;
  }
  if(ns > 0){
    h[depth] = 2;
    ns--;
    if(depth%2==0 || h[depth-1] <= h[depth]) brute(depth+1);
    ns++;
  }
}

int main(){
  int i,j,k,l,m;

  res = 0;

  scanf("%d%d%d",&nf,&ne,&ns);
  n = nf + ne + ns;
  scanf("%d%d%d",&rf,&re,&rs);
  scanf("%d%d",&df,&de);

  Rf = sqrt(rf*rf-1); if(rf==1) Rf = 0;
  Re = sqrt(re*re-1); if(re==1) Re = 0;
  Rs = sqrt(rs*rs-1); if(rs==1) Rs = 0;
  
  brute(0);

  printf("%.15f\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2265-dc5e7a25
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。