naoya_t@topcoder

Kurukshetra 2010 Online Programming Contest

kurukshetra2010 | 18:07 |

http://www.kurukshetra.org.in/

お誘いが来てたので後でちょっと覗いてみる

Hi . Your credentials at Project Euler tells us that you have a flair for math-coding . We gladly invite you to take part in Athena - the on-line MATH-CODING contest of Kurukshetra 2010, an International Techo-Management by College Of Engineering Guindy , Anna University , Chennai , India organized under the patronage of UNESCO !!

catch the action at www.athena.kurukshetra.org.in

Exciting prizes to be won !!

Contest date : 8th January

Contest time : 9:00 P.M IST

過去問マラソン(#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):

-