naoya_t@topcoder

過去問マラソン(#2):SRM145

過去問マラソン | 12:45 |

過去問マラソン2日目。

Easy(250): Bonuses

• 前にも見たかなあ
• Sample caseで答えが合わず悩んでたら、小数点以下を切り捨てたパーセンテージで上から数えててたorz
• 12'32''遅すぎ
• systest一発

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)

class Bonuses {
 public:
  vector<int> getDivision(vector<int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<int> added(n,0);
    while (left>0) {
      int maxpt=0,maxat=-1;
      // rep(i,n){if(added[i]==0&&maxpt<pd[i]) maxpt=pd[i],maxat=i;} // !oops
      rep(i,n){if(added[i]==0&&maxpt<points[i]) maxpt=points[i],maxat=i;}
      added[maxat]++; left--;
    }
    rep(i,n) pd[i]+=added[i];
    return pd;
  }
};

てか後半はソートを使って簡単に書きたい。やり直し

• ソート順が小さい順（昇順）なことを感覚的に捉えられてなくて、テスト動かしてみて確認してるのが時間もったいない

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).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 Bonuses {
 public:
  vector<int> getDivision(vector <int> points) {
    int n=sz(points);
    int sum=0;rep(i,n)sum+=points[i];

    vector<int> pd(n);
    int left=100;
    rep(i,n){pd[i]=100*points[i]/sum;left-=pd[i];}

    vector<i_i> pp(n);
    rep(i,n)pp[i]=cons(-points[i],i);
    sort(all(pp));
    rep(i,left) pd[cdr(pp[i])]++;
    return pd;
  }
};

Medium(600):VendingMachine

• 見たことある気もする
• 実装するだけなんですが
  • コード書き始めるのはもうちょっと問題を咀嚼してからでいいかも。焦っても意味ない
• max_element()で何か変な値が出るので延々悩んでたら、カラムの数にprices[0].size() が入ってた。これはカラム数ではなく文字数！
  • ちょっとiteratorの扱いに慣れてきたぞ
• しかし74'38''...遅い
• systestは一発
  • Easyすっ飛ばしてこれだけ解いてsubmitすれば218.51点はとれた計算
  • Easy, Mediumともに解ける問題なので、２問とも時間内にぜひともクリアしたい

vector<string> split(string str, int delim=' '); // 略

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

int stoi(string s){ return atoi(s.c_str()); }

class VendingMachine {
 public:
  int motorUse(vector <string> prices, vector <string> purchases) {
    int n_shelves=sz(prices), n_columns;
    // n_columns = sz(prices[0]); // !oops
    vector<vector<int> > table(n_shelves);
    vector<int> pricesum;
    rep(sh,n_shelves){
      table[sh] = map_atoi(split(prices[sh])); // sh[i][s>=3] : 1..10000
      if (sh==0) {
        n_columns = sz(table[sh]);
        pricesum.resize(n_columns); rep(i,n_columns) pricesum[i]=0;
      }
      rep(col,n_columns) pricesum[col] += table[sh][col];
    }

    int motorrun = 0;
    int last_t = 0;

    // autorot
    int curr_col = 0, new_col, diff;

    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    set<i_i> boughts;
    rep(i,sz(purchases)){
      vector<string> a1 = split(purchases[i],':'), a0 = split(a1[0],',');
      int shelf=stoi(a0[0]), column=stoi(a0[1]), time=stoi(a1[1]);

      int lapse = time - last_t;
      if (lapse>=5) {
        // autorot at last_t
        vector<int>::iterator max_at = max_element(all(pricesum));
        new_col = max_at - pricesum.begin();
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }

      {
        new_col = column;
        diff = abs(new_col - curr_col);
        motorrun += min(diff, n_columns-diff);
        curr_col = new_col;
      }
      
      i_i key = cons(shelf,column);
      if (found(boughts,key)) return -1;
      boughts.insert(key);

      pricesum[column] -= table[shelf][column];
      table[shelf][column] = 0;
      
      last_t = time;
    }

    // last autorot
    {
      vector<int>::iterator max_at = max_element(all(pricesum));
      new_col = max_at - pricesum.begin();
      diff = abs(new_col - curr_col);
      motorrun += min(diff, n_columns-diff);
      curr_col = new_col;
    }

    return motorrun;
  }
};

Hard(1000): HillHike

(to be continued)

来年の為に

23:57 |

今年はSRM皆勤したけどほとんど練習出来なかった。Easyがsubmitできないなんて色々終わってるので過去問で練習したい。

• Practice Roomにある過去問はSRM144から
• 毎日１回分解いてたら１年で終わる量
• やった事のある問題も当然あるけど何度でもやる。というか前より速くなってるべき

というわけでSRM144から。方針はDIV1の

• Easyは必須
• Mediumも解く
• Hardも問題は読む

という感じで始めたい。

過去問マラソン(#1):SRM144

過去問マラソン | 23:57 |

得点配分が今と違う感じ

Easy(300): BinaryCode

• 前にやった記憶あり
• こういうのすぐにコーディングすると空中分解するタイプ
• とりあえず解けるんだけどchar[]で解いてるしここはSTL使ってなんとかしたい。で
  • vector<char> で stringが初期化できること
  • string で vector<char> が初期化できること
• を今頃知った。
• 入力長が1,2の場合が例外的なので気をつけて
  • pの両側に門番(0)をつけた方が条件分岐なくて良いので楽。最後のpに非0が来たら"NONE"

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class BinaryCode {
 public:
  string guess(string m,int p0){
    int n=sz(m);
    vector<char> q(all(m)), p(n+2);
    rep(i,n) q[i]-='0'; p[0]=0, p[1]=p0;//, p[n+1]=0;
    FOR(i,1,n+1) p[i+1]=q[i-1]-p[i]-p[i-1];
    if (p[n+1]!=0) return "NONE";
    
    FOR(i,1,n) { if(p[i]<0||1<p[i]) return "NONE"; else p[i]+='0'; }
    return string(p.begin()+1, p.end()-1);
  }
  vector <string> decode(string message) {
    vs ans;
    ans.pb( guess(message,0) );
    ans.pb( guess(message,1) );
    return ans;
  }
};

Medium(550): Lottery

• 前にも見たかも
• 文字列パース。というかsplit
• sortedはDP
• わりとすんなり書けた（と言っても25'16''）
• system test一発OK

typedef long long ll;
typedef vector<string> vs;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
typedef pair<int,int> i_i;

// 自作split
vector<string> split(string str, string delim) {
  // 略
}
vector<string> split(string str, int delim=' ') {
  // 略
}

bool atob(string s){ return s[0]=='T'; }

ll pow(int x,int y){ // x^y
  ll ans=1LL; rep(i,y) ans *= (ll)x; return ans;
}
ll fac(int x,int y){ // x!/(x-y)!
  ll ans=1LL; rep(i,y) ans *= (ll)(x--); return ans;
}
class Lottery {
  map<i_i,ll> m1, m2;
  ll sub_sorted_unique(int choices,int blanks){ // 1 2 3 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m1,key)) return m1[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted_unique(choices-i-1,blanks-1);
    }
    m1[key]=sum;
    return sum;
  }
  ll sub_sorted(int choices,int blanks){ // 1 1 2 ...
    if (blanks==0) return 1;
    i_i key=cons(choices,blanks);
    if(found(m2,key)) return m2[key];
    ll sum=0LL;
    rep(i,choices){
      sum += sub_sorted(choices-i,blanks-1);
    }
    m2[key]=sum;
    return sum;
  }
  ll num(string name, int choices, int blanks, bool sorted, bool unique) {
    // number of valid lottery tickets for that game...
    // choices: 10-100 ... [1..choices]
    // blanks: 1-8
    ll cnt = 0LL;

    if (sorted) {
      if (unique) {
        // 1 2 3 4 5
        cnt = sub_sorted_unique(choices,blanks);
      } else {
        // 1 1 2 3 3
        cnt = sub_sorted(choices,blanks);
      }
    } else {
      if (unique) {
        // 3 2 1 5 4
        cnt = fac(choices,blanks);
      } else {
        // 3 3 1 2 1
        cnt = pow(choices,blanks); // 1e2 ^ 8 = 1e16
      }
    }
/*   
    printf("name:%s choices:%d blanks:%d sorted:%s unique:%s => %lld\n",
           name.c_str(), choices, blanks, sorted?"YES":"NO", unique?"YES":"NO",
           cnt);
*/
    return cnt;
  }
 public:
  vector <string> sortByOdds(vector<string> rules) {
    m1.clear(); m2.clear();
    
    vector<pair<ll,string> > res;
    tr(rules,st){
      vs a1 = split(*st,": ");
      string name = a1[0];
      vs a2 = split(a1[1],' ');
      int choices = atoi(a2[0].c_str()), blanks = atoi(a2[1].c_str());
      bool sorted = atob(a2[2]), unique = atob(a2[3]);

      res.pb(cons(num(name,choices,blanks,sorted,unique),name));
    }
    sort(all(res));// reverse(all(res));
    vs ans;
    tr(res,it) ans.pb(it->second);
    return ans;
  }
};

Hard(1100): PenLift

• プロッタ懐かしい
• とか言ってる場合じゃなくて
• とりあえずグラフに変換
  • 同じ向きの繋がった（or 重なった）線分を検出し、union-findしといて後でまとめる
  • 線分を交差点で区切り、nodeとarcを抽出
  • union-findして島分割
  • n回重ね書きするのでarcの本数を各n倍にする
  • それぞれの島が何筆書きになるか、で行ける
    • （ここまでで３時間半。sample case#5がちゃんと解けてない！intersection判定にバグあり？）
  • 結局４時間半かかって解けた
  • system test一発OK
  • 以下駄コード
    • cons,car,cdr,caar,cadr,cdar,cddrとかまあ気にしないで

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<ll,ll> ll_ll;
typedef pair<double,double> d_d;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '¥0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

typedef pair<int,int> point;
typedef pair<point,point> segment;

vector<segment> segments;
vector<bool> deleted;
vector<int> dirs;

int dir(const segment& s){
  point p1 = car(s), p2 = cdr(s);
  if (p1==p2) return -1;
  if (car(p1)==car(p2)) // x1=x2
    return (p2.second > p1.second)?1:3;
  else
    return (p2.first > p1.first)?0:2;
}
segment rev(const segment& s){
  return cons(cdr(s),car(s));
}

segment joint(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int dir = dirs[i]; // assume dirs[i]=dirs[j]
  if (dir==0) { // horizontal
    int y = cdar(s1);
    int x0 = min( caar(s1),caar(s2) ),
        x1 = max( cadr(s1),cadr(s2) );
    return cons(cons(x0,y),cons(x1,y));
  } else {
    int x = caar(s1);
    int y0 = min( cdar(s1),cdar(s2) ),
        y1 = max( cddr(s1),cddr(s2) );
    return cons(cons(x,y0),cons(x,y1));
  }
}

point cross(int i, int j){
  segment s1 = segments[i], s2 = segments[j];
  int d1 = dirs[i], d2 = dirs[j];
  if (d1==1 && d2==0) return cross(j,i);
  int y=cdar(s1);
  if (cdar(s2) <= y && y <= cddr(s2)) {
    FOR(x,caar(s1),cadr(s1)) {
      // x,y
      if(x==caar(s2)) return cons(x,y);
    }
  }
  return cons(INT_MAX,INT_MAX);
}

bool oddp(int n){
  return (n & 1)? true : false;
}

class UnionFind {
  vector<int> data;
 public:  
  UnionFind(int size) : data(size, -1) { }
  
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

class PenLift {
 public:
  int numTimes(vector<string> segs, int n) {
    int N = sz(segs);
    segments.resize(N);
    deleted.resize(N);
    dirs.resize(N);
    
	rep(i,N){ // segment_id
      vector<int> t = map_atoi(split(segs[i]));
      segment s = cons(cons(t[0],t[1]), cons(t[2],t[3]));
      if (dir(s) >= 2) s = rev(s);
      segments[i] = s; deleted[i] = false;
      dirs[i] = dir(s);
    }
    
    // joint
    UnionFind uf0(N); set<int> jointed;
    FOR(i,0,N-2){
      FOR(j,i+1,N-1){
        if (dirs[i]==dirs[j]) {
          if (dirs[i]==0) { // h
            int yi = cdar(segments[i]), yj = cdar(segments[j]);
            if (yi != yj) continue;
            int x0 = caar(segments[i]), x1 = cadr(segments[i]),
                x2 = caar(segments[j]), x3 = cadr(segments[j]);
            if (x0>x2) { swap(x0,x2); swap(x1,x3); } // x0 <= x2
            if (x2 <= x1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          } else { // v
            int xi = caar(segments[i]), xj = caar(segments[j]);
            if (xi != xj) continue;
            int y0 = cdar(segments[i]), y1 = cddr(segments[i]),
                y2 = cdar(segments[j]), y3 = cddr(segments[j]);
            if (y0>y2) { swap(y0,y2); swap(y1,y3); } // y0 <= y2
            if (y2 <= y1) {
              uf0.unionSet(i,j);
              jointed.insert(i); jointed.insert(j);
            }
          }
        }
      }
    }
    map<int,set<int> > joint_isle;
    tr(jointed,it){
      int root = uf0.root(*it);
      if (!found(joint_isle,root)) {
        set<int> s;
        joint_isle[root] = s;
      }
      //if (*it != root)
      joint_isle[root].insert(*it);
    }

    tr(joint_isle,it) {
      int root=it->first;
      if (dirs[root] == 0) { // horizontal
        int y = cdar(segments[root]);
        int xmin = INT_MAX, xmax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int x0 = caar(s), x1 = cadr(s);
          if (x0 > x1) swap(x0,x1);
          xmin = min(xmin,x0);
          xmax = max(xmax,x1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(xmin,y),cons(xmax,y));
        deleted[root] = false;
      } else { // vertical
        int x = caar(segments[root]);
        int ymin = INT_MAX, ymax = INT_MIN;
        tr(it->second,jt) {
          segment s = segments[*jt];
          int y0 = cdar(s), y1 = cddr(s);
          if (y0 > y1) swap(y0,y1);
          ymin = min(ymin,y0);
          ymax = max(ymax,y1);
          deleted[*jt] = true;
        }
        segments[root] = cons(cons(x,ymin),cons(x,ymax));
        deleted[root] = false;
      }
    }
    // cross
    vector<set<point> > seps(N,set<point>());
    FOR(i,0,N-2){
      if (deleted[i]) continue;
      
      FOR(j,i+1,N-1){
        if (deleted[j]) continue;
        
        if (dirs[i]!=dirs[j]) {

          point nx = cross(i,j);
          if (car(nx)==INT_MAX) continue;
          seps[i].insert(nx);
          seps[j].insert(nx);
        }
      }
    }

    rep(segment_id,N) {
      int sepsz = sz(seps[segment_id]);
      if (sepsz > 0) {
        deleted[segment_id] = true;
        
        if (dirs[segment_id]==0) { // horizontal
          int y = cdar(segments[segment_id]);
          set<int> xs;
          xs.insert(caar(segments[segment_id]));
          xs.insert(cadr(segments[segment_id]));
          tr(seps[segment_id],it) xs.insert(it->first);
          vector<int> xsv(all(xs));
          sort(all(xsv));
          rep(k,sz(xsv)-1) {
            segment sk = cons(cons(xsv[k],y),cons(xsv[k+1],y));
            segments.pb(sk); deleted.pb(false);
          }
        } else { // vertical
          int x = caar(segments[segment_id]);
          set<int> ys;
          ys.insert(cdar(segments[segment_id]));
          ys.insert(cddr(segments[segment_id]));
          tr(seps[segment_id],it) ys.insert(it->second);
          vector<int> ysv(all(ys));
          sort(all(ysv));

          rep(k,sz(ysv)-1) {
            segment sk = cons(cons(x,ysv[k]),cons(x,ysv[k+1]));

            segments.pb(sk); deleted.pb(false);
          }
        }
      }
    }

    // 両端登録
    map<point,set<int> > nodes; // points[point] = { segment_ids }

    rep(segment_id,sz(segments)){
      if (deleted[segment_id]) continue;
      vector<point> n(2);
      n[0]=car(segments[segment_id]);
      n[1]=cdr(segments[segment_id]);

      rep(node_id,2) {
        if(found(nodes,n[node_id])) {
          nodes[n[node_id]].insert(segment_id);
        } else {
          set<int> s; s.insert(segment_id);
          nodes[n[node_id]] = s;
        }
      }
    }

    UnionFind uf(sz(segments));

    tr(nodes,nt){
      set<int> arcs = nt->second;
      vector<int> av(all(arcs)); FOR(i,1,sz(av)-1) uf.unionSet(av[0],av[i]);
    }

    map<int,int> isles;
    rep(i,sz(segments)) {
      if (deleted[i]) continue;
      int root = uf.root(i);
      if (!found(isles,root)) isles[root] = 0;
    }

    // again
    tr(nodes,nt){
      point node = nt->first;
      set<int> arcs = nt->second;
      vector<int> av(all(arcs));
      int root = uf.root(av[0]);
      if (oddp(sz(arcs)*n)) isles[root]++;
    }
    tr(isles,it) { it->second /= 2; }

    int ans = sz(isles)-1;
    tr(isles,it) {
      if (it->second == 0) continue;
      ans += it->second - 1;
    }
   
    return ans;
  }
};

SRM456 Hard: FunctionalEquation

きょうの復習, 過去問 | 17:38 |

寝る前にちょっと考えた

• f(x)=ax+b な形だとa=1,b=(C-1)/2になってしまってCが偶数のときにf(x)がintegerにならなくてアウト
• f(x)=ax^2 + bx + c な形だとa=0で結局同上
• f(x)=Σa_ix^i で考えると... 寝落ち

SRM456 Medium: CutSticks

きょうの復習, 過去問 | 20:46 |

• なんか最初単峰性の何かを想像してて、どこで最大になるか求めようとしていた
• 既存の棒の長さを順番に試していって、どこまで行けるか（というか求める値がどことどこの間か）という問題に脳内修正
• ということは要は任意の値でどこまで行けるか、に脳内修正
• ま、二分探索さ。最初から分かっていたさｗ
• どこまで「何が」行けるかの計算に悩んでてごにょごにょしてるうちに時間切れ
• Challenge Phase無視
• Practice room
  • 最初の棒の本数(N)が多いときに変な値が出る → 二分探索の最小値が小さすぎて、割り算した結果がINT_MAXより大きくなる → 無限大表現に INT_MAX/N を使うか（※素直にlong longにしとけばいいものを）
  • 最初の本数が少ないときに小さい値が出る → 大きい棒を切ることで順位が変わるのにstick[K]（※並べ替え済）を返していた。お馬鹿
  • Cが大きいときに変な値が出る →そろそろlong longにしないと無理ですか
  • 答えが1e8みたいに大きくなる時に二分探索が止まらない → 終了条件がhi-lo>1e-9とか駄目ですってば
  • ５度目の正直でpassed

  続きを読む

SRM456 Easy: SilverDistance

きょうの復習, 過去問 | 20:46 |

• 45度傾けたら超簡単だった
• 格子点以外への行き方が１通りしかない
• マンハッタン距離 + 格子点でなければ+1

続きを読む

SRM455 Easy(300): DonutsOnTheGridEasy

過去問 | 22:00 |

• 問題激しく読み違えてた...ドーナツが幾つ取れるか数えようとしてた。重箱状の階層の深さの最大を求めるだけだった。

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

// memoize..
char z[50][50][51][51], mp[50][50][51][51];

class DonutsOnTheGridEasy {
  vector<string> gr;
  int R,C;
  
  int isZeroShape(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (z[r][c][h][w]>=0) return z[r][c][h][w]; // memo

    int re=1;
    
    rep(j,h) { int y=r+j;
      if (gr[y][c]=='.') {re=0; goto end;}
      if (gr[y][c+(w-1)]=='.') {re=0; goto end;}
    }
    rep(i,w) { int x=c+i;
      if (gr[r][x]=='.') {re=0; goto end;}
      if (gr[r+(h-1)][x]=='.') {re=0; goto end;}
    }
 end:
    return z[r][c][h][w] = re;
  }

  int sub(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (mp[r][c][h][w]>=0) return mp[r][c][h][w]; // memo

    int ct=0; if (isZeroShape(r,c,h,w)) ct=1+sub(r+1,c+1,h-2,w-2);
    FOR(hj,1,h-1) ct = max(ct, max(sub(r,c,hj,w),sub(r+hj,c,h-hj,w)));
    FOR(wj,1,w-1) ct = max(ct, max(sub(r,c,h,wj),sub(r,c+wj,h,w-wj)));

    mp[r][c][h][w] = ct;
    return ct;
  }
 public:
  int calc(vector<string> grid) {
    R=sz(grid), C=sz(grid[0]);
    gr = grid;

    // clean up
    memset(z,255,sizeof(z)); memset(mp,255,sizeof(mp));

    return sub(0,0,R,C);
  }
};

SRM456

13:53 |

続きを読む

Member SRM455

13:55 |

12.17+.2009

あとで書く書く

続きを読む

SRM454

12:26 |

12.05+.2009

続きを読む