SRM 374 DIV1 Easy - SyllableSorting

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8374&rd=10793

解き方

文字列操作の問題。
問題文の最後の比較条件を見落としてしまった。。

コード

class SyllableSorting {

public:

bool ispossible(char cur){
char ch[]={'a','e','i','o','u'};
FORE(i,0,5)if(cur==ch[i])return false;
return true;
}

vector<string> calc(string w){
int n=w.size();
vector<string> ans;

int at=0;
while(at<n){
string str="";
int flag=0;
while(at<n){
if(ispossible(w[at])){
if(flag==0)str+=w[at++];
else break;
}else{
str+=w[at++];
flag=1;
}
}
ans.push_back(str);
}

return ans;
}

vector<string> sortWords(vector<string> words) {
int n=words.size();
vector<pair<pair<vector<string>,vector<string> >,string> > p;

FORE(i,0,n){
vector<string> cur=calc(words[i]);
vector<string> cur2=cur;
sort(all(cur));
p.push_back(make_pair(make_pair(cur,cur2),words[i]));
}
sort(all(p));

vector<string> ans;
FORE(i,0,n)ans.push_back(p[i].second);

return ans;
}

};

SRM 392 DIV1 Easy - TwoStringMasks

問題

http://community.topcoder.com/stat?c=problem_statement&pm=8706&rd=11126

解き方

仮の文字列を作る。
＊にあたる共通の部分は？で埋めて、s1とs2について同じ長さの２つの文字列を作る。
各文字について一致していればその文字列は有効になるのでそれが答えになる。
そのような文字列が存在しなければimpossibleとなる。

コード

class TwoStringMasks {

public: string shortestCommon(string s1, string s2) {
for(int l1=0;l1<=200;l1++){
int l2=s1.size()+l1-s2.size();
if(l2<0)continue;

string p1="";
FORE(i,0,s1.size()){
if(s1[i]=='*')FORE(j,0,l1)p1+='?';
else p1+=s1[i];
}

string p2="";
FORE(i,0,s2.size()){
if(s2[i]=='*')FORE(j,0,l2)p2+='?';
else p2+=s2[i];
}

string ans="";
int valid=1;
FORE(i,0,p1.size()){
char ch;
if(p1[i]=='?')ch=p2[i];
else if(p2[i]=='?')ch=p1[i];
else if(p1[i]==p2[i])ch=p1[i];
else{
valid=0;
break;
}
ans+=ch;
}
if(valid)return ans;
}

return "impossible";
}

};

SRM 579 DIV1 Easy - UndoHistory

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499

解き方

前の文字列からそのまま続けられる時はその場合と、
以前の部分文字列を使う場合のうち最小のものを採用していけばよい。

コード

class UndoHistory {

public: int minPresses(vector<string> lines) {
int n=lines.size();
int ret=n;

string prev="";
FORE(i,0,n){
int cost=1e+9;

if(prev.size()<=lines[i].size()){
int valid=1;
FORE(j,0,prev.size())if(prev[j]!=lines[i][j])valid=0;
if(valid)cost=min(cost,(int)lines[i].size()-(int)prev.size());
}

FORE(j,0,i){
int tmp=0;
for(int k=0;k<lines[i].size() && k<lines[j].size();k++){
if(lines[i][k]==lines[j][k])tmp++;
else break;
}
cost=min(cost,(int)lines[i].size()-tmp+2);
}

ret+=cost;
prev=lines[i];
}

return ret;
}

};

SRM 649 DIV1 Easy - Decipherability

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13656&rd=16313

・a～ｚから成る文字列が与えられる。
・この文字列から、任意のK個の文字を取り除いたとき、それがどの箇所か
　特定できればCertain、特定できなければUncertainを返す。

解き方

どのような文字列が削除されると特定できないかの法則を探す。

まず、すべての文字列が削除された場合は特定できる。

次に、文字列の対称性を考えた場合に、a***aの文字列があった場合
Kが４以上だとaだけを残すことができ、どちらを消したか特定できない。

このような同じ文字ではさまれたサブ文字列すべてに対して判定を行い
ひとつでもあてはまれば特定できない文字列となる。

コード

class Decipherability {

public: string check(string s, int K) {
int n=s.size();

if(K==n)return "Certain";

FORE(i,0,n)FORE(j,i+1,n)if(s[i]==s[j]){
if(j-i<=K)return "Uncertain";
}

return "Certain";
}

};

SRM 654 DIV1 Easy - SquareScores

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318

・ある文字列が与えられる。
・文字列はaからzのアルファベット、もしくは?から成る。
・?の場合、aからzの任意の文字列が入る。

・また、ある文字列が与えられた時、そのスコアは連続する文字列の数となる。
　（例）aaabaのスコア aが４つ,aaが２つ、aaaが1つ、bが１つで8
・このとき、与えられた文字列のスコアの期待値を求める。

解き方

スコアがabc・・ではなく、aaa,bbbなど連続した文字列だけでよいので、
実は全探索が可能。

各部分文字列の位置について、aからzのすべての文字列が連続するときの
期待値を求めてあげて足していけばよい。

計算量はO(10^3 * 10~3 * 26)=O(10^7*2.6)なので間に合う。

まずは全探索できないか考える原則にのっとる。

コード

class SquareScores {

public: double calcexpectation(vector<int> p, string s) {
int n=s.size(),m=p.size();
double prob[m];

double ret=0.0;
FORE(i,0,n){
FORE(j,0,m)prob[j]=1.0;
FORE(j,i,n){
if(s[j]=='?'){
FORE(k,0,m)prob[k]*=p[k]*0.01;
}
else{
FORE(k,0,m)if(k!=s[j]-'a')prob[k]=0.0;
}
FORE(k,0,m)ret+=prob[k];
}
}

return ret;
}

};