Hatena::Grouptopcoder

敗戦記

2011-05-15

UTPC 2011

| 10:50

オンライン参加のつもりでしたが、ICPCで組む人と顔合わせのつもりで,現地からの参加に変更してもらいました。

A

  • 足すだけ。
    • ファイルをA.cpp,B.cpp・・・みたいにつくっていたのですが、いつもはmain.cppひとつだけだったので、コンパイルに手間取りました。

B

  • ()と文字数奇数の場合に注意して、書く。

C

  • O(2^n)で全探索しました。

D

  • シミュレーション問題。
    • それほど強実装というわけではないですが、(自分にとっては)簡単というほどの問題でもなく、好きなタイプの問題でした。
  • 取り敢えず書くも、最初のサンプルが合わない。
    • '@'か'_'のところがおかしかったので直した。
  • 必ず停止するかを判定するのかと勘違いして3番目が合わない。
    • 直してサブミット。
    • 3つWAってる。
    • メモリ用のブールを15個しか確保してなかった。
    • 1つWA
    • 訪れたかどうかのフラグに方向も含めてAC

E

  • 解いている人がそこそこ多いので、開いてみるもすぐには思いつかない。
  • スモールが16<=nだけど順番全生成だと間に合いそうにない。
  • 仕方ないので飛ばす。

ここらへんで取り敢えず残りの問題を全部読む。

G

  • なんとなくEの次に解いている人が多かったのでこれを考えてみる。
    • ソートして、大きい辺から3つ次に大きい辺から3つ取ってくる方法を試してみる。
    • 通らない。
  • 考えても大きい方から3つ、次に大きいものから3つ取ってくる以外の組み合わせが思い浮かばないので、必死におかしそうなところを探す。
    • long long配列なのに、ソートでgreater<int>を使っていた。
    • 直す。
      • WAが減ったけど半分ぐらいはWAのまま。
  • よく分からなくなってきたので飛ばす。

E

  • もうこれぐらいしか解ける気がしないので戻ってきた。
    • 取り敢えず幅優先でn<=16を通した。
    • よく考えるとbでソートしたあと、bの小さい問題から順に見ていって、n問ファーストアクセプタンスを得るのに必要な最短時間を更新していけば、うまく行くような気がしてきたので書く。

I

  • Gが分からなかったで取り敢えずこれに。
    • xorを使うと、欲しい値以外は0に変換出来るなとか考えて、その値が1になってくれれば解決じゃないだろうかと、ずっと試行錯誤していました。
    • 時間がきて終了。

http://atcoder.jp/contest/8/standing

5問解いて50位でした。

F以降の問題をもう一問ぐらいとけるようにぐらいは成っていたかったように思いました。どうすれば難しい問題が解けるようになるんでしょうかね。

Fの解答を聞いたときはきれいすぎる生成方法にとても驚きました。

2011-04-10

UVa Huge Easy Contest Ⅱ

| 23:56

http://uva.onlinejudge.org/index2.php?option=com_onlinejudge&Itemid=13&page=show_contest_standings&contest=279&fullscreen=1

なかなか面白そうだと思ったので参加しました。

24時間で26問解くというコンテストでした。

20位にいるI.Tというのが自分です。


微妙にあやふやになりながら書いてます。

A

  • 開く。最初読んでも意味が分からないので、誰か他の人が問題を解くまで待機。

Jが解かれているのでJへ。

J

  • N(100000>=N>=1)以下の数で、最も約数の数が多いものを答えるというような問題。
  • 最初に小さいほうから事前計算で全列挙する方針を書いたのですが、TLEしました。
  • N^(3/2)ぐらいのオーダーだと思ったので大丈夫な気がしたんですが駄目だったようです。
  • しばらく考えても分からないので他の問題に。

B

  • 結局最初に解けたのがこれ。
  • A+B=Cという形の数式が与えられるときに、コレを満たすのは数字を何進数として計算した時かを答えるというような問題。
  • 1進数として数えたときに変になることに気づかずに投げてWA
  • 修正してAC
int toint(string in,int base){
  if(base==1)return SZ(in);
  int ret=0;
  rep(i,SZ(in)){
    ret=ret*base+in[i]-'0';
  }
  return ret;
}

main(){
  int t;
  string in;
  getline(cin,in);
  stringstream str(in);
  str>>t;
  while(t--){
    string in;
    getline(cin,in);
    rep(i,SZ(in))if(!isdigit(in[i]))in[i]=' ';
    stringstream ss(in);
    string a,b,c;
    ss>>a>>b>>c;

    int ans=0;
    for(int i=1;i<100;i++){
      bool ok=true;
      rep(j,SZ(a)){
        if(i==1 && a[j]!='1'){
          ok=false;
        }else if(i!=1 && a[j]>=i+'0')ok=false;
      }

      rep(j,SZ(b)){
        if(i==1 && b[j]!='1')ok=false;
        else if(i!=1 && b[j]>=i+'0')ok=false;
      }

      rep(j,SZ(c)){
        if(i==1 && c[j]!='1')ok=false;
        else if(i!=1 && c[j]>=i+'0')ok=false;
      }

      if(!ok)continue;
      if(toint(a,i)+toint(b,i)==toint(c,i)){
        ans=i;
        break;
      }
    }
    cout<<ans<<endl;
  }
}

C

  • 壊れていない船が何隻あるかを数える。
  • 幅優先探索して終わり
bool vis[100][100];
string in[100];

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    int n;
    cin>>n;
    rep(i,n)cin>>in[i];
    memset(vis,0,sizeof(vis));

    int ans=0;
    rep(i,n){
      rep(j,n){
        if(vis[i][j])continue;
        if(in[i][j]!='x')continue;
        queue<PI> Q;
        Q.push(mp(i,j));
        ++ans;
        while(!Q.empty()){
          int cx=Q.front().F,cy=Q.front().S;
          Q.pop();
          if(vis[cx][cy])continue;
          vis[cx][cy]=true;

          rep(i,4){
            int nx=cx+dx[i],ny=cy+dy[i];
            if(nx<0 || n<=nx ||
               ny<0 || n<=ny ||
               vis[nx][ny] || in[nx][ny]=='.')continue;
            Q.push(mp(nx,ny));
          }
        }
      }
    }
    cout<<ans<<endl;
  }
}

L

  • DNAを4進数の数字と見ればいい。問題なくAC
ll toll(string &in){
  ll ret=0;
  rep(i,SZ(in)){
    switch(in[i]){
    case 'A':ret=ret*4+0;break;
    case 'C':ret=ret*4+1;break;
    case 'G':ret=ret*4+2;break;
    case 'T':ret=ret*4+3;break;
    }
  }
  return ret;
}

main(){
  int t;
  cin>>t;
  rep(ca,t){
    string in;
    cin>>in;
    cout<<"Case "<<ca+1<<": ("<<SZ(in)<<':'<<toll(in)<<')'<<endl;
  }
}

E

  • これもやるだけ。ただ、long longのコンビネーションを出すときに、浮動小数使ったら誤差死して1WA。
ll comb(int n,int k){
  long double ret=1;
  k=min(k,n-k);
  while(k){
    ret*=1.0*n--/k--;
  }
  return ll(ret+0.1);
}

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    string in;
    cin>>in;
    rep(i,SZ(in)){
      if(!isalpha(in[i]) && !isdigit(in[i]))in[i]=' ';
    }

    string a,b;
    int k;
    stringstream ss(in);
    ss>>a>>b>>k;
    rep(i,k+1){
      ll xk=comb(k,i);
      if(i)cout<<'+';
      if(xk>1)cout<<xk<<'*';
      if(i!=k)cout<<a;
      if(k-i>1)cout<<'^'<<k-i;
      if(i!=k && i)cout<<'*';
      if(i)cout<<b;
      if(i>1)cout<<'^'<<i;
    }
    cout<<endl;
  }
}

P

  • 正解者が多かったのでPへ。
  • ある距離以下の星に対してunion-findする。というような問題。
int un[1000];

int find(int x){
  if(x==un[x])return x;
  return un[x]=find(un[x]);
}

void unit(int a,int b){
  un[find(a)]=un[find(b)]=find(a);
}

double x[1000],y[1000];

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    int n;
    double d;
    cin>>n>>d;
    rep(i,n){
      cin>>x[i]>>y[i];
      un[i]=i;
    }

    rep(i,n){
      rep(j,n){
        double tx=x[i]-x[j],ty=y[i]-y[j];
        if(sqrt(tx*tx+ty*ty)<=d)unit(i,j);
      }
    }
    set<int> app;
    rep(i,n)app.insert(find(i));
    cout<<SZ(app)<<endl;
  }
}

G

  • チェッカーの駒が一番上の段に行く時に何通りの行き方があるかという問題。
  • 全探索だと死ぬので動的計画法。苦手意識があったけれどこれぐらいならすんなり。
ll dp[100][100];

string in[100];

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    memset(dp,0,sizeof(dp));
    int n;
    cin>>n;

    rep(i,n){
      cin>>in[n-i-1];
    }


    ll ans=0;
    rep(i,n){
      rep(j,n){
        if(in[i][j]=='W')dp[i][j]=1;
        if(in[i][j]!='.')continue;
        int x=j-1,y=i-1;
        if(y>=0 && 0<=x && x<n && in[y][x]!='B')dp[i][j]+=dp[y][x];
        x=j+1;
        if(y>=0 && 0<=x && x<n && in[y][x]!='B')dp[i][j]+=dp[y][x];
        y=i-2,x=j-2;
        if(y>=0 && 0<=x && x<n && in[y][x]!='B' && in[y+1][x+1]=='B')dp[i][j]+=dp[y][x];
        x=j+2;
        if(y>=0 && 0<=x && x<n && in[y][x]!='B' && in[y+1][x-1]=='B')dp[i][j]+=dp[y][x];
        dp[i][j]%=1000007;
        if(i==n-1)ans=(ans+dp[i][j])%1000007;
      }
    }
    cout<<ans<<endl;
  }
}

O

  • 連続するスペースを一つのスペースにまとめる。
  • 最初に一つずつ数えながらやろうとしたらWAったりPEが取れなかったりしたので、stringクラスにたよることに。
  • replace使いました。WAになりました。
  • テストケースの"間"だけ改行しろとのことだったのでそうしたらAC
    • こういうのってPE扱いになるんじゃないんですかね。
main(){
  int t;
  string in;
  getline(cin,in);
  stringstream ss(in);
  ss>>t;
  rep(ca,t){
    if(ca)cout<<endl;
    cout<<"Case "<<ca+1<<':'<<endl;
    getline(cin,in);
    stringstream str(in);
    int n;
    str>>n;

    rep(i,n){
      getline(cin,in);

      while(true){
        int pos=in.find("  ");
        if(pos<0)break;
        in.replace(pos,2," ");
      }
      cout<<in<<endl;
    }
  }
}

R

  • 合計値とって平均に一番近いの選ぶだけ。
  • 何かWAになった気がしますが、掛け算の桁あふれが原因だった気がします。
ll absll(ll in){
  if(in<0)return -in;
  return in;
}

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case #"<<ca+1<<": ";

    ll n,m,k;
    cin>>n>>m>>k;
    ll sum=0;
    set<ll> cake,dr;
    ll tt;
    rep(i,m){
      cin>>tt;
      sum+=tt;
      cake.insert(tt);
    }

    rep(i,k){
      cin>>tt;
      sum+=tt;
      dr.insert(tt);
    }
    ll a=*cake.begin(),b=*dr.begin();
    rep(i,n-k-m){
      cin>>tt;
      sum+=tt;
    }

    FOR(siter,cake){
      if(absll(*siter*n-sum)<absll(a*n-sum))a=*siter;
    }

    FOR(siter,dr){
      if(absll(*siter*n-sum)<absll(b*n-sum))b=*siter;
    }
    cout<<a<<' '<<b<<endl;
  }
}

K

  • dfsしながらsetに突っ込んだあと表示。
set<string> app;
string in;

void dfs(int ne,int rest){
  if(rest==0){
    app.insert(in);
    return;
  }

  for(int i=ne;i<SZ(in);i++){
    char back=in[i];
    rep(j,4){
      switch(j){
      case 0:in[i]='A';break;
      case 1:in[i]='C';break;
      case 2:in[i]='G';break;
      case 3:in[i]='T';break;
      }
      dfs(i+1,rest-1);
    }
    in[i]=back;
  }
}

main(){
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--){
    app.clear();
    int n,k;
    cin>>n>>k;
    cin>>in;
    dfs(0,k);

    cout<<SZ(app)<<endl;
    FOR(siter,app)cout<<*siter<<endl;
  }
}

H

  • バスの時刻と現在時刻とバスの所要時間から、目的地に辿りつくまでの最短時間を求めるというような問題。
  • 一日近く待つパターンとかはいれないで欲しいです。結構WAりました
main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    int k,hh,mm,time;
    scanf("%d %d:%d",&k,&hh,&mm);
    time=hh*60+mm;
    int ans=1<<22;
    while(k--){
      int q;
      scanf("%d:%d %d",&hh,&mm,&q);
      int diff=hh*60+mm+q-time;
      if(hh*60+mm<time)diff+=24*60;
      if(ans>diff)ans=diff;
    }
    cout<<ans<<endl;
  }
}

A

  • ここにきてAの正解者数が多かったので漸く解く気になりました。
  • よく読むと、最大の面積を持つ長方形を出来るだけ安く買うということだと理解しました。
  • O(n^2*m^2)なので若干不安でしたが、書いたらギリギリ通りました。
int pr[110][110];

main(){
  int t;
  cin>>t;
  rep(ca,t){
    memset(pr,0,sizeof(pr));
    cout<<"Case #"<<ca+1<<": ";

    int n,m,kk;
    cin>>n>>m>>kk;
    rep(i,n){
      rep(j,m){
        int p;
        cin>>p;
        pr[i+1][j+1]=pr[i+1][j]+pr[i][j+1]-pr[i][j]+p;
      }
    }

    int s=0,p=0;

    rep(i,n){
      rep(j,m){
        for(int k=i;k<n;k++){
          for(int l=j;l<m;l++){
            int ts=(k-i+1)*(l-j+1),tp=pr[k+1][l+1]-pr[i][l+1]-pr[k+1][j]+pr[i][j];
            if(ts>s && tp<=kk){
              s=ts;
              p=tp;
            }
            if(ts==s && tp<p){
              p=tp;
            }
          }
        }
      }
    }
    cout<<s<<' '<<p<<endl;
  }
}

J

  • ここらへんになって簡単な問題がなくなってきたような気がしたので、解いている人がかなり多いJへ。
  • 風呂に入りながら考えた方法で事前計算をするとギリギリで通過しました。
  • 解いているひとが多い割に微妙な計算方法な気がするし、早い人は本当に早いのでどういうふうに解いているのか知りたい問題の一つ。
int divi(int in){
  int ret=1;
  for(int i=2;i*i<=in;i++){
    if(in%i)continue;
    int tt=1;
    while(in%i==0){
      ++tt;
      in/=i;
    }
    ret*=tt;
  }
  if(in>1)ret*=2;
  return ret;
}

int most[1000001],ans[1000001];

main(){
  most[1]=ans[1]=1;

  for(int i=2;i<=1000000;i++){
    int d=divi(i);
    if(most[i-1]<=d){
      most[i]=d;
      ans[i]=i;
    }else{
      most[i]=most[i-1];
      ans[i]=ans[i-1];
    }
  }

  int t;
  scanf("%d",&t);
  int n;
  rep(ca,t)scanf("%d",&n),printf("%d\n",ans[n]);
}

F

  • 案外書くだけの問題。'.'は意味ない模様。
int mem[100];
int p;

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<":";
    string in;
    cin>>in;
    memset(mem,0,sizeof(mem));
    p=0;
    rep(i,SZ(in)){
      switch(in[i]){
      case '>':p=(p+1)%100;break;
      case '<':p=(p+99)%100;break;
      case '+':mem[p]=(mem[p]+1)%256;break;
      case '-':mem[p]=(mem[p]+255)%256;break;
      case '.':;
      }
    }
    rep(i,100)printf(" %02X",mem[i]);
    cout<<endl;
  }
}

T

  • これも最初に解いているひとが多いから解こうとしてTLE食らった問題。
  • X/(N-X)^(1/2)=iとなるようなiにたいしてXを求めていたから遅かったようです。
  • (N-X)^(1/2)が整数になるようなものを探していく方針でAC
main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<':';
    ll n;
    cin>>n;
    set<ll> ans;
    for(ll i=1;;i++){
      if(i*i>=n)break;
      ll x=n-i*i;
      if(x%i)continue;
      ans.insert(x);
    }
    FOR(siter,ans)cout<<' '<<*siter;
    cout<<endl;
  }
}

I

  • サイコロの面が与えられるので同じ物かどうかを判定しろというような問題。
  • ライブラリ的なものを持っていなかったので、面倒くさくて飛ばしていたのですが解いている人がそこそこ多い問題はこれぐらいしか残っていなかったので、解くことに。
  • 24通り書くのは面倒なので、回転の関数を書く。
string next(string in,int dir){
  string ret=in;
  switch(dir){
  case 0://x
    ret[0]=in[2];
    ret[2]=in[1];
    ret[1]=in[4];
    ret[4]=in[0];
    break;
  case 1://y
    ret[1]=in[3];
    ret[3]=in[0];
    ret[0]=in[5];
    ret[5]=in[1];
    break;
  case 2://z
    ret[2]=in[3];
    ret[3]=in[4];
    ret[4]=in[5];
    ret[5]=in[2];
    break;
  }
  return ret;
}

main(){
  int t;
  cin>>t;
  while(t--){
    bool ok=false;

    string a,b;
    cin>>a>>b;
    rep(j,4){
      rep(i,4){
        a=next(a,j%2);
        if(a==b)ok=true;
      }
      a=next(a,2);
    }
    a=next(a,1);
    rep(i,4){
      a=next(a,2);
      if(a==b)ok=true;
    }
    a=next(a,1);
    a=next(a,1);
    rep(i,4){
      a=next(a,2);
      if(a==b)ok=true;
    }
    
    
    if(ok)cout<<"Equal"<<endl;
    else cout<<"Not Equal"<<endl;
  }
}

Z

  • 与えられた期間に何日働くかを数える。
  • この前書いたカレンダーを持ってきて終わり
int mon[]={31,28,31,30,31,30,31,31,30,31,30,31};
map<ll,int> day;

main(){
  int y=1975,m=1,d=1;
  rep(i,4000000){
    if(y==2026)break;
    day[10000*y+m*100+d]=i;
    if(m==12 && d==31){
      y++;
      m=1;
      d=1;
      if((y%4==0 && y%100!=0) || y%400==0)mon[1]=29;
      else mon[1]=28;
      continue;
    }

    if(d==mon[m-1]){
      ++m;
      d=0;
    }
    ++d;
  }

  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    int n;
    cin>>n;
    set<int> ho,wo;
    while(n--){
      int y,m,d;
      char c;
      scanf(" %d-%d-%d %c ",&y,&m,&d,&c);
      if(c=='H')ho.insert(day[y*10000+m*100+d]);
      else wo.insert(day[y*10000+m*100+d]);
    }

    int s,e;
    int y,m,d;
    scanf("%d-%d-%d",&y,&m,&d);
    s=day[y*10000+m*100+d];
    scanf("%d-%d-%d",&y,&m,&d);
    e=day[y*10000+m*100+d];

    int ans=0;
    for(int i=s;i<=e;i++){
      if(wo.count(i)){
        ++ans;
        continue;
      }
      if(ho.count(i))continue;
      if(i%7==4 || i%7==3)continue;
      ++ans;
    }
    cout<<ans<<endl;
  }
}

Q

  • 五目並べのシミュレーション的なもの。
  • setで書きました。
int tx[]={1,1,0,-1},ty[]={0,1,1,1};

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    bool cro=0,nou=0;
    set<PI> cr,no;
    int n,k;
    cin>>n>>k;
    rep(i,n){
      int x,y;
      cin>>x>>y;
      if(i%2){
        no.insert(mp(x,y));
        rep(j,4){
          int cx=x,cy=y,tk=0;
          while(no.count(mp(cx,cy))){
            ++tk;
            cx=cx+tx[j];
            cy=cy+ty[j];
            if(tk>=k)break;
          }
          cx=x-tx[j];
          cy=y-ty[j];
          while(no.count(mp(cx,cy))){
            ++tk;
            cx=cx-tx[j];
            cy=cy-ty[j];
            if(tk>=k)break;
          }
          if(tk>=k)nou=true;
        }
      }else{
        cr.insert(mp(x,y));
        rep(j,4){
          int cx=x,cy=y,tk=0;
          while(cr.count(mp(cx,cy))){
            ++tk;
            cx=cx+tx[j];
            cy=cy+ty[j];
            if(tk>=k)break;
          }
          cx=x-tx[j];
          cy=y-ty[j];
          while(cr.count(mp(cx,cy))){
            ++tk;
            cx=cx-tx[j];
            cy=cy-ty[j];
            if(tk>=k)break;
          }
          if(tk>=k)cro=true;
        }
      }
    }
    if(cro && nou)cout<<"error";
    else if(cro)cout<<"crosses";
    else if(nou)cout<<"noughts";
    else cout<<"none";
    cout<<endl;
  }
}

何だか無駄があるけど気にしない。

これ解いて一旦寝ました。

起きたらジャッジが止まっていて順位があまり変わっていませんでした。

X

  • 一番最後に解けた問題。
  • 最初計算量的に無理だと思ったのですが、電球の状態数がたかだか2^15しかないことの気がついたので、解法を思いついて何とかなりました。
bool vis[1<<15];
int sw[100];

main(){
  int t;
  cin>>t;
  rep(ca,t){
    cout<<"Case "<<ca+1<<": ";
    int n,m;
    cin>>n>>m;
    memset(vis,0,sizeof(vis));
    memset(sw,0,sizeof(sw));
    rep(i,m){
      rep(j,n){
        int t;
        cin>>t;
        sw[i]|=t<<j;
      }
    }
    queue<PI> q;
    int ans=-1;
    q.push(mp(0,(1<<n)-1));
    while(!q.empty()){
      int c=q.front().F,st=q.front().S;
      q.pop();
      if(st==0){
        ans=c;
        break;
      }
      if(vis[st])continue;
      vis[st]=true;

      rep(i,m){
        int nst=st^sw[i];
        if(vis[nst])continue;
        q.push(mp(c+1,nst));
      }
    }
    if(ans>=0)cout<<ans<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
  }
}

ジャッジが止まっている間にX以外にもD,N,U,Wを投げていたのですが、見事に1つしかACされませんでした。Dあたりは解けそうだと思って最後らへんまで考えていたのですが、WAのままでした。

結局18問解けて、自分としては満足のいく結果だと思います。ICPC形式のコンテストのほうが好きですね。また次があるとしたらさらに問題数が増えて、時間が長くなったりするんでしょうか。なかなか楽しいコンテストでした。

2011-04-03

The 11th Zhejiang University Programming Contest

| 23:14

http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=324

どうも開催されていたようなので参加してきました。

UVaでもあったようで出たかったのですが、時間を把握してないうちに終わってしまったようです。残念。

取り敢えずAをひらいてみる。

普通に無理そうなので、しばらく待機して一番最初に解かれていたJを開く。

やるだけ。

main(){
  int t;
  cin>>t;
  while(t--){
    int p;
    cin>>p;
    int t;
    map<int,int> app;
    rep(i,p){
      cin>>t;
      app[-t]++;
    }
    int ans,ansn=0;
    FOR(miter,app){
      if(miter->S>ansn){
	ansn=miter->S;
	ans=-miter->F;
      }
    }
    cout<<ans<<endl;
  }
}

次にCを開く。Zodiacは十二支という意味だとは知りませんでしたね。これも書くだけなのかと思ったのですが、与えられた年における干支を答える問題かと思って書くと、サンプルが合わないので適当に順番を逆に変えると通りました。

そのときは逆順に回るものなのだとか考えて、さっさと次にいってしまったのですが、今更ながら、与えられるのが年齢でその人の生まれた年の干支を答えるんだと理解しました。

main(){
  int t;
  cin>>t;
  while(t--){
    int p;
    cin>>p;
    switch(p%12){
    case 2:cout<<"Tiger";break;
    case 1:cout<<"Rabbit";break;
    case 0:cout<<"Dragon";break;
    case 11:cout<<"Snake";break;
    case 10:cout<<"Horse";break;
    case 9:cout<<"Ram";break;
    case 8:cout<<"Monkey";break;
    case 7:cout<<"Rooster";break;
    case 6:cout<<"Dog";break;
    case 5:cout<<"Pig";break;
    case 4:cout<<"Rat";break;
    case 3:cout<<"Ox";break;
    }
    cout<<endl;
  }
}

次にACが多いGへ。ガウス素数というものの個数を数えるらしいです。最初意味が分からずに日本語wikipediaを読んだりしましたが、ようするに問題文の二つの条件のどちらかに引っかかるものの数を答えれば良さそうなので、書く。

TLE

素数判定をO(n^(1/2))にするとWAになりました。

ここからしばらくはまりタイムに。ガウス整数の判定関数にいくつかバグがあったりしたのですが、出力形式の最後のほうに書いている既約分数で出力というのを完全に見落としていたのがかなり痛かったです。それを直してAC

bool isg(int a,int b){
  rep(tt,2){
    if(a==0 && b!=0 && abs(b)%4==3){
      bool ok=true;
      for(int i=2;i*i<=abs(b);i++){
	if(b%i)continue;
	ok=false;
	break;
      }
      if(ok)return true;
    }
    swap(a,b);
  }

  ll k=ll(a)*a+ll(b)*b;
  if(k==2)return true;
  if(a && b && k%4==1){
    bool ok=true;
    for(ll i=2;i*i<=k;i++){
      if(k%i)continue;
      ok=false;
      break;
    }
    if(ok)return true;
  }
  return false;
}

main(){
  int t;
  cin>>t;
  while(t--){
    int x1,x2,y1,y2;
    cin>>x1>>x2>>y1>>y2;
    int c=0,p=0;
    for(int i=x1;i<x2+1;i++){
      for(int j=y1;j<y2+1;j++){
	++p;
	if(isg(i,j)){
	  //cout<<i<<' '<<j<<endl;
	  ++c;
	}
      }
    }
    cout<<c/__gcd(c,p)<<'/'<<p/__gcd(c,p)<<endl;
  }
}

次は、その時点で正解数が多かったのはIだったのですが、どちらかというとDのほうが面白そうだったのでそちらを先に解くことに。(決してIの問題文が長くて面倒だったわけではないです)

最初は独自にクラスを作ろうと思ったのですが、setやmapに突っ込むためのコードの書き方が分からなかったので、pairとかを使わせてもらいました。

あとは与えられた命令を素直に実装していくだけでした。

一発AC

typedef map<string,pair<string,set<string> > > cla;

main(){
  int t;
  cin>>t;
  while(t--){
    string in;
    while(getline(cin,in))if(in=="begin")break;
    cla exist;

    while(getline(cin,in)){
      if(in=="end")break;
      if(in.substr(0,5)=="class"){
	string cname,sname;
	int pos=in.find(':');
	if(pos>=0){
	  cname=in.substr(6,pos-6);
	  sname=in.substr(pos+1);
	}else{
	  cname=in.substr(6);
	}

	if(exist.count(cname)){
	  cout<<"oops!"<<endl;
	  continue;
	}
	if(sname.size() && exist.count(sname)==0){
	  cout<<"oops!"<<endl;
	  continue;
	}
	exist[cname];
	if(sname.size())exist[cname].F=sname;
	cout<<in<<endl;
      }else if(in.substr(0,3)=="def"){
	string cname=in.substr(4,in.find('.')-4);
	string mname=in.substr(in.find('.')+1);

	if(exist.count(cname)==0){
	  cout<<"oops!"<<endl;
	  continue;
	}
	if(exist[cname].S.count(mname)){
	  cout<<"redef "<<cname<<'.'<<mname<<endl;
	}else{
	  exist[cname].S.insert(mname);
	  cout<<in<<endl;
	}

      }else if(in.substr(0,5)=="undef"){
	string cname=in.substr(6,in.find('.')-6);
	string mname=in.substr(in.find('.')+1);
	if(exist.count(cname)==0 || exist[cname].S.count(mname)==0){
	  cout<<"oops!"<<endl;
	}else{
	  exist[cname].S.erase(mname);
	  cout<<in<<endl;
	}
      }else{//call
	string cname=in.substr(5,in.find('.')-5);
	string mname=in.substr(in.find('.')+1);
	bool ok=false;
	while(exist.count(cname)){
	  if(exist[cname].S.count(mname)){
	    ok=true;
	    cout<<"invoke "<<cname<<'.'<<mname<<endl;
	    break;
	  }
	  cname=exist[cname].F;
	}
	if(!ok)cout<<"oops!"<<endl;
      }
    }
    cout<<endl;
  }
}

次にIへ。若干TLEが怖かったのですが、要するに、日付を全探索すれば良いということだと思ったので、日付を生成するためにhttp://d.hatena.ne.jp/atetubou/20110324/1300943742からコードを引っ張ってきました。そして、その日付文字列と日付のチェックサムをあらかじめ計算しておきました。

で、ここからバグバグに。

まずおかしかったのは、出力文字列の抽出箇所でした。あとは、添字がところどころおかしかったりしたのですが、一番の問題は日付の生成でした。

まず、日付の生成を2011年4月2日で打ち切らなかったこと。そして、1900年は閏年ではないということをすっかり忘れていたことです。

string day[4000000];
int dayw[4000000];

int mon[]={31,28,31,30,31,30,31,31,30,31,30,31};

int wi[]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1};

main(){
  int y=1900,m=1,d=1;
  int num=0;
  rep(i,4000000){
    if(y==2011 && m==4 && d==3)break;
    ++num;
    int ty=y,tm=m,td=d;
    day[i]+=ty/1000+'0';
    ty%=1000;
    day[i]+=ty/100+'0';
    ty%=100;
    day[i]+=ty/10+'0';
    ty%=10;
    day[i]+=ty+'0';
    day[i]+=tm/10+'0';
    day[i]+=tm%10+'0';
    day[i]+=td/10+'0';
    day[i]+=td%10+'0';
    int tw=0;
    rep(j,8){
      tw+=(day[i][j]-'0')*wi[j+6];
    }
    dayw[i]=tw;
    if(m==12 && d==31){
      y++;
      m=1;
      d=1;
      if((y%4==0 && y%100!=0) || y%400==0)mon[1]=29;
      else mon[1]=28;
      continue;
    }

    if(d==mon[m-1]){
      ++m;
      d=0;
    }
    ++d;
  }
  int t;
  cin>>t;
  while(t--){
    string in;
    cin>>in;
    if(in.size()==15){
      int ans=16,idx=0;
      rep(i,num){
	int tans=0;
	rep(j,6){
	  if(in[j+6]!=day[i][j+2])++tans;
	}
	if(tans<ans){
	  ans=tans;
	  idx=i;
	  if(ans==0)break;
	}
      }
      cout<<in.substr(0,6)<<day[idx].substr(2)<<in.substr(12)<<endl;
    }else{
      int tw=0;
      int ans=16,idx;
      char last;
      rep(i,17){
	if(i==6)i=14;
	tw+=wi[i]*(in[i]-'0');
      }
      rep(i,num){
	int tans=0;
	rep(j,8){
	  if(in[j+6]!=day[i][j])++tans;
	}
	int sw=tw+dayw[i];
	int a=(12-sw%11)%11;
	if((a==10 && in[17]!='X') || (a!=10 && in[17]-'0'!=a))++tans;
	if(tans<ans){
	  ans=tans;
	  idx=i;
	  last=a+'0';
	  if(a==10)last='X';
	}
      }
      cout<<in.substr(0,6)<<day[idx]<<in.substr(14,3)<<last<<endl;
    }
  }
}

これで5問AC

残り時間は1時間ちょっとなので、もう一問くらい解けそうだと思ったのですが、問題文とAC数から判断するに、BかEしか自分には残っていないように思われました。

文字列処理系はDで調子が良かったので、せっかくだからということでEを選んだのですが、WAからPEに変わった後は何をどうやってもPEのままでした。

コンテストが終わってから、問題文をよく読むとtabが出現していた場合の処理を変に分岐させていたので、それを直してからsubmitしてみたものの結局PE。

どこがおかしいのか分からないままモヤモヤしてます。

結局5問解いて、28位でした。1問以上解いている人が404人いるようなのでなかなかいい順位にはつけていたのではないかと思います。まぁ、UVaのコンテストに流れた人が多かったようですけどね!!

2011-03-28

ITRIX 11 OPC

| 11:55

SPOJで行われていたコンテストに参加しました。

5問あったのですが、2問解いたあと、3問目以降が分からずに寝ました。

せっかくなので書いたコードを貼り付けます。

A

  • ヒットアンドブローを文字列に拡張したような問題。
  • 書く。サーバーが非常に重くてなかなか提出できない。
  • やっとつながった。提出。

8分24秒

main(){
  int t;
  cin>>t;
  while(t--){
    string in;
    cin>>in;
    set<int> app;
    rep(i,in.size())app.insert(in[i]);
    int m;
    cin>>m;
    while(m--){
      string a;
      cin>>a;
      int g=0,b=0;
      rep(i,a.size()){
	if(app.count(a[i]))++g;
	if(a[i]==in[i])++b;
      }
      cout<<g<<' '<<b<<endl;
    }
  }
}

B

  • 0のみ、又は2,3,5,7のみからなる数字を小さい順に並べたときに、n番目に来る数を答える問題。
  • AOJにあったPC甲子園の過去問に似たような問題があったので、それを思い出しながら書く。
  • 微妙に数字の変換に戸惑いながら書き切る。
  • 0が来る場合があるかどうかは分からないのですが、一応0がきた場合は"0"を返すようにしてみました。

17分23秒

string luck(ll n){
  if(n==0)return "0";
  string ret;
  do{
    n--;
    ret+=n%4;
    n/=4;
  }while(n);
  rep(i,ret.size()){
    switch(ret[i]){
    case 0:ret[i]='2';break;
    case 1:ret[i]='3';break;
    case 2:ret[i]='5';break;
    case 3:ret[i]='7';break;
    }
  }
  reverse(ALL(ret));
  return ret;
}

main(){
  int t;
  cin>>t;
  while(t--){
    ll n;
    cin>>n;
    cout<<luck(n)<<endl;
  }
}

C

  • 超要約すると、m*m以下の正方行列から縦横にかぶらないようにm個の要素を選び出し、その和を最大化する。というような問題。
  • 愚直にやると15!とかになって終わらない。なんとなく幅優先とかを書いたりしましたが、無理でした。
  • 次に訪れる場所と訪れた場所を持ってdpするというようなことも考えましたが、訪れた場所とその次の状態をうまく生成する方法が分からずに、あきらめました。
  • あとで蟻本を見たら集合の順列の作り方が書いてあったので、練習で通しました。
ll dp[15][1<<15];
ll a[15][15],b[15][15],c[15][15];

main(){
  int t;
  cin>>t;
  while(t--){
    memset(dp,0,sizeof(dp));
    int m;
    cin>>m;
    rep(i,m)rep(j,m)cin>>a[i][j];
    rep(i,m)rep(j,m)cin>>b[i][j];
    rep(i,m)rep(j,m){
      cin>>c[i][j];
      c[i][j]*=min(a[i][j],b[i][j]);
    }

    ll ans=0;
    rep(i,m){
      dp[0][1<<i]=c[i][0];
      ans=max(ans,dp[0][1<<i]);
    }


    for(int i=1;i<m;i++){
      rep(j,m){
	int comb=(1<<i)-1;
	while(comb< (1<<m) ){
	  if(((comb>>j) &1)==0){
	    dp[i][comb|1<<j]=max(dp[i][comb|1<<j],dp[i-1][comb]+c[j][i]);
	    ans=max(dp[i][comb|1<<j],ans);
	  }
	  int x=comb&-comb,y=comb+x;
	  comb=((comb&~y)/x>>1)|y;
	}
      }
    }
    cout<<ans<<endl;
  }
}

2011-02-27

Maximum Winter-Contest 2011

| 10:35

一応参加しましたが、惨敗でした。あんまり思い出したくないですが、書いておきます。

開始

A

  • 蟻本に載っていたしゃくとり法だということを思い出し、本のページをめくりながら書きました。
  • 30分ぐらいかかってアクセプト。

B

  • 読む。
  • いろいろと考えてかかる。
    • 着弾地点が2個以下の時は発射基地が無数にあるのではないか。
    • 同一の点があるのではないか。
    • 並行に3つ並んだ点の出現。
  • 外心の計算が面倒臭かったが、紙に書いて移す。
  • だいたい書いてサンプルが通った後提出してWA
  • ここらへんですでに息切れ。

C

  • 解いている人が多い。
  • 読む。ナップザックっぽい。が、どうすればいいのかよく分からない。
  • ダイクストラっぽくやろうとした。
    • 書いたやつがバグっていて、あまりに汚かったので、直す気力が尽きた。

G

  • これも解いている人多い。
  • 読む。BFSすれば終わりか?
  • 書く。サンプルでた。
  • 出す。RE。上の階が無いときも上に行こうとしてた。
  • 修正。WA。もうダメだ。
  • 取り敢えずソースコードとにらめっこしてましたが、どこがだめなのか分からず・・・。

F

  • これもそこそこ解いている人いるなぁ。
  • 読む。BITだというのはすぐ分かったけれど、一次元もろくに実装したことのない自分には無理でした。

こんな感じで結局1問しか解けずに終了しました。

なにはともあれ、コンテストを開いてもらえたのはとてもありがたかったと思います。