考えたこと
- とりあえずinitial→targetじゃなくて逆に戻していく動作を考える
- 先頭にBなら取り除いて残りを反転、末尾にAなら取り除くの2パターンがある
- 愚直にやると2Nくらいかかりそうだけど冷静に考えるとそこまでパターン数は多くない気がしてくる
- 2通りに派生しつづけるようなケースがなさそうな気持ちになる
- |init| = 1, |target| = 50のケースを何個か作って試しても一瞬で終わるしだめなケースが思い浮かばない
- 投げたら通った(は?)
- 解説を読んで冷静になって考えるとtargetの部分集合とその反転しか作られるケースはないので2乗オーダーくらいしかケースはない
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
class ABBADiv1 {
public:
string canObtain(string init, string target)
{
function<bool(string)> solve = [&](string s) -> bool {
if(s.size() < init.size()) return false;
if(s == init) return true;
bool ret = false;
if(s[0] == 'B') {
string t = s.substr(1);
reverse(ALL(t));
ret |= solve(t);
}
if(s.back() == 'A') {
s.pop_back();
ret |= solve(s);
}
return ret;
};
return solve(target) ? "Possible" : "Impossible";
}
};