敗戦記

PKU 3640 Conformity

PKU

http://poj.org/problem?id=3640

n人の生徒達の科目選択のリストが渡される。

ここで科目選択の組み合わせのパターンで最も多い組み合わせと同じ組あわせの生徒は何人いるかを答えるというような問題。

最初問題文の意味が把握出来ませんでしたが、なんとか理解してみるとTLEがさけられない。

結局javaへと逃げました。hashmap<long,int>がダメになるというよく分からないエラーが出ましたが、何とかなりました。

import java.util.*;
import java.math.*;
import java.lang.*;

public class Main{

    public static long in[]=new long[10000];
    public static int tin[]=new int[5];
    
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        int n;
        while(true){
            n=cin.nextInt();
            if(n==0)break;
            HashMap<Long,Integer> app=new HashMap<Long,Integer>();
            int max=0;
            for(int i=0;i<n;i++){
                for(int j=0;j<5;j++)tin[j]=cin.nextInt();
                Arrays.sort(tin);
                long t=0;
                for(int j=0;j<5;j++){
                    t=(t<<9)+tin[j];
                }
                if(app.containsKey(t))app.put(t,(int)app.get(t)+1);
                else app.put(t,1);
                in[i]=t;
                max=Math.max(max,app.get(t));
            }
            int ans=0;
            for(int i=0;i<n;i++){
                if(max==app.get(in[i]))++ans;
            }
            System.out.println(ans);
        }
    }
}

Permalink | コメント(0) | トラックバック(0) | 22:13

PKU 2504 Bounding box

PKU

http://poj.org/problem?id=2504

正n角形の3つの頂点の座標が与えられるので、その正n角形をすっぽりと覆う、最小の長方形の面積を答えるというような問題。

ただし、長方形の辺はx軸、y軸に平行とする。

http://www.nn.iij4u.or.jp/~hsat/misc/math/centre/circumcentre.html

外心を求めるのが面倒だったのでこのサイトから式を持ってきました。

いろいろとはまった挙句にサンプルが通ってもWAなので、よくみてみるとPlolygonとかになっていました。

typedef pair<double,double> vec2;

vec2 operator+(const vec2&l,const vec2&r){
  return vec2(l.F+r.F,l.S+r.S);
}

vec2 operator*(const double &l,const vec2&r){
  return vec2(l*r.F,l*r.S);
}

vec2 operator*(const vec2 &l,const double&r){
  return r*l;
}

vec2 operator/(const vec2 &l,const double &r){
  return vec2(l.F/r,l.S/r);
}

vec2 operator-(const vec2&l,const vec2&r){
  return vec2(l.F-r.F,l.S-r.S);
}

double operator*(const vec2&l,const vec2&r){
  return l.F*r.F+l.S*r.S;
}

double norm2(vec2 in){
  return in.F*in.F+in.S*in.S;
}

main(){
  int n;
  int po=0;
  while(cin>>n,n){
    ++po;
    vec2 in[3];
    rep(i,3)cin>>in[i].F>>in[i].S;
    double ed[3];
    rep(i,3)ed[i]=norm2(in[(i+2)%3]-in[(i+1)%3]);
    vec2 a=in[1]-in[0],b=in[2]-in[0];
    double s2=(norm2(a)*norm2(b)-(a*b)*(a*b))/4;
    vec2 q=mp(0,0);
    rep(i,3){
      double add=0;
      rep(j,3){
        if(i==j)add-=ed[j];
        else add+=ed[j];
      }
      add*=ed[i];
      q=q+in[i]*add;
    }
    q=q/(16*s2);
    double theta=atan2(in[0].S-q.S,in[0].F-q.F);
    double r=sqrt(norm2(in[0]-q));
    double maxx=in[0].F,maxy=in[0].S,minx=in[0].F,miny=in[0].S;
    rep(i,n){
      vec2 np=q+vec2(r*cos(theta+i*2*pi/n),r*sin(theta+i*2*pi/n));
      maxx=max(maxx,np.F);
      maxy=max(maxy,np.S);
      minx=min(minx,np.F);
      miny=min(miny,np.S);
    }
    printf("Polygon %d: %.3f\n",po,(maxx-minx)*(maxy-miny));
  }
}

Permalink | コメント(0) | トラックバック(0) | 20:26

PKU 2151 Check the difficulty of problems

PKU

http://poj.org/problem?id=2151

tチームが参加し、m個の問題があるプログラミングコンテストを開く。

この時に、あるチームiが、ある問題jを正解する確率はPijとする。

以下の条件を両方とも満たす確率を求めろというような問題。

・全てのチームが1問以上解く。

・コンテストの優勝チームが最低でもn問以上解く。

多段dp的な問題。

諦めようかと思いましたが、解けたことがすごく嬉しかったので、考えたことを書いてみたいと思います。

まず、あるチームがm問中k問解く確率を求めます。

これはdp[出現した問題数][解いた問題数]という感じで、dpします。

これは

dp[j+1][k]=(問題j+1が解ける確率)*dp[j][k-1]+(問題j+1が解けない確率)*dp[j+1][k]

で求められます。

これで個々のチームがk問正解する確率が求められたので、指定された条件を満たす確率もdpで求めます。

これは

dp[参加したチーム数][n問以上といたチームがあるかないか]という添字で確率を記憶しておけば、

dp[j+1][n問以上解いたチームがある]

=dp[j][n問以上解いたチームがない]*(j+1番目のチームがn問以上正解する確率)+

dp[j][n問以上解いたチームがある]*(j+1番目のチームが1問以上正解する確率)

dp[j+1][n問以上解いたチームがない]

=dp[j][n問以上解いたチームがない]*(j+1番目のチームが1以上n問未満の正解数の確率)

という式が立てられるので、あとはそれを適用するだけです。

２時間以上考えました。動的計画法を多段階的に適用するのが面白く感じました。

double dp[40][40];
double ans[1010][2];

double pp[1000];

main(){
  int m,t,n;
  while(cin>>m>>t>>n,m){
    double p0=1,p1=1;
    memset(ans,0,sizeof(ans));
    ans[0][0]=1;

    rep(i,t){
      memset(dp,0,sizeof(dp));
      dp[0][0]=1;
      rep(j,m){
        cin>>pp[j];
        for(int k=0;k<=j+1;k++){
          dp[j+1][k]=(1-pp[j])*dp[j][k];
          if(k)dp[j+1][k]+=pp[j]*dp[j][k-1];
        }
      }
      double tp1n=0,tpn=0;
      for(int j=1;j<n;j++)tp1n+=dp[m][j];
      for(int j=n;j<=m;j++)tpn+=dp[m][j];
      ans[i+1][0]=ans[i][0]*tp1n;
      ans[i+1][1]=ans[i][1]*(1-dp[m][0])+ans[i][0]*tpn;
    }
    printf("%.3f\n",ans[t][1]);
  }
}

Permalink | コメント(0) | トラックバック(0) | 11:06

PKU 2394 Checking an Alibi

PKU

http://poj.org/problem?id=2394

指定されたノードのうち、ノード1から距離がM以下のものを列挙するというような問題。

ダイクストラやるだけ。

なんですが、コストの初期化をさぼったせいで1WA。

400問解いたあたりでも感じたような気がするんですが、開くたびに解けない感覚に襲われてます、他のonline judgeに逃げたいです。

vector<PI> G[500];
bool vis[500];
int cost[500];

main(){
  int f,p,c,m;
  cin>>f>>p>>c>>m;
  rep(i,f)cost[i]=m+1;

  rep(i,p){
    int f1,f2,t;
    cin>>f1>>f2>>t;
    --f1,--f2;
    G[f1].pb(mp(f2,t));
    G[f2].pb(mp(f1,t));
  }

  priority_queue<PI> q;
  q.push(mp(0,0));

  while(!q.empty()){
    int cc=-q.top().F,v=q.top().S;
    q.pop();
    if(vis[v])continue;
    vis[v]=true;
    cost[v]=cc;
    rep(i,SZ(G[v])){
      int to=G[v][i].F;
      if(vis[to])continue;
      q.push(mp(-cc-G[v][i].S,to));
    }
  }

  set<int> ans;

  rep(i,c){
    int lc;
    cin>>lc;
    --lc;
    if(cost[lc]<=m)ans.insert(i+1);
  }
  cout<<SZ(ans)<<endl;
  FOR(iter,ans)cout<<*iter<<endl;
}

Permalink | コメント(0) | トラックバック(0) | 08:41