naoya_t@topcoder

過去問マラソン(#8): SRM150

19:36 |

２日休んだけど再開

Easy(250): InterestingDigits

• 241.50pt = 5'21''
  • テンプレートの中の余分なマクロを削除するのに時間がかかってもったいない
• passed system test

#define pb  push_back

class InterestingDigits {
  int b;
  bool p(int n){
    if (b*b % n == 1 && b % n == 1) return true;
    return false;
  }
 public:
  vector <int> digits(int base) {
    b=base;
    vector<int> res;
    for(int n=1;n<base;n++) if (p(n)) res.pb(n);
    return res;
  }
};

Medium(500): StripePainter

• DPで一見簡単そうなんだけど
• 試行錯誤x試行錯誤x試行錯誤
  • いま何色に塗られているか
  • 左端の色で最長マッチ、ではSample #4でうまく行かない
  • どこまで塗るかをDPで全パターン探索する感じで
• 168.12pt (= 101'30'') 全然間に合ってない
• passed system test

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

class StripePainter {
  map<pair<vector<char>,string>,int> memo;
  
  int sub(vector<char> curr, string goal){
    int l=sz(goal); if(l==0) return 0;

    pair<vector<char>,string> key = cons(curr,goal);
    if (found(memo,key)) return memo[key];

    {
      int b=0, e=l;
      FOR(i,0,l-1) { if (goal[i]==curr[i]) b++; else break; }
      RFOR(i,b,l-1) { if (goal[i]==curr[i]) e--; else break; }
      if (b!=0 || e!=l) {
        curr = vector<char>(curr.begin()+b, curr.end()-(l-e));
        goal = goal.substr(b,e-b);
      }
    }
    l=sz(goal);
    if(l==0) return memo[key]=0;
    if(l==1) return memo[key]=1;

    int c0=goal[0];
    vector<int> ats;
    rep(i,l) if(goal[i]==c0 && curr[i]!=c0) ats.pb(i);

    int mincnt = INT_MAX;
    tr(ats,it){
      int x = *it + 1;
      int cnt = 0;
      if (x > 0) {
        if (x == 1) cnt++;
        else cnt += 1+sub( vector<char>(x,c0), goal.substr(0,x) );
      }
      if (l-x > 0) {
        if (l-x == 1) cnt++;
        else cnt += sub( vector<char>(curr.begin()+x,curr.end()), goal.substr(x,l-x) );
      }
      mincnt = min(cnt,mincnt);
    }
    return memo[key]=mincnt;
  }
 public:
  int minStrokes(string stripes) {
    return sub(vector<char>(sz(stripes),' '), stripes);
  }
};

Hard(1000):

-