Hatena::Grouptopcoder

敗戦記

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形式のコンテストのほうが好きですね。また次があるとしたらさらに問題数が増えて、時間が長くなったりするんでしょうか。なかなか楽しいコンテストでした。