Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-19

PKU 3809 -- Twenty Questions

| 19:25 | PKU 3809 -- Twenty Questions - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3809 -- Twenty Questions - Wrong Answer -- japlj PKU 3809 -- Twenty Questions - Wrong Answer -- japlj のブックマークコメント

311 でメモ化再帰した。TLE厳しい感じ。


#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int pow3[11], obj[128], memo[200000];
int b, n;

int rec(int st, int cand, int mask, int bits)
{
  if(memo[st]>=0) return memo[st];
  if(cand <= 1) return memo[st] = 0;
  int& ret = memo[st];
  ret = n;
  for(int i=0; i<b; ++i) {
    if(st/pow3[i]%3==0) {
      int cnt = 0;
      for(int k=0; k<n; ++k) {
	bool ok = (obj[k] & (mask | (1<<i))) == bits;
	if(ok) cnt++;
      }
      if(cnt == 0 || cnt == cand) continue;
      ret = min(ret, 1 +
		max(rec(st+pow3[i], cnt, mask|(1<<i), bits),
		    rec(st+pow3[i]*2, cand-cnt, mask|(1<<i), bits|(1<<i))));
    }
  }
  return ret;
}

int main()
{
  pow3[0] = 1;
  for(int i=1; i<=10; ++i) pow3[i]=pow3[i-1]*3;
  while(scanf("%d%d", &b, &n), b||n) {
    for(int i=0; i<n; ++i) {
      char s[12];
      scanf("%s", s);
      obj[i] = 0;
      for(int j=0; j<b; ++j) obj[i]=obj[i]*2+s[j]-'0';
    }
    memset(memo, -1, sizeof(memo));
    printf("%d\n", rec(0, n, 0, 0));
  }
  return 0;
}

PKU 3805 -- Separate Points

| 18:33 | PKU 3805 -- Separate Points - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3805 -- Separate Points - Wrong Answer -- japlj PKU 3805 -- Separate Points - Wrong Answer -- japlj のブックマークコメント

凸包とって全部の線を試す。一本の線の上に点がいくつもある場合を考えて ccw を多少いじる。


#include<cstdio>
#include<complex>
#include<algorithm>

using namespace std;

typedef complex<int> pt;
namespace std {
  bool operator < (const pt& a, const pt& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

int cross(const pt& a, const pt& b) {
  return imag(conj(a)*b);
}
int dot(const pt& a, const pt& b) {
  return real(conj(a)*b);
}
int ccw(pt a, pt b, pt c) {
  b -= a; c -= a;
  if(cross(b,c)>0) return 1; if(cross(b,c)<0) return -1;
  if(dot(b,c)<0) return 0; if(norm(b)<=norm(c)) return -2;
  return 0;
}

int convex_hull(pt *ps, int n)
{
  int k=0;
  pt ch[200];
  sort(ps, ps+n);
  for(int i=0; i<n; ch[k++]=ps[i++])
    while(k>=2 && ccw(ch[k-2],ch[k-1],ps[i])<=0) --k;
  for(int i=n-2, t=k+1; i>=0; ch[k++]=ps[i--])
    while(k>=t && ccw(ch[k-2],ch[k-1],ps[i])<=0) --k;
  for(int i=0; i<k-1; ++i) ps[i] = ch[i];
  return k-1;
}

int main()
{
  int n, m;
  while(scanf("%d%d", &n, &m), n||m) {
    pt p[200];
    for(int i=0; i<n+m; ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      p[i] = pt(x, y);
    }
    if(n>=3 && m>=3) {
      int N = n;
      n = convex_hull(p, n);
      for(int i=N; i<N+m; ++i) p[n+i-N] = p[i];
      m = convex_hull(p+n, m);
    }
    bool ok = false;
    for(int i=0; !ok&&i<n; ++i) {
      for(int j=n; !ok&&j<n+m; ++j) {
	int b[5]={0}, w[5]={0};
	for(int k=0; k<n; ++k) b[ccw(p[i],p[j],p[k])+2]++;
	for(int k=n; k<n+m; ++k) w[ccw(p[i],p[j],p[k])+2]++;
	ok = true;
	b[ccw(p[i],p[j],p[i])+2]--;
	for(int k=0; k<5; ++k) ok &= b[k]*w[k]==0;
	b[ccw(p[i],p[j],p[i])+2]++;
	w[ccw(p[i],p[j],p[j])+2]--;
	for(int k=0; k<5; ++k) ok &= b[k]*w[k]==0;
      }
    }
    puts(ok ? "YES" : "NO");
  }
  return 0;
}

PKU 3804 -- Swimming Jam

| 18:04 | PKU 3804 -- Swimming Jam - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3804 -- Swimming Jam - Wrong Answer -- japlj PKU 3804 -- Swimming Jam - Wrong Answer -- japlj のブックマークコメント

1秒ずつシミュレーションしたらTLEしたので、次に端に到着する人が現れるまでワープさせるようにしたらTLE1秒のところをぴったり1000MSで通った。


#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct swimmer {
  int pos, pace, laps;
  swimmer(int po, int pa, int la)
    : pos(po), pace(pa), laps(la) { }
};
bool operator < (const swimmer& a, const swimmer& b)
{
  return a.pace < b.pace;
}

int main()
{
  int n;
  while(scanf("%d", &n), n) {
    vector<swimmer> a, b;
    for(int i=0; i<n; ++i) {
      int t, c;
      scanf("%d%d", &t, &c);
      a.push_back(swimmer(t, t, c*2));
    }
    sort(a.begin(), a.end());
    int tm;
    for(tm=0; a.size()+b.size()>0; ) {
      int x = a.size()>0 ? a[0].pos : 300;
      int y = b.size()>0 ? b[0].pos : 300;
      if(x > y) x = y;
      for(int i=0; i<(int)a.size(); ++i) a[i].pos-=x;
      for(int i=0; i<(int)b.size(); ++i) b[i].pos-=x;
      tm += x;
      if(a.size()>0 && a[0].pos<=0) {
	int i;
	vector<swimmer> p;
	for(i=0; i<(int)a.size() && a[i].pos<=0; ++i)
	  p.push_back(swimmer(a[i].pace, a[i].pace, a[i].laps-1));
	sort(p.begin(), p.end());
	while(i--) a.erase(a.begin());
	for(i=0; i<(int)p.size(); ++i) b.push_back(p[i]);
      }
      if(b.size()>0 && b[0].pos<=0) {
	int i;
	vector<swimmer> p;
	for(i=0; i<(int)b.size() && b[i].pos<=0; ++i)
	  if(b[i].laps>1)
	    p.push_back(swimmer(b[i].pace, b[i].pace, b[i].laps-1));
	sort(p.begin(), p.end());
	while(i--) b.erase(b.begin());
	for(i=0; i<(int)p.size(); ++i) a.push_back(p[i]);
      }
    }
    printf("%d\n", tm);
  }
  return 0;
}

PKU 3803 -- Repeated Substitution with Sed

| 17:32 | PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj PKU 3803 -- Repeated Substitution with Sed - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>
#include<string>
#include<set>

using namespace std;

set<string> memo;
string p[10], q[10];
string target;
int n, sol;

void search(string cur, int c)
{
  if(cur == target) {
    if(sol > c) sol = c;
    return;
  }
  if(c >= sol || cur.size() >= target.size()) return;
  if(memo.find(cur) != memo.end()) return;
  memo.insert(cur);
  for(int i=0, x=0, y=0; i<n; ++i, x=0, y=0) {
    string next = "";
    while(x < cur.size() && (x = cur.find(p[i], x)) != string::npos) {
      next += cur.substr(y, x-y) + q[i];
      y = x += p[i].size();
    }
    next += cur.substr(y);
    search(next, c+1);
  }
}

int main()
{
  while(scanf("%d", &n), n) {
    memo.clear();
    for(int i=0; i<n; ++i) {
      char a[12], b[12];
      scanf("%s%s", a, b);
      p[i] = a; q[i] = b;
    }
    char s[12], t[12];
    scanf("%s%s", s, t);
    target = t;
    sol = 100;
    search(s, 0);
    printf("%d\n", sol==100 ? -1 : sol);
  }
  return 0;
}

PKU 3802 -- Cubist Artwork

| 17:02 | PKU 3802 -- Cubist Artwork - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3802 -- Cubist Artwork - Wrong Answer -- japlj PKU 3802 -- Cubist Artwork - Wrong Answer -- japlj のブックマークコメント

n個のブロックが積まれてる山がいくつ存在するかについて考えると、n個のブロックの山が前からa個、横からb個見えたなら全部で max(a,b) 個あれば十分。

あとは足すだけ。


#include<cstdio>

using namespace std;

int main()
{
  int w[2];
  while(scanf("%d%d", &w[0], &w[1]), w[0]||w[1]) {
    int h[2][20], c=0;
    for(int i=0; i<2; ++i)
      for(int j=0; j<w[i]; ++j) scanf("%d", &h[i][j]);
    for(int i=1, x=0; i<=20; ++i, x=0) {
      for(int j=0, y=0; j<2; ++j, x=x<y?y:x, y=0)
	for(int k=0; k<w[j]; ++k) y+=h[j][k]==i;
      c += x*i;
    }
    printf("%d\n", c);
  }
  return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/JAPLJ/20110119
 |