POJ 2005 Blackjack

問題

トランプがnセット（1セットあたりジョーカーなしの52枚）与えられ、このカードデッキを使ってブラックジャックを行う。
この中からディーラーが1枚、あなたが2枚をランダムにピックアップし、場にお互いが見えるように置く。ディーラーがランダムにもう1枚引いたときにあなたが勝つ確率を求めよ。

やりかた

自分の得点はすぐ計算できる。その際にAを11として加算しても21より大きくならないならそうする。
ディーラーの得点は最初に引いたディーラーのカードがAか否かで場合分け。場合分けした上で各場合についてディーラーが引いた場合に負けとなるカードの総枚数（自分の勝ちパターン数）を計算し、ディーラーが引きうるカードの総数n * 52 - 3（全パターン数）で割れば割合となる。

以下ソース。

int p(char c){
  if(c == 'A') return 1;
  else if(isdigit(c)) return (int)(c - '0');
  else return 10;
}
int num(char c){
  if(c == 'A') return 1;
  if(c == 'K') return 13;
  if(c == 'Q') return 12;
  if(c == 'J') return 11;
  if(c == 'T') return 10;
  return (int)(c - '0');
}
int main(int argc, char **argv){
  int card[14];
  int n;
  while(cin >> n, n){
    if(n == 0) break;
    for(int i = 1; i <= 13; i++) card[i] = 4 * n;

    int dealer = 0, me = 0;
    char a, b, c;
    cin >> a >> b >> c;
    card[num(a)]--;
    card[num(b)]--;
    card[num(c)]--;
    
    me = p(b) + p(c);
    if(b == 'A' || c == 'A') me = (me + 10 <= 21) ? me + 10 : me;

    int chance = 0;
    if(a == 'A'){//ディーラーは最初にAを引いた
      for(int i = 1; i <= 13; i++){
	if(i == 1){//ディーラーは2枚目にAを引くケース
	  dealer = 12;
	  if(dealer < me && me <= 21) chance += card[i];
	}else{//ディーラーは2枚目にA以外をを引くケース
	  dealer = min(10, i) + 11;
	  if(dealer > 21) dealer -= 10;
	  if(dealer < me && me <= 21) chance += card[i];
	}
      }
      printf("%.3f\%\n\n", chance * 100.0 / (n * 52 - 3));
    }else{//ディーラーは最初にAではないカードを引いた
      for(int i = 1; i <= 13; i++){
	dealer = p(a);
	if(i == 1){//ディーラーは2枚目にAを引くケース
	  dealer += 11;
	  if(dealer > 21) dealer -= 10;
	  if(dealer < me && me <= 21) chance += card[i];
	}else{//ディーラーは2枚目にA以外を引くケース
	  dealer += min(i, 10);
	  if((dealer > 21 && me <= 21) || (dealer < me && me <= 21))
	    chance += card[i];
	}
      }
      printf("%.3f\%\n\n", chance * 100.0 / (n * 52 - 3));      
    }
  }
  return 0;
}

場合分けはもう少し削れるはず。

POJ 2418 Hardwood Species

問題

木の名前がいくつか入力される。各木の種類について、それが入力された総数のうち何%を占めているか木の名前のアルファベット順にパーセンテージで出力せよ。

やりかた

mapに木の名前と出現数を入れて総数で割って、、、というだけ。入力はgetsを使えば余裕で通る。

以下ソース。

int main(int argc, char **argv){
  char tree[256];
  map<string, int> p;
  int num = 0;
  while(gets(tree)){
    p[string(tree)]++;
    num++;
  }
  map<string, int>::iterator it = p.begin();
  for(; it != p.end(); it++)
    printf("%s %.4f\n", (it->first).c_str(), it->second * 100.0 / num);
  return 0;
}

atetubouさんによればgetlineでも通ったそうです。
PKU 2418 Hardwood Species - 日記

POJ 1730 Perfect Pth Powers

問題

整数Xが与えられる。X=b^pを満たすような整数bおよび自然数pが存在するとき、Xをp-th perfect numberという。pの最大値を求めよ。
制約:

やりかた

例えばなのでmax(p)=4となるように、Xを素因数分解して、各素因数の指数の最大公約数が答えになる。答えはせいぜい31以下なので、31以下の自然数pを大きい方から試して、素因数の指数が全部pで割り切れるような初めてのpを出力すればいい。
入力が負の数をとりうるので要注意。

以下ソース。

map<ll, int> pf(ll n){
  map<ll, int> p;
  for(ll i = 2; i * i <= n; i++){
    while(n % i == 0){
      p[i]++;
      n /= i;
    }
  }
  if(n != 1) p[n]++;
  return p;
}
int main(int argc, char **argv){
  ll n;
  while(cin >> n, n){
    map<ll, int> pr = pf(n < 0 ? -n : n);
    for(int p = 32; p >= 1; p--){
      bool check = true;
      map<ll, int>::iterator it = pr.begin();
      for(; it != pr.end(); it++){
	ll power = it->second;
        //pでべき乗数を割り切れないか、割り切れるけど正負が合わない場合は失敗とする
	if(power % p != 0 || (n < 0 && p % 2 == 0)) check = false;
      }
      if(check){
	cout << p << endl;
	break;
      }
    }
  }
  return 0;
}

負数の入力があることにしばらく気づかなかった。

POJ 2402 Palindrome Numbers

問題

自然数Nが与えられる。N <= 2e9
1から数えてN番目に出現する回文形式の整数を返せ。

やりかた

ある桁数の整数中に回文整数がいくつあるかというと、
1桁：1 ～ 9　9個
2桁：11 ～ 99　9個
3桁：101 ～ 999　90個
4桁：1001 ～9999　90個
5桁：10001 ～ 99999　900個
6桁：100001 ～ 999999　900個
といった具合にK桁の場合、9 * 10 ** ((K - 1) / 2)個存在する。
これでN番目の回文整数の桁数Kが求まる。ここから、N - (K-1桁までの回文整数の総数) = NがK桁の回文を小さい方から数えた順番(0-indexed)が求まる。
ここで例えば、桁数5の回文整数の、135番目に現れるとわかったとする。桁数5の回文整数は10001から始まり、ここから数えて135番目に現れる5桁の回文整数は、10001を半分の桁数にした100に134(1-indexedにした)を加えた234を折り返してつなげた23432となる。
桁数KのX番目を求める処理はこれをそのまま実装すればいい。

以下ソース。

string i2s(ll i){
  stringstream ss;
  ss << i;
  return ss.str();
}

int main(int argc, char **argv){
  ll r;
  while(cin >> r, r){
    ll sum = 0;
    int d;
    //桁数を求める => d
    for(d = 1; d <= 20; d++){
      ll total = 9LL * pow(10L, (d - 1) / 2);
      if(sum + total >= r) break;
      else sum += total;
    }
    r -= sum;
    ll s = pow(10LL, (d - 1) / 2) + r - 1;

    string ret = i2s(s);
    cout << ret;
    reverse(ALL(ret));
    if(d % 2 == 1)
      cout << ret.substr(1) << endl;
    else
      cout << ret << endl;
  }
  return 0;
}

POJ 3270 Cow Sorting

問題

要素のスワップを繰り返して数列を昇順にソートしたい。数列中のXとYを入れ替える時のコストをX+Yとする。ソートに必要な最小コストを求めよ。

やりかた

数列を巡回置換のまとまりに分解する。
例えば(3,5,7,4,2,1,6)であれば(3,7,1,6)(5,2)(4)となる。

すると各まとまり（列）ごとに分けて計算すれば良くなる。各列のサイズをci、最小の要素をmi、和をsumiとし、全体の数列中の最小の要素をMiとすると答えは以下の数式で表せる。

以下ソース。

//置換群の列挙 O(nlogn)
template<typename T>
vector<vector<int> > perm_group(vector<T> src){
  vector<T> dst = src;
  sort(dst.begin(), dst.end());

  int N = src.size();
  map<T, int> src_index, dst_index;
  for(int i = 0; i < N; i++) 
    src_index[src[i]] = i, dst_index[dst[i]] = i;
  
  vector<bool> vis(N, false);
  vector<vector<int> > ret;
  for(int i = 0; i < N; i++){
    if(vis[i]) continue;
    int start = i, idx = i;
    vector<int> perm;
    perm.push_back(start);
    vis[start] = true;
    while(src_index[dst[idx]] != start){
      idx = src_index[dst[idx]];
      perm.push_back(idx);
      vis[idx] = true;
    }
    ret.push_back(perm);
  }
  return ret;
}

int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  vector<int> s(N);
  int min1 = INF;
  for(int i = 0; i < N; i++){
    scanf("%d", &s[i]);
    min1 = min(min1, s[i]);
  }
  
  vector<vector<int> > p = perm_group(s);

  int ans = 0;
  for(int i = 0; i < p.size(); i++){
    if(p[i].size() == 1) continue;

    int min2 = INF;
    int sum = 0;
    for(int j = 0; j < p[i].size(); j++){
      sum += s[p[i][j]];
      min2 = min(min2, s[p[i][j]]);
    }
    ans += min(sum - min2 + (p[i].size() - 1) * min2, 
	       sum + min2 + (p[i].size() + 1) * min1);
  }
  printf("%d\n", ans);
  return 0;
}

POJ 2959 Ball bearings

問題

直径Dの円に内接する複数の直径dの小円を考える。小円同士の中心が少なくともs+d以上離れているように配置したい。最大でいくつの小円を配置できるか。

やりかた

配置する間隔は等間隔にする。間隔は円の個数に対して単調減少なので二分探索できる。C個置けるとすると隣り合う円の中心同士の距離は(D -d) * sin(π/C)になるのでこれがs+d以上になるかに関して二分探索する。

以下ソース。

int main(int argc, char **argv){
  int N; cin >> N;
  while(N--){
    double s, D, d;
    cin >> D >> d >> s;
    double ub = 1e10, lb = 0;
    for(int i = 0; i < 100; i++){
      double mid = (ub + lb) / 2.0;
      double dist = (D - d) * sin(3.14159265359 / mid);
      if(dist + EPS < d + s) ub = mid;
      else lb = mid;
    }
    cout << floor(ub) << endl;
  }
  return 0;
}

POJ 2437 Muddy roads

問題

一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる（s,eは非負整数）。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。

やりかた

貪欲。
領域の左端から注目している領域をすべて覆うように木板を置く。置いた後の木板の右端が次のぬかるみにかかっていれば、その領域も続いて覆うように木板を置く。これをすべて覆うまで続ける。

以下ソース。

int main(int argc, char **argv){
  int N, K;
  cin >> N >> K;
  vector<pair<int, int> > m;
  for(int i = 0; i < N; i++){
    int l, r; cin >> l >> r;
    m.push_back(make_pair(l, r));
  }
  sort(ALL(m));
  
  int idx, cnt = 0, r = 0;
  for(idx = 0; idx < N;){
    r = m[idx].first;
    int c = (m[idx].second - m[idx].first + K - 1) / K; //領域idxをすべて覆うのに必要な枚数
    cnt += c;
    r += c * K;//領域の右端を移動する
    idx++;
    while(m[idx].first < r && idx < N){//領域の右端が次の領域にかかっていたらその領域も続けて覆う
      c = (m[idx].second - r + K - 1) / K;
      cnt += c;
      r += c * K;
      idx++;
    }
  }
  cout << cnt << endl;
  return 0;
}