SRM 671 DIV1 Easy - BearCries

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14010&rd=16551

解き方

固定できる条件はなさそう。
ある値でソーティングして貪欲にも解けなさそうなのでｄｐを考える。

dp[現在の位置][;があって_がない絵文字][;があって_がある絵文字]=現在の位置の一つ前までの状態数と考えると、200*200*200=8*10^6で間に合う。

dp[n][0][0]が最終的な答えになる。

コード

long long dp[202][202][202];

class BearCries {

public: int count(string message) {
int n=message.size();
int MOD=1000000007;

memset(dp,0,sizeof(dp));
dp[0][0][0]=1;

FORE(i,0,n){
FORE(j,0,201)FORE(k,0,201){
if(message[i]=='_'){
if(j)dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*j)%MOD;
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k]*k)%MOD;
}else{
if(k)dp[i+1][j][k-1]=(dp[i+1][j][k-1]+dp[i][j][k]*k)%MOD;
dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k])%MOD;
}
}
}

return dp[n][0][0];
}

};

SRM 381 DIV1 Easy - TheDiceGame

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8414&rd=10804

解き方

dpで解く。
前の状態から現在の状態までに行ける全ての場合について和をとっていく。
前の状態から＋１回かつサイコロなので1/6を掛けたものになる。

コード

class TheDiceGame {

public: double expectedThrows(int candies) {

memset(dp,0,sizeof(dp));

for(int i=1;i<=candies;i++){

for(int j=1;j<=6;j++){

int prev=max(0,i-j);

dp[i]+=(dp[prev]+1.0)/6.0;

}

}

return dp[candies];

}

};

2015 TCO Round 2C Easy - YetAnotherCardGame

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13912&rd=16523

解き方

dpの問題。
１．どのような順序で処理されるか
　→petr、snukeが順番に１つずつ出していく
２．前の状態としてどのような状態があればよいか
　→前に出されたカードと、それまでに重ねられたカードの数

dp[一番上のカードの数字]＝ 重ねられたカードの数の最大値とし、
毎ターンできるだけ小さな数字でカードを重ねていけば良い。

問題文中の取ることが出きる動作のうち、１枚カードを食べるというのは
要はパスしてもよいというのがわかれば上記に帰着できそうだった。

コード

class YetAnotherCardGame {

public: int maxCards(vector<int> petr, vector<int> snuke) {
int n=petr.size();
int dp[101];
memset(dp,0,sizeof(dp));

sort(all(petr));
sort(all(snuke));
FORE(i,0,n){
for(int x=100;x>=0;x--){
FORE(j,0,n)if(petr[j]>x){
dp[petr[j]]=max(dp[petr[j]],dp[x]+1);
break;
}
}

for(int x=100;x>=0;x--){
FORE(j,0,n)if(snuke[j]>x){
dp[snuke[j]]=max(dp[snuke[j]],dp[x]+1);
break;
}
}
}

return *max_element(dp,dp+101);
}

};

2015 TCO Round 2B Easy - Bitwisdom

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13778&rd=16500

解き方

dpで解く。
dp[現在の位置][現在が1か0か][1が最初から連続しているかのフラグ]とする。

現在のビット０になったとき、
１が最初から連続していれば１回の操作が必要で、
連続していなければ２回の操作が必要になる。

#英出張中で出れなかったが、日本だと出場しやすい時間だったので出たかった…

コード

class Bitwisdom {

public: double expectedActions(vector<int> p) {
int n=p.size();
double dp[301][2][2];

memset(dp,0,sizeof(dp));
double ret=0;

dp[0][0][0]=(100-p[0])*0.01;
dp[0][1][1]=p[0]*0.01;

for(int i=1;i<n;i++){
ret+=dp[i-1][1][0]*(100-p[i])*0.02;
ret+=dp[i-1][1][1]*(100-p[i])*0.01;

dp[i][0][0]+=dp[i-1][0][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][0]*(100-p[i])*0.01;
dp[i][0][0]+=dp[i-1][1][1]*(100-p[i])*0.01;

dp[i][1][0]+=dp[i-1][0][0]*p[i]*0.01;
dp[i][1][0]+=dp[i-1][1][0]*p[i]*0.01;

dp[i][1][1]+=dp[i-1][1][1]*p[i]*0.01;
}
ret+=dp[n-1][1][1]+dp[n-1][1][0];

return ret;
}

};

SRM 555 DIV1 Easy - CuttingBitString

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12155&rd=15177

解き方

ｄｐで解く。ｎは５０なので整数の最大は2^50=10^15程度なのでlong longで
表すことができる。

コード

class CuttingBitString {

public:

bool ispossible(string s){
if(s[0]=='0')return false;

int n=s.size();
long long ret=0,p=1;
for(int i=n-1;i>=0;i--){
ret+=(s[i]-'0')*p;
p*=2;
}

if(ret==0)return false;
while(ret%5==0 && ret>0)ret/=5;

return ret==1;
}

int getmin(string S) {
int n=S.size();
int dp[n+1];

FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;

for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++)if(dp[j]!=1e+9){
if(ispossible(S.substr(j,i-j+1))){
dp[i+1]=min(dp[i+1],dp[j]+1);
}
}
}

return dp[n]==1e+9 ? -1 : dp[n];
}

};