WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM572 Div2 Medium "NextOrPrev"

問題

文字列に対し、下記の2つの操作を行える
Ope "Next" : 'z'以外の文字を1つ選び、その文字を次のように変える。(a->b b->c c->d ... )
Ope "Prev" : 'a'以外の文字を1つ選び、その文字を次のように変える。(z->y y->x x->w ... )
例)
aabc -> 操作 "Next" 'b' -> aacc
aabc -> 操作 "Prev" 'b' -> aaac
aabc -> 操作 "Next" 'a' -> bbbc

操作Nextにかかる費用、Prevにかかる費用が与えられている。

文字列startから文字列goalへ、費用が最小になるよう
2つの操作を行った時、その費用を返せ。
startからgoalへ変換できないときは-1を返せ。

また、startとgoalには同じ文字が2つ以上含んでいない。

制約

1 <= Next,Prevのコスト <= 1000
1 <= start,goalの文字数 <= 26

考えた事

a -> d
e -> c
みたいに、NextとPrevの操作で範囲が重なってしまうとダメ
a -> d
c -> e
みたいに、Next同士の操作だったら範囲が重なってもいい

あれ?NextとPrevの操作で範囲が重なるから
いったんPrevで逃がしといて、
Nextで持っていくみたいな操作って意味ないよね?

ってことは、最小費用になるか、変換できないか、になるな。

あれ?最後のSample通らない・・・

あ、
a -> e
b -> c
みたいに、同じ操作でも追い越さなきゃいけないようなのはダメだ~

ソースコード
class NextOrPrev {
public:
    int getMinimum(int nextCost, int prevCost, string start, string goal){
        int n = start.length();
        for( int i = 0; i < n; i++ ){
            for( int j = i + 1; j < n; j++ ){
                int si = start[i], gi = goal[i], sj = start[j], gj = goal[j];
                if( si > gi ) swap( si, gi );
                if( sj > gj ) swap( sj, gj );
                if( si < sj && gj < gi ) return -1;
                if( sj < si && gi < gj ) return -1;
            }
        }

        int dr[26];
        fill( dr, dr + 26, 0 );

        int res = 0;
        for( int i = 0; i < n; i++ ){
            int d = 1;
            int s = start[i] - 'a';
            int e = goal[i] - 'a' - 1;
            int cost = nextCost;
            if( start[i] > goal[i] ){
                d = -1;
                e = start[i] - 'a' - 1;
                s = goal[i] - 'a';
                cost = prevCost; 
            }
            for( int i = s; i <= e; i++ ){
                if( dr[i] != 0 && dr[i] != d ){
                    return -1;
                }
                dr[i] = d;
            }
            res += ( e - s + 1 ) * cost;
        }

        return res;            
    }
};