PCK 2015 予選
9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。
1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした)
8ほぼ書き終わってたのに間に合わなくて辛い(TrieでやるとMLEするらしいのでどの道通せてなかったかも)
おそらく4位。去年より順位下がってつらい。
1 やるだけ
int main() { int p,m,c; cin >> p >> m >> c; cout << p+m+c << endl; return 0; }
2 やるだけ
int h1,h2; int k1,k2; int a,b,c,d; int main() { scanf("%d %d",&h1,&h2); scanf("%d %d",&k1,&k2); scanf("%d %d %d %d",&a,&b,&c,&d); int h = 0,k = 0; h = h1*a+h2*b+(h1/10)*c+(h2/20)*d; k = k1*a+k2*b+(k1/10)*c+(k2/20)*d; if(h>k)printf("hiroshi\n"); else if(k>h)printf("kenjiro\n"); else printf("even\n"); return 0; }
3 やるだけ
int D,L; int main() { scanf("%d %d",&D,&L); printf("%d\n",(D/L)+(D%L)); return 0; }
4 やるだけ
int N; int a[105]; int main() { memset(a,0,sizeof(a)); scanf("%d",&N); for(int i=0;i<3;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int val; scanf("%d",&val); val--; a[val]|=(1<<i); } } int ans = 0; for(int i=0;i<N;i++) { //printf("%d %d\n",i,a[i]); if(a[i]==7||a[i]==6||a[i]==4)ans++; } printf("%d\n",ans); return 0; }
5 やるだけ
int N; int p[105]; int imos[105]; int main() { scanf("%d",&N); for(int i=0;i<N;i++)scanf("%d",&p[i]); for(int i=0;i<N;i++)imos[p[i]]++; for(int i=100;i>0;i--)imos[i-1]+=imos[i]; for(int i=100;i>=0;i--)if(imos[i]>=i) { printf("%d\n",i); return 0; } return 0; }
6 やるだけ
int C,N; char ch[1010][1010]; int f[1010][1010]; bool ok[1010][1010]; int bad = 0; bool check(int x,int y) { if(f[x][y]==f[x][N-1-y]&&f[x][y]==f[N-1-x][y]&&f[x][y]==f[N-1-x][N-1-y])return true; return false; } int ans = 0; int main() { scanf("%d %d",&C,&N); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin >> ch[i][j]; } } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(ch[i][j]=='0')f[i][j]=0; else f[i][j]=1; } } int M = N/2; for(int i=0;i<M;i++) { for(int j=0;j<M;j++) { if(check(i,j))ok[i][j]=true; else { ok[i][j]=false; bad++; } } } if(bad==0)ans++; for(int i=0;i<C-1;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int x,y; scanf("%d %d",&x,&y); x--;y--; f[x][y]^=1; if(x>=M)x=N-1-x; if(y>=M)y=N-1-y; bool d = check(x,y); if(d!=ok[x][y]) { if(d)bad--; else bad++; } ok[x][y]=d; } if(bad==0)ans++; } printf("%d\n",ans); return 0; }
7 UnionFind使うだけ
const int SIZE = 250000; struct UnionFind { int par[SIZE]; void init(int n) { for(int i=0;i<n;i++) { par[i] = i; } } int find(int x) { if(par[x] == x)return x; else return par[x] = find(par[x]); } void unite(int x,int y) { x = find(x); y = find(y); if(x==y)return; if(x > y)par[y] = x; else par[x] = y; } bool same(int x,int y) { return find(x) == find(y); } }uf; int N,M,K; int main() { scanf("%d %d %d",&N,&M,&K); //0 N-1 N N+M-1 uf.init(N+M); for(int i=0;i<K;i++) { int type; int a,b,c,x; scanf("%d",&type); if(type==1) { scanf("%d %d",&a,&b); a--;b--; a = uf.find(a); b = uf.find(b); //cout << a << ' ' << b << endl; if(a>=N&&b>=N&&a!=b) { printf("%d\n",i+1); return 0; } uf.unite(a,b); } else { scanf("%d %d",&c,&x); c--;x--; c = uf.find(c); //cout << c << ' ' << x+N << endl; if(c>=N&&c!=x+N) { printf("%d\n",i+1); return 0; } uf.unite(c,x+N); } } printf("0\n"); return 0; }
8 Trieで数えるだけだと思ったけどロリハじゃないと通らないらしい
9 二分探索
#define INF 100000000 using namespace std; typedef pair<double,double> P; long long x[100000]; long long r[100000]; double min(double a,double b){return a<b?a:b;} double max(double a,double b){return a>b?a:b;} P cross(P a,P b){ return P(max(a.first,b.first),min(a.second,b.second)); } bool solve(double w,int n){ P seg=P(-INF,INF); for(int i=0;i<n;i++){ if(w>r[i])return false; double left=x[i]-sqrt(r[i]*r[i]-w*w); double right=x[i]+sqrt(r[i]*r[i]-w*w); P cseg=cross(seg,P(left,right)); if(cseg.first>cseg.second)return false; else seg=cseg; } return true; } int main(){ int n,i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%lld %lld",&x[i],&r[i]); double bottom=0,top=1000001; for(int bi=0;bi<40;bi++){ double mid=(bottom+top)/2; if(solve(mid,n))bottom=mid; else top=mid; } printf("%.12lf\n",bottom); return 0; }
10 JOI春のオリエンテーリングみたいにトポソして片方先に行かせながらDP
#define INF 1000000000000LL typedef pair<int,int> P; vector<P> re[1000]; int cost1[2000]; int cost2[2000]; bool used[1000]; vector<int> ord; long long dp[1000][1000]; int depth[1000]; long long min(long long a,long long b){return a<b?a:b;} void dfs(int v){ used[v]=true; for(int i=0;i<re[v].size();i++){ int u=re[v][i].first; if(!used[u])dfs(u); } ord.push_back(v); } int main(){ int n,m,i,j,k,l; scanf("%d %d",&n,&m); for(i=0;i<m;i++){ int a,b; scanf("%d %d %d %d",&a,&b,&cost1[i],&cost2[i]); a--;b--; re[b].push_back(P(a,i)); } for(i=0;i<n;i++)used[i]=false; dfs(n-1); for(i=0;i<n;i++)for(j=0;j<n;j++)dp[i][j]=INF; dp[ord[0]][ord[0]]=0; for(i=0;i<n;i++)depth[ord[i]]=i; for(i=0;i<n;i++){ for(j=i;j<n;j++){ int u=ord[i]; int v=ord[j]; if(u!=v){ for(k=0;k<re[v].size();k++){ int w=re[v][k].first; int e=re[v][k].second; if(depth[u]<=depth[w])dp[u][v]=min(dp[u][v],dp[u][w]+cost1[e]); else dp[u][v]=min(dp[u][v],dp[w][u]+cost1[e]); } } else{ for(k=0;k<re[v].size();k++){ for(l=0;l<re[v].size();l++){ int w1=re[v][k].first; int e1=re[v][k].second; int w2=re[v][l].first; int e2=re[v][l].second; if(e1==e2)dp[v][v]=min(dp[v][v],dp[w1][w1]+cost1[e1]+cost2[e1]); else{ if(depth[w1]<=depth[w2])dp[v][v]=min(dp[v][v],dp[w1][w2]+cost1[e1]+cost1[e2]); else dp[v][v]=min(dp[v][v],dp[w2][w1]+cost1[e1]+cost1[e2]); } } } } } } printf("%lld\n",dp[n-1][n-1]); return 0; }