Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-02-03

Codeforces Round #105 (Div. 2)

02:31 | Codeforces Round #105 (Div. 2) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces Round #105 (Div. 2) - capythm@TopCoder Codeforces Round #105 (Div. 2) - capythm@TopCoder のブックマークコメント

ox-x- 860pt という散々な結果に・・・。A~D問題の復習した結果をまとめました。

A. Insomnia cure

http://codeforces.com/contest/148/problem/A

問題の意味

  • 王女は寝るとき頭の中でドラゴンを数えてたが、ただ数えるだけなのは飽きた。
  • そこで、k番目ごとのドラゴンにパンチをくらわすようにした
  • 同様に、l,m,n番目ごとのドラゴンにも攻撃をする
  • d番目までドラゴンを数える場合の攻撃をヒットしたドラゴンの数を出力せよ

解法

  • $1<d<10^5$なので、攻撃を加えたドラゴンにフラグを立てて、最後にカウントする方法で間に合う。
  • グローバル変数は0に初期化されることを利用すると、初期化が不要な分、若干早くなる。

ソースコード

#include <iostream>
using namespace std;

int a[100003];
int main( void )
{
  int k,l,m,n,d;
  cin >> k >> l >> m >> n >> d;
  for( int i=k; i<=d; i+=k ) a[i] = 1;
  for( int i=l; i<=d; i+=l ) a[i] = 1;
  for( int i=m; i<=d; i+=m ) a[i] = 1;
  for( int i=n; i<=d; i+=n ) a[i] = 1;
  int ret=0;
  for( int i=1; i<=d; i++  ) ret += a[i];
  cout << ret << endl;
  return 0;
}

別解

  • d がものすごく大きい場合は上記のアルゴリズムでは間に合わない。
  • その場合、包除原理を利用する方法がある。
  • d 中 k で割り切れるドラゴンの数は d/k で、これがパンチをしたドラゴンの数
  • 同様に d/l, d/m, d/n で攻撃を加えたドラゴンの数がわかるが、これらの和では例えば k でも l でも割り切れるドラゴンを余分に足しすぎてしまっているので差し引く必要がある(包除原理)
  • k でも l でも割り切れる→kとlの最小公倍数 lcm(k,l) の倍数
#include <iostream>
using namespace std;

int gcd( int a, int b )
{
  int t;
  if( a < b ){ t = a; a = b; b = t; }
  while( ( t = a % b ) != 0 ){ a = b; b = t; }
  return b;
}
int lcm( int a, int b )
{
  return a * b / gcd(a,b);
}

int main( void )
{
  int k,l,m,n,d;
  cin >> k >> l >> m >> n >> d;
  int ret =   d/k + d/l + d/m + d/n 
            - d/lcm(k,l) - d/lcm(k,m) - d/lcm(k,n) - d/lcm(l,m) - d/lcm(l,n) - d/lcm(m,n)
            + d/lcm(k,lcm(l,m)) + d/lcm(k,lcm(l,n)) + d/lcm(k,lcm(m,n)) + d/lcm(l,lcm(m,n))
            - d/lcm(lcm(k,l),lcm(m,n));
  cout << ret << endl;
  return 0;
}

B. Escape

http://codeforces.com/problemset/problem/148/B

問題の意味

  • 王女がドラゴンの住む洞窟から城まで逃げ出したい
  • 王女の時速 v_p、ドラゴンの時速 v_d
  • ドラゴンは王女が逃げ出してから t 時間後に王女を追いかけ始める
  • 王女はドラゴンに追いつかれると洞窟から盗んだ宝石を落とす。ドラゴンは宝石を拾って洞窟まで戻る。洞窟で宝石を片付けるのに f 時間かかる。
  • 王女が無事に城(位置c)にたどり着けるには宝石が何個必要か?
  • ただし、王女とドラゴンが同時に城にたどり着いた場合、王女は逃げ切れたとする。

解法

  • シミュレーションにより解きます。
  • v_p \geq v_dの場合、解が0なのは自明なので、それ以外の場合を考える。
  • 王女が位置 x に、ドラゴンが位置 0 にいる場合、ドラゴンが王女に追いつくまでにかかる時間をsとすると、sv_d = x+sv_p から s=\frac{x}{v_d-v_p}、追いつかれる位置がx'=\frac{v_d}{v_d-v_p}xであることがわかる。
  • x'\geq cなら追加の宝石はいらない。そうでない場合、宝石を落とす。その場合、ドラゴンが洞窟まで戻るのに x'/v_d時間、宝石を片付けるのにf時間かかるので、その時間分王女は逃げることができるので、xを更新する。
  • 城まで逃げ切れるかを比較する場合、double 演算では丸め誤差があるのでそれを考慮した計算を行う(微少量εの誤差を許容して比較)

ソースコード

#include <iostream>
using namespace std;

int main( void )
{
  double EPS = 1e-9;
  double vp,vd,t,f,c;
  cin >> vp >> vd >> t >> f >> c;
  int ret = 0;
  if( vp >= vd ){ cout << ret << endl; return 0; }
  double x = vp * t;
  while( 1 ){
    x = vd * x / (vd-vp);
    if( x+EPS >= c ){ cout << ret << endl; break; }
    ret++;
    x += (x/vd + f)*vp;
  }
  return 0;
}

C. Terse princess

http://codeforces.com/problemset/problem/148/C

問題の意味

  • 王女はたくさんの花婿候補と面談する。王女が花婿を選ぶ基準は金(資産)。
  • 王女は、現在の候補者が直前の候補者よりも金持ちなら「Oh」、今までの候補者の資産の合計よりもより多くの資産を持ってたら「Wow」を言う(「Wow」を言う場合は「Oh」は言わない)
  • 最初の候補者の時は何も言わない
  • 「Oh」は a 回「Wow」は b 回、面談した候補者は n 人、値域:a,bは0~15、nはa+b+1~100 資産は1~50000
  • これらから考えられる花婿候補の資産を出力せよ(解は複数あるのでどれか一つでよい)
  • 解なしの場合は単に -1 を出力

解法

  • 場合分けをちゃんと考える
  • b>0の場合:例えば(n,a,b)=(7,2,3)
    • 1 2 4 8 9 10 1 と出力すればいい。(最初は1、続くb個は2倍にしていく、さらに続くa個は+1していく、余ったら1出力)
    • bは最大15なので2^{15}=32768は50000以下で収まる
  • b=0、a=n-1、n>1 の場合、解なしになるので -1 を出力する
    • ただし、b=0, a=0, n=1 (a=n-1成立)は例えば 1 出力で OK なので気をつける
  • b=0、a<n-1 の場合:例えば(n,a,b)=(7,3,0)</li>
    • 2 2 3 4 5 1 1 (最初の2個は2 (←大きすぎなければ何でもいい)、続くa個は+1。余ったら1出力)

上記を注意深く実装すればいい(これが難しい・・・)。

ソースコード

#include <iostream>
using namespace std;

int main( void )
{
  int n,a,b;
  cin >> n >> a >> b;
  int idx=0, r;
  if( b > 0 ){
    r = 1;
    cout << r;
    for( int i=0; i<b; i++ ){ r*=2; cout << ' ' << r; }
    idx = b+1;
  } else {
    if( n > 1 && a == n-1 ){ cout << -1 << endl; return 0; }
    r = 2; cout << r;
    idx = 1;
    if( a > 0 ){ cout << ' ' << 2; idx++; }
  }
  for( int i=0; i<a; i++ ){ r++; cout << ' ' << r; idx++; }
  for( int i=idx; i<n; i++ ){ cout << ' ' << 1; }
  cout << endl;
  return 0;
}

D. Bag of mice

http://codeforces.com/problemset/problem/148/D

問題の意味

  • ドラゴンと王女がゲームをする
  • かばんの中に w 個の白いねずみと b 個の黒いねずみがいる。
  • 交代交代に1匹ずつねずみを捕りだし、最初に白いねずみを取り出した方が勝ち
  • 王女が先手
  • ただし、ドラゴンがねずみを取り出すとき、鞄の中のねずみがパニックになり一匹かばんの中から逃げ出す。逃げ出したねずみはどちらの色でも勝敗に関係ない。王女の手番ではこういうことは起きない。
  • 王女が勝つ確率を出力せよ

解法

  • 白ねずみ w 個、黒ねずみ b 個の時の王女の勝率を P(w,b)とおく。
  • 1発目で王女が勝つ確率は w/(w+b)
  • b/(w+b) の確率で手番がドラゴンになる
    • この時、ドラゴンが黒いねずみを取り出す(王女が勝つ可能性がある)確率は (b-1)/(w+b-1)
    • そこから白いねずみが逃げる確率は w/(w+b-2), 黒いねずみが逃げる確率は (b-2)/(w+b-2)

上記をまとめると、以下の式が成立する。

 P(w,b) = \frac{w}{w+b} + \frac{b}{w+b}\times\frac{b-1}{w+b-1}\(\frac{w}{w+b-2}P(w-1,b-2) + \frac{b-2}{w+b-2}P(w,b-3)\)

  • 上式を使って w=0,b=0,b<0 になってしまうケースに気をつけながらメモ化再帰あるいはDPにより実装すれば解ける

ソースコード(メモ化再帰による実装)

#include <iostream>
#include <cstdio>
using namespace std;

double p[1003][1003];
int w;

double solve( int w, int b )
{
  if( p[w][b] >= 0 ) return p[w][b];
  if( w == 0 ){ p[w][b] = 0; return 0; }
  if( b == 0 ){ p[w][b] = 1; return 1; }
  if( b < 0  ){ return 1; }
  double ret = 0;
  ret += (double)w/(w+b);
  if( b < 2 ){ p[w][b] = ret; return ret; }
  ret += ((double)b*(b-1)/((double)(w+b)*(w+b-1))) * ( ( (double)(b-2)/(double)(w+b-2) ) * solve( w,b-3 ) + 
                                                       ( (double)(w)  /(double)(w+b-2) ) * solve( w-1,b-2)  );
  p[w][b] = ret; return ret;
}

int main( void )
{
  int b;
  cin >> w >> b;
  for( int i=0; i<1003; i++ ) for( int j=0; j<1003; j++ ) p[i][j] = -1;
  printf( "%1.9lf\n", solve(w,b) );
  return 0;
}

ソースコード(DPによる実装)

#include <iostream>
#include <cstdio>
using namespace std;

double p[1003][1003];

int main( void )
{
  int w,b;
  cin >> w >> b;
  for( int i=1; i<=w; i++ ) for( int j=0; j<=b; j++ ){
    double W=i,B=j;
    p[i][j] = W/(W+B);
    if( j > 1 ) p[i][j] += B/(W+B) * (B-1)/(W+B-1) *     W/(W+B-2) * p[i-1][j-2];
    if( j > 2 ) p[i][j] += B/(W+B) * (B-1)/(W+B-1) * (B-2)/(W+B-2) * p[i  ][j-3];
  }
  printf( "%1.9lf\n", p[w][b] );
  return 0;
}