TopCoder SRM590 Div1 Easy 250 FoxAndChess

概要

'L', 'R', '.' からなる文字列 begin と target が与えられる. begin から,

• 'L' を左の '.' と swap
• 'R' を右の '.' と swap

という操作で target を作れるか.

制約

$ 1 \le n \le 50 $

解法

• 各文字の個数は一致してなきゃいけない.
• 'L', 'R' が出てくる順番も一致していなきゃいけない.
• 左から $i$ 番目の 'L' 同士, 'R' 同士がマッチングする.
• 左/右にしか行けないという条件をチェック.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 242.37 pts

string FoxAndChess::ableToMove( string start, string goal ){
    const int n = size(start);
    string s, g;
    rep(i, n){
        if(start[i] != '.') s += start[i];
        if(goal[i] != '.') g += goal[i];
    }
    if(s != g) return "Impossible";
    vector<int> rs1, rs2;
    vector<int> ls1, ls2;
    rep(i, n){
        if(start[i] == 'R') rs1.emplace_back(i);
        if(start[i] == 'L') ls1.emplace_back(i);
        if(goal[i] == 'R') rs2.emplace_back(i);
        if(goal[i] == 'L') ls2.emplace_back(i);
    }
    repsz(i, rs1) if(rs1[i] > rs2[i]) return "Impossible";
    repsz(i, ls1) if(ls1[i] < ls2[i]) return "Impossible";
    return "Possible";
}