Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 016 D - 軍艦ゲーム (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #016
問題文

問題概要

ノード数 $N$,枝数 $M$ のDAGが与えられる.
ノード $1$ からノード $N$ に移動するまでのかかる時間の期待値の最小値を求める問題.
以下の手順で移動する.
また,最大体力は $H$ で,初期体力は最大値である.
 1. 今いるノードから,出ている枝を $1$ つランダムに選び,その枝に沿って移動する.枝が出ていないなら移動できない.
 2. 辿り着いたノードに設定されている数値 $D_i$ だけ体力を減らす.体力が $0$ 以下になった場合は,それ以上何もできないので,そのようなことにはならないようにする.
 3. 現在の体力を $C$ として,$H-C$ だけ時間を消費して,ノード $1$ に移動しても良い.移動した場合は体力は全回復する.
1.~3.までの行動を $1$ 回行うと時間が $1$ だけ経過する.
ただし,期待値が無限大になる場合,ノード $N$ に辿りつけない場合はそれを指摘する.
$1 \leq N \leq 100$
$1 \leq H \leq 100$
答えは $10^6$ を超えない(期待値として有限時間で辿り着けるなら)

解法

3. のノード $1$ に戻る選択肢がなければ,今いるノードと現在体力を状態としてDPすれば良い.
答えを $X$ だと決め打ちすると,ノード $1$ に戻るときにかかる時間の期待値を $X$ を使って表すことができ,DPできる.
その結果の答え $T_X$ は,本当の答えを $T$ とすると,
 もし,$X \leq T$ ならば,帰るときに小さく見積もってしまうので $X \leq T_X \leq T$ となり,
 もし,$X \geq T$ ならば,帰るときに大きく見積もってしまうので $X \geq T_X \geq T$ となる.
これを利用して $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 N, M, H;
double C;

int edge[120][120], es[120];
int D[120];
double dp[120][120];

double solve(int now, int hp){
  int i, j, k, nhp;
  double res = 1e100, tmp;

  if(dp[now][hp] > -1) return dp[now][hp];
  if(now==N-1) return dp[now][hp] = 0;

  if(now != 0){
    tmp = C + (H-hp);
    res = tmp;
  }

  if(es[now]){
    tmp = 0;
    rep(i,es[now]){
      k = edge[now][i];
      nhp = hp - D[k];
      if(nhp <= 0){ tmp = 1e100; break; }

      tmp += (solve(k, nhp) + 1) / es[now];
    }
    if(res > tmp) res = tmp;
  }

  return dp[now][hp] = res;
}

int main(){
  int i,j,k,l,m,n,loop;
  double A, B, tmp;

  scanf("%d%d%d",&N,&M,&H);
  A = 0; B = 1e7;

  rep(i,N) es[i] = 0;
  rep(i,M){
    scanf("%d%d",&j,&k);
    j--; k--;
    edge[j][es[j]++] = k;
  }
  rep(i,N) scanf("%d",D+i);

  rep(loop,100){
    C = (A+B)/2;

    rep(i,N) rep(j,H+1) dp[i][j] = -100;
    tmp = solve(0, H);
    if(tmp > C) A=C;
    else        B=C;
  }

  if(A > 2e6) puts("-1"); else printf("%.10f\n",(A+B)/2);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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