ある文字列Iに，2つの操作が出来る．
- 文字列の最後に"A"を足す
- 文字列を反転して，最後に"B"を足す
文字列Iが文字列Tになるかを判定せよ
考察
愚直にIに操作していくと，2T.size()-I.size()で無理．しかしTから減らしていくには，一意しかない．末尾が"A"ならば，一つ前の状態をpreTとすると，T = preT+“A"となる．まと同様に，末尾が"B"ならば，T = reverse(preT) + "B"である．これを繰り返し，Iと同じsizeになった時に，同じかどうかで判定できる．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #line 5 "ABBA.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
class ABBA {
public:
string canObtain(string I, string T) {
while(T != I && T.size() > I.size()) {
if(T[T.size()-1] == 'A') {
T = T.substr(0,T.size()-1);
}else {
T = T.substr(0,T.size()-1);
reverse(T.begin(),T.end());
}
}
if(T == I) return "Possible";
return "Impossible";
}
};
|
コードを短く，シンプルにかける．本番中は誤読をしていて死んでいた．このある状態を目的の状態にする問題で，逆からやると上手くいく系はすぐ解けるようになりたい．