2013 TCO Round2C

TopCoder

Easy (250)　0
Medium (550)　0
Hard (1000)　0
Challenge　+150
結果　332位　2141→2105

250で最短距離dを求めた後に、d-1を答えにしている人がいて、チャレンジで150点稼いだ。Round3進出は無理でもTシャツを貰えるかもと思っていたら、自分の250が落ちた。何で最短距離を求める処理を間違えたのだろう……。

SRM572 Div2 Medium(500) NextOrPrev

TopCoder

NextOrPrev

ae→{0,1}, acb→{0,2,1}のように、各文字の文字列中での順位を表す配列を考える。startとgoalでの配列が一致していれば変換可能、一致していなければ途中で同じ文字になってしまうので不可能。変換可能なら貪欲に変換すれば良い。

#include <string>
#include <vector>
using namespace std;

//  各文字の文字列中での辞書順を返す
vector<int> Rank( string w )
{
    int n = (int)w.size();
    vector<int> R(n);
    for ( int i=0; i<n; i++ )
        for ( int j=0; j<n; j++ )
            if ( w[j]<w[i] )
                R[i]++;
    return R;
}

class NextOrPrev{public:
int getMinimum( int nextCost, int prevCost, string start, string goal )
{
    if ( Rank(start)!=Rank(goal) )
        return -1;

    int ans = 0;
    for ( int i=0; i<(int)start.size(); i++ )
    {
        if ( start[i]<goal[i] )
            ans += nextCost*(goal[i]-start[i]);
        if ( start[i]>goal[i] )
            ans += prevCost*(start[i]-goal[i]);
    }

    return ans;
}};

SRM572 Div2 Easy(250) EasyHomework

TopCoder

EasyHomework

#include <vector>
#include <string>
using namespace std;

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