Topcoder SRM 572(Div.2) 参戦記

あんまり更新していませんが、生きています。コンテストにもちょいちょい参加しています。ただ、あんまり書いていないだけです。

250-Problem:最近のSRMのDiv.2Easyはとにかく解いてもらおうという感じに思えます。初心者の人がとっつきやすくて良いです。単純に「整数配列の総積の符号を答えよ」なので、順に見ていって、マイナスなら反転、0があれば0にする、を繰り返せば終わりです。

500-Problem:解けている人が少ないのですが、これは問題文が今ひとつだったからでしょうか。折角なので訳出してみます(適当に補ったりして、問題文を通りやすくしています)。

英小文字からなる文字列に対し、次の2つの操作を施し、文字列を変換することを考える。
操作A:z以外の小文字を1文字選び、それを1文字後ろの文字に変換する。即ち、aをbに、bをcに、...、yをzに変換する。
操作B:a以外の小文字を1文字選び、それを1文字前の文字に変換する。即ち、bをaに、cをbに、...、zをyに変換する。
貴方は両方の操作を任意の回数、任意の順序で施すことが出来る。また、操作Aを一度行うためにかかるコストnextCostと操作Bを一度行うためにかかるコストprevCostが与えられるものとする。また、最初の文字列startと最後の文字列goalも与えられる。これらの文字列は全て英小文字からなっており、同じ文字は含まれないものとする。この時、startからgoalに変換するための最小コストを求めよ。なお、変換不能な場合は-1を返せ。

と、こうなるのですが、この問題文だけだと変換不能な場合は見えません(私の解釈がまずいのか？)。テストケースで"ae"から"cb"へのケースで-1を返しているので、どうやら斜体下線にした条件が変換過程においても守られなければならない、という条件なのだと思うのですが…。

私は、変換中にもこの条件を満たさなければならないという仮定の下、解答を作りました。要するに変換前後で"交わり"がなければよいので、変換前後の大小関係が推移的であればよいと言い換えて解きました。(正解したので、この解釈は合っていると思います)

得点は615.5, 順位は26位/770名. Ratingは1072->1174.でした。この出来でこの順位はどうなんだ？


[Easy(C++),Accepted]

#include<iostream>
#include<vector>

using namespace std;

class EasyHomework{
public:
string determineSign(vector <int> A){
int P=1;
for(int i=0;i<A.size();i++){
if(A[i]<0) P*=-1;
else if(A[i]==0) P*=0;
else P*=1;
}
if(P==-1) return "NEGATIVE";
else if(P==0) return "ZERO";
return "POSITIVE";
}
};

[Medium(C++),Accepted]

#include<iostream>
#include<string>

using namespace std;

class NextOrPrev{
public:
int getMinimum(int nextCost, int prevCost, string start, string goal){
int num[32];

/*Count all num*/
for(int i=0;i<start.length();i++)
num[i]=goal[i]-start[i];

/*Check Change Possible?*/
for(int i=1;i<start.length();i++){
for(int j=0;j<i;j++){
if(start[i]<start[j] && goal[i]>goal[j]) return -1;
if(start[i]>start[j] && goal[i]<goal[j]) return -1;
}
}

int sum=0;
/*Calc sum*/
for(int i=0;i<start.length();i++){
if(num[i]<0)
sum+=-prevCost*num[i];
else
sum+=nextCost*num[i];
}
return sum;
}
};