問題
http://community.topcoder.com/stat?c=problem_statement&pm=10054&rd=13510
２つの操作の列が与えられる。
操作は以下の２種類。
・type a 与えられたアルファベット（ここではa）をタイプする
・undo x x秒前までの操作を取り消す。
このとき、最後のこった文字列を求める。
解き方
操作は右側の操作によって打ち消されるので、
右側の方から取り消される操作を調べていく。
残ったタイプの操作が最後に残る文字列となる。
コード
class Undo {
public: string getText(vector<string> commands, vector<int> time) {
int n=commands.size();
int used[n];
memset(used,0,sizeof(used));
for(int i=n-1;i>=0;i--)if(!used[i]){
stringstream out(commands[i]);
string c;
int num;
out>>c>>num;
if(c=="undo"){
int e=time[i]-num;
used[i]=1;
for(int j=i-1;j>=0;j--)if(e<=time[j])used[j]=1;
}
}
string ret="";
for(int i=0;i<n;i++)if(!used[i]){
stringstream out(commands[i]);
string tmp;
char ch;
out>>tmp>>ch;
ret+=ch;
}
return ret;
}
};
public: string getText(vector<string> commands, vector<int> time) {
int n=commands.size();
int used[n];
memset(used,0,sizeof(used));
for(int i=n-1;i>=0;i--)if(!used[i]){
stringstream out(commands[i]);
string c;
int num;
out>>c>>num;
if(c=="undo"){
int e=time[i]-num;
used[i]=1;
for(int j=i-1;j>=0;j--)if(e<=time[j])used[j]=1;
}
}
string ret="";
for(int i=0;i<n;i++)if(!used[i]){
stringstream out(commands[i]);
string tmp;
char ch;
out>>tmp>>ch;
ret+=ch;
}
return ret;
}
};
Share this
Related Posts
SRM 495 DIV1 Easy - ColorfulCards
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11302&rd=14424
解き方
すべての状態について、満たすすべての整数を調- SRM 402 DIV1 Easy - RandomSort
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8590&rd=12174
解き方
全探索可能。
配列の状態を持つのでdpではなく
- SRM 577 DIV1 Easy - EllysRoomAssignmentsDiv1
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12514&rd=15497
解き方
部屋の数Rから、部屋への割り当てが行われる回
- SRM 460 DIV1 Easy - TheQuestionsAndAnswersDivOne
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146
解き方
数が小さいので全探索可能。
すでに答えた人の