読者です 読者をやめる 読者になる 読者になる

パソコン甲子園2010の予選問題を解く

Programming Algorithm パソコン甲子園

パソコン甲子園は、私自身本来であれば出場資格のある者の筈なのだが、私の通っている高校がたまたま文系一色である故、相方を見付けられない、そもそも過去に出場したためしがないなど、種々の困難に見舞われ、今年は出場する事ができなかった。

そこで、すでに今年の問題が掲載されたとの事なので、出場者のid:kyuridenamidaの誘いもあり一度解いてみる事にした。

パソコン甲子園の過去問
2010yosenn.pdfが今年の予選問題のPDFである。

大体解答時間は9時ぐらいからはじめて休憩やらダラダラ含め12時ごろに6問ぐらいしか解けていなかった。
まあ本選であれば複数人だろうし、仕方がない気もするが、これくらいはサクッと解けないと困るなあという感じがする。

ちなみに当のid:kyuridenamida君の解答:

01 水道料金を節約しよう

not solved
謎バグに悩まされる、しかもきれいに解けない

02 病院でウォーキング

入力データセットの中で最大の物を出力するだけ、である。
1番のほうが圧倒的にむずかしい。おかしいと思う。

#include <cstdio>

int main(){
	int n;
	while(scanf("%d\n", &n), n){
		int max = 0, maxp;
		for(int i = 0; i < n; i++){
			int p, d1, d2;
			scanf("%d %d %d\n", &p, &d1, &d2);
			if(d1 + d2 > max){max = d1 + d2; maxp = p;}
		}
		printf("%d %d\n", maxp, max);
	}
	return 0;
}

03 塾のクラス分け

基本的に条件をif文で実装するだけ、だと思う。だがそういう箇所にバグが混入しやすいので、賢い人はもう少しきれいに実装する事をお勧めする。

#include <cstdio>

int main(){
	int n;
	while(scanf("%d\n", &n), n){
		for(int i = 0; i < n; i++){
			int pm, pe, pj;
			scanf("%d %d %d\n", &pm, &pe, &pj);
			int cls = 2;
			if(((pm + pe + pj) / 3) >= 50 && (pm >= 80 || pe >= 80)){cls = 1;}
			if(((pm + pe + pj) / 3) >= 70){cls = 1;}
			if((pm + pe + pj) / 3 >= 80){cls = 1;}
			if((pm + pe + pj) / 3 >= 80){cls = 0;}
			if((pm + pe) / 2 >= 90){cls = 0;}
			if(pm == 100 || pe == 100 || pj == 100){cls = 0;}
			puts(cls == 0 ? "A" : cls == 1 ? "B" : "C");
		}
	}
	return 0;
}

04 人気のアイスクリーム店

これもアイスクリームは10種類しかないので、単純に実装するだけである。

#include <cstdio>
#include <vector>
using namespace std;
int main(){
	int n;
	while(scanf("%d\n", &n), n){
		vector<int> v(10, 0);
		for(int i = 0; i < n; i++){
			int t;
			scanf("%d\n", &t);
			v[t]++;
		}
		for(int i = 0; i < 10; i++){
			if(v[i] == 0){
				puts("-");
			}else{
				for(int j = 0; j < v[i]; j++) putchar('*');
				puts("");
			}
		}
	}
	return 0;
}

05 博士の愛した2進数

指定された範囲内での、10進小数の2進数表現を出力する問題。範囲内になければNAと出力すればよい。
なんかありえない解き方をしている気がしなくもないが、それでも値の範囲が範囲なので速度的にもどうにかなっている。

#include <cstdio>

int main()
{
	double n;
	while(scanf("%lf\n", &n), !(n < 0)){
		for(int i = 0; i < (1 << 8); i++){
			for(int j = 0; j < (1 << 4); j++){
				int denom = 0, pk = 0;
				for(int k = 3; 0 <= k; k--){
					if((1 << k) & j){
						denom = 1 << (4 - k);
						pk = k;
						break;
					}
				}
				if(((double)i + (double)(j >> pk) / (double)denom) == n){
					for(int k = 7; 0 <= k; k--){
						putchar(i & (1 << k) ? '1' : '0');
					}
					putchar('.');
					for(int k = 3; 0 <= k; k--){
						putchar(j & (1 << k) ? '1' : '0');
					}
					putchar('\n');
					goto l;
				}

			}
		}
		puts("NA");
l:;
	}
	return 0;
}

06 FizzBuzz

フィズバズの名を借りたヨセフスのお芋である。
FizzBuzzの結果と人数を受け取って、間違った人から輪から抜けていくというルールの下、最後に誰が残っているかを出力する。
なんとか一発通過した。
ヨセフスのお芋はまともに解けた試しがないのだが、v.erase(remove(v.begin(), v.end(), n), v.end())記法さえ覚えてしまえば意外と簡単なんじゃないかという気がしてきた。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
enum  NT{NORMAL, FIZZ, BUZZ, FIZZBUZZ};
typedef struct {
	int num;
	NT nt;
} FB;
FB maketruefb(int n){
	FB fb;
	fb.num = 0;
	if(!(n % 3) && !(n % 5)){
		fb.nt = FIZZBUZZ;
	}else if(!(n % 3)){
		fb.nt = FIZZ;
	}else if(!(n % 5)){
		fb.nt = BUZZ;
	}else{
		fb.nt = NORMAL;
		fb.num = n;
	}
	return fb;
}

int main()
{
	int m, n;
	while(cin>>m && cin >> n, m && n){
		vector<FB> v;
		for(int i = 0; i < n; i++){
			FB fb;
			string s;
			cin>>s;
			fb.nt = NORMAL;
			if(!s.compare("Fizz")) fb.nt = FIZZ;
			if(!s.compare("Buzz")) fb.nt = BUZZ;
			if(!s.compare("FizzBuzz")) fb.nt = FIZZBUZZ;
			if(fb.nt == NORMAL){
				fb.num = atoi(s.c_str());
			}else{
				fb.num = 0;
			}
			v.push_back(fb);
		}
		vector<int> person;
		for(int i = 1; i <= m; i++) person.push_back(i);
		int ptr = 0;
		for(int i = 0; i < v.size(); i++){
			FB truefb = maketruefb(i + 1);
			if(truefb.nt != v[i].nt || truefb.num != v[i].num){
				person.erase(remove(person.begin(), person.end(), person[ptr]), person.end());
			}else{
				ptr++;
			}
			ptr = ptr % person.size();
		}
		for(int i = 0; i < person.size(); i++){
			cout<<person[i]<<(i == person.size() - 1 ? '\n' : ' ');
		}
	}
	return 0;
}

07 四つ子素数

以前解いた事のある問題。
何故か配点の割にやたら簡単な問題である。
だが、main中のautoな変数としてchar[10000001]確保しようとしたらsegvした。
globalにしたら解消した。

#include <cstdio>

const int max_pn = 10000001;
char pn[max_pn];
int main()
{
	for(int i = 0; i < max_pn; i++){
		pn[i] = 1;
	}
	pn[0] = 0;
	pn[1] = 0;
	for(int i = 2; i < max_pn; i++){
		if(pn[i]){
			for(int j = i + i; j < max_pn; j += i) pn[j] = 0;
		}
	}

	int n;
	while(scanf("%d\n", &n), n){
		for(int i = n; 13 <= i; i--){
			if(pn[i] && pn[i - 2] && pn[i - 6] && pn[i - 8]){
				printf("%d\n", i);
				break;
			}
		}
	}

	return 0;
}

08

not solved

09

not solved

10

not solved