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に戻る。
皿にのっているパンケーキのおいしさの総和がそのときのおいしさになる。
このとき、パンケーキのおいしさの期待値を返す。
制約
- 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; } };