Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #115 D問題 - Plane of Tanks: Duel (この記事を編集する[管理者用])

Source

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

問題概要

2人でFPSゲームで銃の撃ち合い対戦する.
相手を倒せる確率を求める問題.
時間0では両者とも同時に攻撃する.
自分と敵のステータスとして,それぞれ
 HP : これが0になると倒され,以降攻撃できない
 DT : 攻撃間隔.このプレイヤーは時間0, DT, 2DT, 3DT, ... に攻撃する
 L, R : 最小攻撃力と最大攻撃力.攻撃が命中したら,敵のHPがL以上R以下のランダムの整数だけ減る.
 P : 攻撃を避けられる率.この確率で相手に全くダメージを与えられない.(整数%で与えられる)
が与えられる.
HPは200以下,DTは1以上30以下,攻撃力は10以上100以下.

解法

おそらく想定解法は以下の通り.
それぞれ何回攻撃を食らったら死ぬかという確率を十分大きな回数までDPで求めておく.
DPにおいて,R-L+1個の和を計算するとき,累積和を用いて高速化する.
後は,シミュレーションする.
避けられる率が100%の時は例外処理するのも良い.

本番では,以下で解いた.(おそらく想定解法ではない)
時間は周期LCM(DT1, DT2)で考えればよく,その間の攻撃回数はたかだか60回程度.
時間,自分のHP,相手のHPを状態にして,DPした.
DPする時,次に攻撃が命中する攻撃で場合分けし,ずっと当たらず時間が一周したら同じ状態に戻ってくるので,適当に処理する.
O((DT1+DT2)^2 * HP^2)ぐらい.

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)

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}
int LCM(int a,int b){ return a*b/GCD(a,b); }

double  dp[120][210][210];
double sum[120][210][210];

int hp1, dt1, l1, r1, p1; double P1;
int hp2, dt2, l2, r2, p2; double P2;
int turn_size, turn[670];

double inv[20000];

double get_ave(int t, int a1, int a2, int b1, int b2){
  int area = (a2-a1+1) * (b2-b1+1);
  double res = 0;

  if(b2 < 0){
    return 1;
  }
  if(b1 < 0){
    res += (-b1)*(a2-a1+1);
    b1 = 0;
  }
  if(a2 < 0){
    return 0;
  }
  if(a1 < 0){
    a1 = 0;
  }

  res += sum[t][a2+1][b2+1] - sum[t][a1][b2+1] - sum[t][a2+1][b1] + sum[t][a1][b1];

  return res * inv[area];
}

int main(){
  int i,j,k,l,m,n;
  int t, s, ss, mt;
  int h1, h2;
  double pp;
  double ave1[200], ave2[200];

  REP(i,1,20000) inv[i] = 1.0/i;

  scanf("%d%d%d%d%d",&hp1,&dt1,&l1,&r1,&p1);
  scanf("%d%d%d%d%d",&hp2,&dt2,&l2,&r2,&p2);

  if(p1==100){puts("0"); return 0;}
  if(p2==100){puts("1"); return 0;}
  P1 = p1 / 100.0;
  P2 = p2 / 100.0;

  turn_size = 0;
  mt = LCM(dt1,dt2);
  rep(t,mt){
    if(t%dt1==0) turn[turn_size++] = 1;
    if(t%dt2==0) turn[turn_size++] = 2;
  }

  rep(h1,hp1) rep(h2,hp2){
    rep(t,turn_size){
      ave1[t] = get_ave( t, h1, h1, h2-r1, h2-l1 );
      ave2[t] = get_ave( t, h1-r2, h1-l2, h2, h2 );
    }
    
    rep(t,turn_size){
      pp = 1;
      rep(s,turn_size){
        ss = turn[(t+s)%turn_size];
        if(ss==1){
          dp[t][h1][h2] += pp * (1-P1) * ave1[(t+s+1)%turn_size];
          pp *= P1;
        } else {
          dp[t][h1][h2] += pp * (1-P2) * ave2[(t+s+1)%turn_size];
          pp *= P2;
        }
      }
      dp[t][h1][h2] /= (1-pp);
/*      printf("%d %d %d : %f\n",t,h1,h2,dp[t][h1][h2]);*/
      sum[t][h1+1][h2+1] = sum[t][h1+1][h2] + sum[t][h1][h2+1] - sum[t][h1][h2];
      sum[t][h1+1][h2+1] += dp[t][h1][h2];
    }
  }

  printf("%.15f\n",dp[0][hp1-1][hp2-1]);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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