Hatena::Grouptopcoder

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

2011-05-23

PKU 1579 -- Function Run Fun

| 22:34 | PKU 1579 -- Function Run Fun - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1579 -- Function Run Fun - Wrong Answer -- japlj PKU 1579 -- Function Run Fun - Wrong Answer -- japlj のブックマークコメント

某言語の練習。メモ化するだけ。


program P1579
  implicit none
  integer a, b, c
  integer,dimension(0:20,0:21,0:21) :: memo
  
  memo = -1
  
  do
    read(*,*) a, b, c
    if (a==-1 .and. b==-1 .and. c==-1) exit
    print '("w(", i0, ", ", i0, ", ", i0, ") = ", i0)', a, b, c, w(a, b, c)
  end do
  
  contains
    recursive function w(a, b, c) result(res)
      integer a, b, c, res
      
      if (a<=0 .or. b<=0 .or. c<=0) then
        res = 1
        return
      else if ((a>20) .or. (b>20) .or. (c>20)) then
        res = w(20, 20, 20)
        return
      end if
      
      if (memo(a, b, c) /= -1) then
        res = memo(a, b, c)
      else if (a<b .and. b<c) then
        res = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
      else 
        res = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
      end if
      
      memo(a, b, c) = res
    end function w
end program P1579

2011-04-28

PKU 3908 -- Quick answer

| 20:21 | PKU 3908 -- Quick answer - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3908 -- Quick answer - Wrong Answer -- japlj PKU 3908 -- Quick answer - Wrong Answer -- japlj のブックマークコメント

Union-Findやるだけ。


#include<cstdio>
#include<vector>

using namespace std;

vector<int> U;
int find(int x) { return U[x]!=x?U[x]=find(U[x]):U[x]; }
int main()
{
  int n;
  while(~scanf("%d", &n)) {
    vector<int> ni;
    U.clear();
    for(int i=0; i<=n; ++i)
      U.push_back(i), ni.push_back(i);
    int yes=0, no=0;
    char op[4];
    while(scanf("%s", op), op[0]!='e') {
      int i, j;
      if(op[0]=='c') {
	scanf("%d%d", &i, &j);
	U[find(ni[i])] = find(ni[j]);
      } else if(op[0]=='d') {
	scanf("%d", &i);
	U.push_back(ni[i] = U.size());
      } else {
	scanf("%d%d", &i, &j);
	(find(ni[i]) == find(ni[j]) ? yes : no)++;
      }
    }
    printf("%d , %d\n", yes, no);
  }
  return 0;
}

PKU 3911 -- Internet Service Providers

| 19:50 | PKU 3911 -- Internet Service Providers - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3911 -- Internet Service Providers - Wrong Answer -- japlj PKU 3911 -- Internet Service Providers - Wrong Answer -- japlj のブックマークコメント

やるだけ。


#include<cstdio>

int main()
{
  int n, c;
  while(~scanf("%d%d", &n, &c)) {
    if(!n) puts("0");
    else {
      int t = c/n/2;
      for(int i=c/n/2+1; i>=c/n/2-1; --i)
	if(i>=0 && i*(c-1ll*i*n)>=t*(c-1ll*t*n)) t=i;
      printf("%d\n", t);
    }
  }
  return 0;
}

2011-04-20

PKU 3903 -- Stock Exchange

| 23:18 | PKU 3903 -- Stock Exchange - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3903 -- Stock Exchange - Wrong Answer -- japlj PKU 3903 -- Stock Exchange - Wrong Answer -- japlj のブックマークコメント

速い方のLISやるだけ


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

using namespace std;

typedef long long ll;
ll A[100000];
int main()
{
  int L;
  while(~scanf("%d", &L)) {
    for(int i=0; i<L; ++i)
      scanf("%lld", &A[i]);
    vector<ll> P(L, (1ULL<<63)-1);
    vector<int> I(L);
    for(int i=0; i<L; ++i)
      P[I[i]=lower_bound(P.begin(), P.end(), A[i])-P.begin()]=A[i];
    printf("%d\n", *max_element(I.begin(), I.end())+1);
  }
  return 0;
}

2011-04-15

PKU 3255 -- Roadblocks

| 20:11 | PKU 3255 -- Roadblocks - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3255 -- Roadblocks - Wrong Answer -- japlj PKU 3255 -- Roadblocks - Wrong Answer -- japlj のブックマークコメント

dijkstraやるだけ。


#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

struct edge {
  int src, dst, len;
  edge(int s, int d, int l)
    : src(s), dst(d), len(l) { }
};
bool operator < (const edge& e, const edge& f) {
  return e.len > f.len;
}
typedef vector<edge> vertex;
typedef vector<vertex> graph;

int dijkstra(const graph& g, int s, int t, int k)
{
  const int n = g.size();
  vector<vector<int> > d(n);
  priority_queue<edge> Q;
  for(Q.push(edge(-1, s, 0)); !Q.empty(); ) {
    edge e = Q.top(); Q.pop();
    if((int)d[e.dst].size() >= k) continue;
    d[e.dst].push_back(e.len);
    for(int i=0; i<(int)g[e.dst].size(); ++i)
      Q.push(edge(e.dst, g[e.dst][i].dst, e.len+g[e.dst][i].len));
  }
  return d[t][k-1];
}

int main()
{
  int n, r;
  scanf("%d%d", &n, &r);
  graph g(n);
  for(int i=0; i<r; ++i) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    a--; b--;
    g[a].push_back(edge(a, b, d));
    g[b].push_back(edge(b, a, d));
  }
  printf("%d\n", dijkstra(g, 0, n-1, 2));
  return 0;
}

PKU 3069 -- Saruman's Army

| 19:53 | PKU 3069 -- Saruman's Army - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3069 -- Saruman's Army - Wrong Answer -- japlj PKU 3069 -- Saruman's Army - Wrong Answer -- japlj のブックマークコメント

greedyやるだけ。


#include<cstdio>
#include<algorithm>

int main()
{
  int r, n, x[1024];
  while(scanf("%d%d", &r, &n), r>=0||n>=0) {
    for(int i=0; i<n; ++i) scanf("%d", &x[i]);
    std::sort(x, x+n);
    int sol = 0;
    for(int i=0; i<n; sol++) {
      int j;
      for(j=i; j<n&&x[j]-x[i]<=r; ++j) ;
      for(i=j-1; i<n&&x[i]-x[j-1]<=r; ++i) ;
    }
    printf("%d\n", sol);
  }
  return 0;
}

PKU 1852 -- Ants

| 19:45 | PKU 1852 -- Ants - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1852 -- Ants - Wrong Answer -- japlj PKU 1852 -- Ants - Wrong Answer -- japlj のブックマークコメント

区別のつかない物が完全弾性衝突→すり抜けと見なすというお決まりのアレでやるだけ。


#include<cstdio>
#include<algorithm>

int main()
{
  int T;
  scanf("%d", &T);
  while(T--) {
    int L, N, a, b, t;
    scanf("%d%d", &L, &N);
    a = 0; b = 0;
    for(int i=0; i<N; ++i) {
      scanf("%d", &t);
      a = std::max(a, std::min(t, L-t));
      b = std::max(b, std::max(t, L-t));
    }
    printf("%d %d\n", a, b);
  }
  return 0;
}

2011-04-04

PKU 1841 -- Meadow

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

最小全域森やるだけ。TLEとMLEがきつい。


#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

float D[2000][2000], u[2000], d[2000];
float prim(int n, int k)
{
  for(int i=0; i<n; ++i) d[i]=D[0][i];
  for(int i=1; i<n; ++i) {
    int v=-1;
    for(int j=0; j<n; ++j)
      if(d[j]!=0 && (v==-1 || d[j]<d[v])) v=j;
    u[i-1]=d[v]; d[v]=0;
    for(int j=0; j<n; ++j)
      if(D[v][j]<d[j]) d[j]=D[v][j];
  }
  sort(u, u+n-1);
  return u[n-k-1];
}

int f, b, m, e, x[2000], y[2000];
int main()
{
  scanf("%d%d", &f, &b);
  for(int i=0; i<f; ++i) scanf("%d%d", &x[i], &y[i]);
  for(int i=0; i<f; ++i)
    for(int j=i+1; j<f; ++j)
      D[i][j]=D[j][i]=sqrt((float)(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
  printf("%.2f\n", prim(f, b));
  return 0;
}

PKU 1838 -- Banana

| 03:41 | PKU 1838 -- Banana - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1838 -- Banana - Wrong Answer -- japlj PKU 1838 -- Banana - Wrong Answer -- japlj のブックマークコメント

Flood-Fillするだけ。


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

using namespace std;

int U[16666];
void init(int n) { for(int i=0; i<n; ++i) U[i]=i; }
int find(int x) { if(U[x]!=x) U[x]=find(U[x]); return U[x]; }

int main()
{
  int N, K;
  scanf("%d%d", &N, &K);
  vector<pair<pair<int, int>, int> > P(N);
  for(int i=0; i<N; P[i].second=i++)
    scanf("%d%d", &P[i].first.first, &P[i].first.second);
  init(N);
  for(int i=0; i<2; ++i) {
    sort(P.begin(), P.end());
    for(int j=0; j<N-1; ++j)
      if(P[j].first.first==P[j+1].first.first&&P[j+1].first.second-P[j].first.second==1)
	U[find(P[j].second)] = find(P[j+1].second);
    for(int j=0; j<N; ++j)
      swap(P[j].first.first, P[j].first.second);
  }
  vector<int> R(N, 0);
  for(int i=0; i<N; ++i)
    R[find(i)]++;
  sort(R.begin(), R.end());
  int sol = 0;
  for(int i=0; i<K; ++i)
    sol += R[R.size()-i-1];
  printf("%d\n", sol);
  return 0;
}

PKU 1837 -- Balance

| 03:16 | PKU 1837 -- Balance - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1837 -- Balance - Wrong Answer -- japlj PKU 1837 -- Balance - Wrong Answer -- japlj のブックマークコメント

DPやるだけ。


#include<cstdio>

int dp[21][15050], p[21];
int main()
{
  int c, g;
  scanf("%d%d", &c, &g);
  for(int i=0; i<c; ++i) scanf("%d", &p[i]);
  dp[0][7500] = 1;
  for(int i=1; i<=g; ++i) {
    int w;
    scanf("%d", &w);
    for(int j=0; j<c; ++j)
      for(int k=0; k<=15000; ++k)
	if(dp[i-1][k]>0) dp[i][k+w*p[j]] += dp[i-1][k];
  }
  printf("%d\n", dp[g][7500]);
  return 0;
}

PKU 1200 -- Crazy Search

| 03:00 | PKU 1200 -- Crazy Search - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 1200 -- Crazy Search - Wrong Answer -- japlj PKU 1200 -- Crazy Search - Wrong Answer -- japlj のブックマークコメント

rolling hashやるだけ。


#include<cstdio>

using namespace std;

char S[1<<24], P[256], V[1<<24] = {0};
int main()
{
  int l, n, nc;
  scanf("%d%d%s", &n, &nc, S);
  for(int i=0; i<256; ++i) P[i]=-1;
  for(l=nc=0; S[l]; ++l)
    if(P[S[l]]==-1) P[S[l]]=nc++;
  if(n>l) { puts("0"); return 0; }
  int hash = 0, exp = 1, sol = 0;
  for(int i=0; i<n; ++i, exp*=nc)
    hash = hash*nc+P[S[i]];
  V[hash]=1;
  sol=1;
  for(int i=n; i<l; ++i) {
    hash = nc*hash-exp*P[S[i-n]]+P[S[i]];
    sol+=!V[hash];
    V[hash]=1;
  }
  printf("%d\n", sol);
  return 0;
}