Hatena::Grouptopcoder

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

 | 

2011-01-21

PKU 3541 -- Given a string...

| 19:04 | PKU 3541 -- Given a string... - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3541 -- Given a string... - Wrong Answer -- japlj PKU 3541 -- Given a string... - Wrong Answer -- japlj のブックマークコメント

KMPやるだけ


#include<cstdio>
#include<cstring>

using namespace std;

int main()
{
  char T[5050], S[15050];
  scanf("%s%s", T, S);
  int n = strlen(S), fail[5050];
  for(int i=n; i<3*n; ++i) S[i]=S[i-n];
  fail[0] = -1;
  for(int i=1; i<n; ++i) {
    int j = fail[i-1];
    while(j >= 0 && T[i] != T[j+1]) j = fail[j];
    if(T[i] == T[j+1]) j++;
    fail[i] = j;
  }
  for(int i=0; i<n; ++i) {
    int j = -1;
    for(int k=0; k<2*n; ++k) {
      while(j >= 0 && (S[k]^S[i+k])+'0' != T[j+1]) j = fail[j];
      if((S[k]^S[i+k])+'0' == T[j+1]) ++j;
      if(j >= n-1) { puts("Yes"); return 0; }
    }
  }
  puts("No");
  return 0;
}

PKU 3539 -- Elevator

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

lo[x] := cで割った余りが x であるような階のうち、到達可能な最も低い階

をまずpriority queueとかで適当に計算すると、lo[x]+k*c (k >= 0) なる階にはすべて到達できるので 0 <= lo[x]+k*c < h なる k の数を全ての x について足せばよい。

TLEが厳しめっぽくて、 c の代わりに min{a,b,c} を使わないと通らなかった。


#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;

int main()
{
  ll h, lo[100000];
  int a, b, c;
  scanf("%lld%d%d%d", &h, &a, &b, &c);
  if(c>b) swap(b,c); if(c>a) swap(a,c);
  for(int i=0; i<c; ++i) lo[i] = 1ll<<60;
  priority_queue<ll> Q;
  for(Q.push(0), lo[0]=0; !Q.empty(); ) {
    ll p = Q.top(); Q.pop();
    if(lo[(p+a)%c]>p+a) Q.push(p+a), lo[(p+a)%c]=p+a;
    if(lo[(p+b)%c]>p+b) Q.push(p+b), lo[(p+b)%c]=p+b;
  }
  ll sol = 0;
  for(int i=0; i<c; ++i) {
    if(lo[i] >= h) continue;
    ll hi = h-h%c+i;
    if(hi < h) hi += c;
    sol += (hi-lo[i])/c;
  }
  printf("%lld\n", sol);
  return 0;
}

PKU 3538 -- Domestic Networks

| 17:45 | PKU 3538 -- Domestic Networks - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3538 -- Domestic Networks - Wrong Answer -- japlj PKU 3538 -- Domestic Networks - Wrong Answer -- japlj のブックマークコメント

最小全域木を求めてから、安い方のケーブルをできるだけ使う。安い方をどれだけ使えるかはDPで求める。


#include<cstdio>
#include<algorithm>

using namespace std;

int U[1024];
void init(int n) { for(int i=1; i<=n; ++i) U[i]=i; }
int find(int x) { return x!=U[x] ? U[x]=find(U[x]) : U[x]; }
void uni(int x, int y) { U[find(x)]=find(y); }

struct edge { int a, b, c, i; } E[10000];
bool operator < (const edge& e, const edge& f) {
  return e.c < f.c;
}

int main()
{
  int n, m, e=0, s=0, use[1000], p[2], q[2], r[2]={5,6};
  scanf("%d%d", &n, &m);
  for(int i=0; i<m; ++i)
    scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c), E[i].i=i;
  sort(E, E+m); init(n);
  for(int i=0; i<m; ++i) {
    if(find(E[i].a) == find(E[i].b)) continue;
    use[e++] = i; s += E[i].c;
    uni(E[i].a, E[i].b);
  }
  if(e!=n-1) { puts("Impossible"); return 0; }
  scanf("%d%d%d%d", &p[0], &q[0], &p[1], &q[1]);
  if(p[0]>p[1]) swap(p[0],p[1]), swap(q[0],q[1]), swap(r[0],r[1]);
  int dp[10001]={0}, ch[10001], cat[10000], use0;
  dp[0] = 1;
  for(int i=0, cost; i<e&&(cost=E[use[i]].c); cat[use[i++]]=1)
    for(int j=q[0]-cost; j>=0; --j)
      if(dp[j] && !dp[j+cost])
	dp[j+cost]=1, ch[j+cost]=i;
  for(use0=q[0]; !dp[use0]; use0--) ;
  if(s - use0 > q[1]) { puts("Impossible"); return 0; }
  for(int u=use0; u; u-=E[use[ch[u]]].c) cat[use[ch[u]]] = 0;
  printf("%d\n", p[0]*use0 + p[1]*(s-use0));
  for(int i=0; i<e; ++i)
    printf("%d %d\n", E[use[i]].i+1, r[cat[use[i]]]);
  return 0;
}

PKU 3537 -- Crosses and Crosses

| 16:56 | PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj のブックマークコメント

連続する n 個の空白からなる盤面に対するGrundy数を計算する。ある場所に x を書くと、そのxから距離が2以下のところに次に x を置くと確実に負けるので、x の両隣2マス分は除外して考えられる。


#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
  int n, grundy[2048] = {0};
  scanf("%d", &n);
  for(int i=1; i<=n; ++i) {
    int reach[2048] = {0};
    for(int j=0; j<i; ++j) reach[grundy[max(j-2,0)]^grundy[max(i-j-3,0)]]=1;
    while(reach[grundy[i]]) grundy[i]++;
  }
  printf("%d\n", grundy[n] ? 1 : 2);
  return 0;
}

PKU 3535 -- A+B

| 16:39 | PKU 3535 -- A+B - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3535 -- A+B - Wrong Answer -- japlj PKU 3535 -- A+B - Wrong Answer -- japlj のブックマークコメント

i文字目に使える文字が c 種類あるとすると、i桁目がc進数である(cで繰り上がりする)ような整数どうしの足し算としてよい。


#include<cstdio>

using namespace std;

char a[100000], b[100000], s[100000], c[32];
bool ng[100000][26];

int main()
{
  int n, k;
  scanf("%d%d", &n, &k);
  for(int i=0; i<k; ++i) {
    scanf("%s", s);
    for(int j=0; j<n; ++j) ng[j][s[j]-'a'] = true;
  }
  scanf("%s%s", a, b);
  int carry = 0;
  for(int i=n-1; i>=0; --i) {
    int chars = 0;
    for(int j=0; j<26; ++j) {
      if(ng[i][j]) continue;
      if(a[i]=='a'+j) carry+=chars;
      if(b[i]=='a'+j) carry+=chars;
      c[chars++] = 'a'+j;
    }
    s[i] = c[carry % chars];
    carry /= chars;
  }
  s[n] = '\0';
  printf("%s\n", s);
  return 0;
}
 |