tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

パソコン甲子園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には当然勝てない。

まあ悪問ですよね。