ferinの競プロ帳

競プロについてのメモ

SRM663 div1 easy ABBADiv1

考えたこと

  • とりあえず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;
//#define int ll

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";
  }
};