KUPC 2011(京都大学プログラミングコンテスト) 参加記 - ひよっこプログラマのプログラミング

KUPC 2011

KUPC参加記です。KUPCは京都大学写真部とは関係ないようです。

結果

A,B,C,Dの4問Acceptで、最終順位は48位でした。
私にとって慣れない問題の形式もありましたが、あまりよく考えずにコードを書くのはよくないと思いました。
printf/scanf を使用することを推薦されていたのにiostreamを使っていました、ごめんなさい。

Rank

Time

07:20

00:04 / 0

01:06 / 0

00:38 / 2

04:44 / 37

解説とソースコード

問題A : KUPC

問題文

'K'，'U'，'P'，'C'という文字がいくつあるか調べる問題です。
多くの人が数分で解いていたようです。

ソースコード

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	string s;
	int k=0,u=0,p=0,c=0;

	cin >> s;
	for(int i=0 ; i<s.size() ; i++ ){
		if( s[i] == 'K' ) k++;
		if( s[i] == 'U' ) u++;
		if( s[i] == 'P' ) p++;
		if( s[i] == 'C' ) c++;
	}
	cout << min( k , min( u , min(p,c) ) ) << endl;
}

問題B : 蝉

問題文

左上のN君の家から右下の学校にたどり着くまでに出会う最小の蝉の数を調べる問題です。
動的計画法で各ブロックにたどり着く最小の蝉の数を更新するとよいと思います。
最短経路(最小コスト)を求める問題には慣れておきたいです。

ソースコード

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	int h,w,dp[51][51];
	string s[51];

	cin >> h >> w;
	for(int i=0 ; i<h ; i++ ){
		cin >> s[i];
	}
	for(int y=0 ; y<h ; y++ ){
		for(int x=0 ; x<w ; x++ ){
			dp[y][x] = 10000;
		}
	}
	dp[0][0] = 0;
	for(int y=0 ; y<h ; y++ ){
		for(int x=0 ; x<w ; x++ ){
			if( y != 0 ){
				dp[y][x] = min( dp[y][x] , dp[y-1][x] + (s[y][x]-'0') );
			}
			if( x != 0 ){
				dp[y][x] = min( dp[y][x] , dp[y][x-1] + (s[y][x]-'0') );
			}
		}
	}
	cout << dp[h-1][w-1] << endl;
}

問題C : しりとり

問題文

しりとりをする問題です。相手は必ず2文字以内の単語を返すので、こちらが単語の最後が毎回同じアルファベットで返すようにすると相手は26種類しか正しい返答ができないので必ず勝てると思います。
相手が今まで出た単語を再び言うか正しくしりとりできていない場合に"!OUT"と出力しましょう。

ソースコード

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

map<string,bool> words;
string start;

void answer(string s){
	printf("?%s\n", s.c_str() ); fflush(stdout);
	words[s] = true;
}

bool ask(){
	char str[100];
	scanf("%s", str);
	string s( str );
	
	if( words.count(s) || s[0] != 'a' ){
		printf("!OUT\n"); fflush(stdout);
		return false;
	}else{
		words[s] = true;
		start.clear();
		start.push_back( s[ s.size()-1 ] );
	}
	
	return true;
}

string to_s(int n){
	char c1 = (n%26) + 'a';
	char c2 = n/26 + 'a';
	string s;
	s.push_back( c2 );
	s.push_back( c1 );
	return s;
}

int main(){
	int n=0;

	answer( "a" );
	while( ask() ){
		string s;
		s.push_back( start[0] );
		s += to_s( n++ );
		s.push_back( 'a' );
		answer( s );
	}
}

問題D : 列の構成

問題文

条件を満たす数列(要素は0か1)を出力する問題です。
問題文の意味を理解するのに時間がかかってしまいました。
解が複数存在するので条件を満たす数列になるまで乱数で適当に数列を生成しても通る問題だったようです。乱数を使う方法は無駄が多いので最適な方法を使えばもっと高速に解が求まると思います。

ソースコード

#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std;

int c[501][501];

string random(int n){
	string s;
	for(int i=0 ; i<n ; i++ ){
		s.push_back( rand() % 2 + '0' );
	}
	return s;
}

bool f(string s, int n, int k){
	int sum = 0;
	for(int i=0 ; i<k ; i++ ){
		sum = 0;
		for(int j=0 ; j<n/2 ; j++ ){
			sum += s[ c[i][j]-1 ] - '0';
		}
		if( n/8 <= sum && sum <= 3*n/8 ){
			;
		}else{
			return false;
		}
	}
	return true;
}

int main(){
	int n,k;
	srand((unsigned int)time(NULL));

	cin >> n >> k;
	for(int i=0 ; i<k ; i++ ){
		for(int j=0 ; j<n/2 ; j++ ){
			cin >> c[i][j];
		}
	}
	string s = random(n);
	while( f( s , n , k ) == false ){
		int i_ = rand()%s.size();
		s[i_] = (s[i_]=='0')? '1' : '0';
	}
	cout << s << endl;
}

感想

結果は前回(UAPC)と似たような順位だったのでおそらく実力通りだと思います。
問題Dで一か所おかしいコードがあることに気付かず乱数が悪いのかと勘違いして誤答をたくさん提出して無駄に時間をかけたのは残念でした。まだまだ実力不足で解けない問題がたくさんあるので次回のコンテストまでにたくさん練習したいと思います。