パソコン甲子園2011 予選
やってました。10個もゴミをまとめてくれてありがとうございます。ゴミじゃない問題はいつになったら登場するのですか? 初登場をこの目で見てみたいものです。
前回と同じでHziwarAとチームを組んで参加しています。
さすがにこれは冗談でした→ http://twitpic.com/6fa6ga
1. 勉強時間がどうとか
書くだけ
#include<stdio.h> int main(){ int a; while(scanf("%d",&a),a){ int b; scanf("%d",&b); int val=0; for(int i=0;i<b;i++){ int c,d; scanf("%d%d",&c,&d); val+=d-c; } if(val>=a)printf("OK\n"); else printf("%d\n",a-val); } }
2.カロリーがどうとか
書くだけ
#include<stdio.h> int b[1000],c[1000],d[1000],e[1000]; int main(){ int a; while(scanf("%d",&a),a){ for(int i=0;i<a;i++)scanf("%d%d%d%d",b+i,c+i,d+i,e+i); int C,D,E,F; scanf("%d%d%d%d",&C,&D,&E,&F); bool ok=false; for(int i=0;i<a;i++){ if(c[i]<=C&&d[i]<=D&&e[i]<=E&&c[i]*4+d[i]*9+e[i]*4<=F){ ok=true; printf("%d\n",b[i]); } } if(!ok)printf("NA\n"); } }
3.金利
書くだけ。Monetoうるさい。
#include<stdio.h> #include<math.h> int main(){ int a,b; while(scanf("%d",&a),a){ scanf("%d",&b); double m=0; int ret=0; for(int i=0;i<a;i++){ int c,d,e; scanf("%d%d%d",&c,&d,&e); if(e==1){ double f=1+(double)d*b/100; if(f>m){ m=f; ret=c; } }else{ double f=pow((1.0+(double)d/100),b); if(f>m){ m=f; ret=c; } } } printf("%d\n",ret); } }
4.四元数
数学知識あると問題文読まなくても解けるのではと思ったのでHziwarAに投げる。
5.生ゴミ
文字列。変な実装をする。Javaに頼った。Javaに頼るとやるだけでCEもWAもないはず。
import java.util.*; class Main{ public static void main(String args[]){ Scanner s=new Scanner(System.in); while(true){ HashMap<String,Integer>map=new HashMap<String,Integer>(); String p=s.nextLine(); if(p.equals("0"))System.exit(0); String q=s.nextLine(); char r=q.charAt(0); String [] str=p.split(" "); Arrays.sort(str); String ans[]=new String[str.length]; int now=0; int len=0; int mm=0; for(int i=0;i<str.length;i++){ if(str[i].charAt(0)==r&&!map.containsKey(str[i])){ len++; map.put(str[i],1); ans[now++]=str[i]; mm=Math.max(mm,map.get(str[i])); }else if(str[i].charAt(0)==r){ map.put(str[i],map.get(str[i])+1); mm=Math.max(mm,map.get(str[i])); } } int count=0; boolean panai=false; for(int i=mm;i>0;i--){ for(int j=0;j<now;j++){ if(map.get(ans[j])==i){ if(panai)System.out.print(" "); System.out.print(ans[j]); panai=true; count++; map.put(ans[j],0); if(count==5)break; } } if(count==5)break; } if(!panai)System.out.print("NA"); System.out.println(); } } }
6.色がどうのこうの
どうせPCKだし全探索だろうが、面倒なのでHziwarAに投げる。
7.温泉旅行
たけし。事前に2Stepでいけるところを計算しておいて後は2段でDijkstra。実装とかデバッグとか読解とか(これが一番難)厳しい。
#include<stdio.h> #include<queue> #include<algorithm> #include<vector> using namespace std; vector<pair<int,int > > g[100]; int ijk[2][100]; bool visited[2][100]; bool can[100][100]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a+b){ for(int i=0;i<100;i++)g[i].clear(); for(int i=0;i<100;i++) for(int j=0;j<100;j++) can[i][j]=false; for(int i=0;i<b;i++){ int c,d,e; scanf("%d%d%d",&c,&d,&e); g[c-1].push_back(make_pair(d-1,e)); g[d-1].push_back(make_pair(c-1,e)); } for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ for(int k=0;k<g[g[i][j].first].size();k++){ can[i][g[g[i][j].first][k].first]=true; // printf("%d %d\n",i,g[g[i][j].first][k].first); } } } priority_queue<pair<int,pair<int,int > > >Q;// cost type at Q.push(make_pair(0,make_pair(0,0))); Q.push(make_pair(0,make_pair(1,0))); for(int i=0;i<a;i++)ijk[0][i]=ijk[1][i]=999999999; ijk[0][0]=ijk[1][0]=0; for(int i=0;i<a;i++)visited[0][i]=visited[1][i]=false; while(Q.size()){ int cost=-Q.top().first; int type=Q.top().second.first; int at=Q.top().second.second; Q.pop(); if(visited[type][at])continue; visited[type][at]=true; // printf("%d %d %d\n",type,at,ijk[type][at]); for(int i=0;i<g[at].size();i++){ if(!visited[type][g[at][i].first]&&ijk[type][at]+g[at][i].second<ijk[type][g[at][i].first]){ ijk[type][g[at][i].first]=ijk[type][at]+g[at][i].second; Q.push(make_pair(-cost-g[at][i].second,make_pair(type,g[at][i].first))); } } if(!type){ for(int i=0;i<a;i++){ if(can[at][i]&&!visited[1][i]&&ijk[0][at]<ijk[1][i]){ ijk[1][i]=ijk[0][at]; Q.push(make_pair(-cost,make_pair(1,i))); } } } } printf("%d\n",min(ijk[0][a-1],ijk[1][a-1])); } }
8.タイムセール?
HziwarAが解くとか言うので投げる。
9.饅頭
10.氷
時間そんなに無いって。
Result(?)
12345678(WA1)の8完68点。semiexpには当然勝てない。
まあ悪問ですよね。