SRM 656 div2

Easy

問題概要

文字列s('a'~'z'で構成されている)のうちのちょうどk個の文字を任意の'a'~'z'に置き換えたとき、全ての文字が同じになるような文字列を返す。ただし、少なくとも1つは答えが存在し、複数答えがある場合は、そのうちの1つを返す。

制約

• 1 ≤ |s| ≤ 50
• 0 ≤ k ≤ |s|

解法

与えられた文字列の'a'~'z'の文字の出現数を数え、いずれかの文字の総数と|s|-kが等しいなら、長さ|s|のその文字を返す。

コード

class CorruptedMessage {
public:
  string reconstructMessage(string s, int k) {
    int arr[26] = {0}, N = s.size();
    for(int i = 0 ; i < N ; i++){
      arr[s[i]-'a']++;
    }
    int idx = -1;
    for(int i = 0 ; i < 26 ; i++){
      if(arr[i]+k == N){
	idx = i;
	break;
      }
    }
    string res;
    for(int i = 0 ; i < N ; i++){
      res += idx+'a';
    }
    return res;
　}
};

Med

問題概要

N個のパンケーキがある。各パンケーキiは幅i+1であり、おいしさはd[i]である。
まず初めにN個のうち1個を選び、皿にのせる。次に以下の操作をする。

1. パンケーキがなければ終了する。
2. まだ選んでいないパンケーキをランダムに選ぶ。
3. 選んだパンケーキの幅が、皿の一番上にあるパンケーキの幅よりも大きいならば、取らずに終了する。
4. そのパンケーキを皿の上のパンケーキに積む。1に戻る。

皿にのっているパンケーキのおいしさの総和がそのときのおいしさになる。
このとき、パンケーキのおいしさの期待値を返す。

制約

• 1 ≤ N ≤ 10
• 1 ≤ d[i] ≤ 100

解法

全探索。
まず初めにループで一番下に置くパンケーキを決める。
次に、再帰でパンケーキが置けなくなるか全てのパンケーキが置けるまで繰り返し、おいしさを足していく。
その総和を分岐の数で割る。

注意しないといけないのは、割る操作はまとめてやらないと誤差死する。

コード

class RandomPancakeStackDiv2 {
public:
  double solve(int S,int top,vector<int> &d,int N,int idx){
    if(S == (1<<N)-1){ return 0.0; }
    double res = 0.0;
    bool can = false;
    for(int i = 0 ; i < N ; i++){
      if((S >> i) & 1){ continue; }
      if(top > i){
	can = true;
	res += solve(S|(1<<i),i,d,N,idx+1)+d[i];
      }
    }
    return (can ? res/(N-idx) : 0.0);
  }
  double expectedDeliciousness(vector <int> d) {
    double res = 0.0;
    int N = d.size();
    for(int i = 0 ; i < N ; i++){
      double a = solve(1<<i,i,d,N,1)+d[i];
      res += a;
    }
    return res/N;
  }
};