第8回情報オリンピック予選速報入ります

今年は難しかったと思う。一昨年去年と続いて予選満点の自分が今年満点じゃないのを証拠に挙げておく。

死んだー＼(^o^)／

あと、解答が正しい保証はないです。それと、間違いを指摘すると泣きますが、構わないのでばしばし撃墜してください。別にMじゃありません。

ああ、それと、ネットワークアクセス禁止にもかかわらず堂々とTwitterで喋ってる奴ら自重しろ。

何、お前はなんで知ってるかって？そりゃ、開発台とは別のPCでTwitterのTLのログをしっかり取ってるから、試験中はアクセスしてないんだよこれがね！！

そうそう、僕の解答を丸ごとアーカイブしたのを置いておく。

http://acikelabo.org/joi2009-yo.tar.gz

第一問

出社時刻と退社時刻から、会社にいた時間を計算する。値はすべて"h m s"形式。

ただの処理ゲー。

#include <cstdio>

using namespace std;

int main(int argc, char* argv[], char* envp[])
{
	for(int i=0;i<3;i++) {
		int sh,sm,ss,eh,em,es;
		scanf("%d %d %d %d %d %d\n",&sh,&sm,&ss,&eh,&em,&es);
		int span=(eh-sh)*3600+(em-sm)*60+(es-ss);
		printf("%d %d %d\n",span/3600,(span/60)%60,span%60);
	}
	return 0;
}

第二問

10個の値のうち大きい３つの和を求める。それを2回やる。それだけ。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char* argv[], char* envp[])
{
	vector<int> univs(2);
	for(unsigned int i=0;i<univs.size();i++) {
		vector<int> pts(10);
		for(unsigned int j=0;j<pts.size();j++) {
			scanf("%d\n", &pts[j]);
		}
		sort(pts.begin(),pts.end());
		univs[i]=pts[9]+pts[8]+pts[7];
	}
	printf("%d %d\n",univs[0],univs[1]);
	return 0;
}

第三問

1次元版ぷよぷよ。三色ぷよの列があって、４つ繋がると消える。

初期状態から一つだけぷよの色を変えることで連鎖をさせる。一番よくて何個まで消せるか。ただし答えるのは消した数ではなく消した残りの数。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>


using namespace std;


int main(int argc, char* argv[], char* envp[])
{
	unsigned int charas_len;
	scanf("%d\n",&charas_len);
	vector<int> charas(charas_len);
	for(unsigned int i=0;i<charas.size();i++) {
		scanf("%d\n",&charas[i]);
	}
	int min_span=charas_len;
	for(unsigned int i=0;i<charas.size();i++) {
		int orig_chara=charas[i];
		if(i>=1 && charas[i-1]!=orig_chara) {
			charas[i]=charas[i-1];
			unsigned int begin=i,end=i+1;
			int span_len=charas_len;
			while(true) {
				span_len=charas_len-(end-begin)+1;
				if(begin<0)break;
				int current_chara=charas[begin];
				int current_power=0;
				for(;begin>=0 && charas[begin]==current_chara;begin--) {
					current_power++;
				}
				for(;end<charas_len && charas[end]==current_chara;end++) {
					current_power++;
				}
				if(current_power<4)break;
			}
			//printf("%d if charas[%d] == %d\n",span_len,i,charas[i-1]);
			if(min_span>span_len) min_span = span_len;
		}
		if(i<charas_len-1 && charas[i+1]!=orig_chara) {
			charas[i]=charas[i+1];
			unsigned int begin=i,end=i+1;
			int span_len=charas_len;
			while(true) {
				span_len=charas_len-(end-begin)+1;
				if(begin<0)break;
				int current_chara=charas[begin];
				int current_power=0;
				for(;begin>=0 && charas[begin]==current_chara;begin--) {
					current_power++;
				}
				for(;end<charas_len && charas[end]==current_chara;end++) {
					current_power++;
				}
				if(current_power<4)break;
			}
			//printf("%d if charas[%d] == %d\n",span_len,i,charas[i-1]);
			if(min_span>span_len) min_span = span_len;
		}
		charas[i]=orig_chara;
	}
	printf("%d\n",min_span);
	return 0;
}

第四問

与えられた形状のフィールドで、上下左右に動けるとき、任意の場所から開始して最大何歩まで歩けるか。同じ場所は通れない。

再帰を使ってないのはただのバカ。あたいって最強うわなにすr

#include <cstdio>
#include <vector>

using namespace std;

const int directions_x[] = {1,0,-1,0};
const int directions_y[] = {0,-1,0,1};

int main(int argc,char* argv[],char* envp[])
{
	int m,n;
	scanf("%d\n",&m);
	scanf("%d\n",&n);
	vector<vector<int> > table(m,vector<int>(n));
	for(int y=0;y<n;y++) {
		for(int x=0;x<m;x++) {
			scanf("%d",&table[x][y]);
		}
	}
	vector<int> footdirections(n*m);
	vector<pair<int,int> > footprints(n*m);
	int maxdepth=0;
	for(int sy=0;sy<n;sy++) {
		for(int sx=0;sx<m;sx++) {
			//fprintf(stderr, "%d,%d\n",sx,sy);
			if(!table[sx][sy])continue;
			int depth=0;
			int x=sx;
			int y=sy;
			footdirections[0]=0;
			while(true) {
				//fprintf(stderr, " %d:%d,%d\n",depth,x,y);
				if(footdirections[depth]==4) {
					footdirections[depth]=0;
					if(depth==0)break;
					depth--;
					x=footprints[depth].first;
					y=footprints[depth].second;
					table[x][y]=1;
				} else if(0<=x && x<m && 0<=y && y<n && table[x][y]&1) {
					if(depth>maxdepth)maxdepth=depth;
					table[x][y]=2;
					footprints[depth]=pair<int,int>(x,y);
					x+=directions_x[footdirections[depth]];
					y+=directions_y[footdirections[depth]];
					footdirections[depth]++;
					depth++;
					footdirections[depth]=0;
				} else {
					footdirections[depth]=0;
					if(depth==0)break;
					depth--;
					x=footprints[depth].first;
					y=footprints[depth].second;
					table[x][y]=1;
				}
			}
		}
	}
	printf("%d\n",maxdepth+1);
	return 0;
}

第五問

シャッフルして、条件に一致するカードの枚数を数えるんだけど、カードの枚数が異様に多いので、連結リスととかで同種のカードをまとめて管理するなどする。

#include <cstdio>
#include <vector>

using namespace std;

struct block
{
	int length;
	int color;
	block* next;
	block* cut(int offset,block* newblock) {
		newblock->length=this->length-offset;
		newblock->color=this->color;
		newblock->next=this->next;
		this->length=offset;
		this->next=newblock;
		return newblock;
	}
	block() : length(0),color(0),next(NULL) {}
	block(int len,int col,block* nex) : length(len),color(col),next(nex) {
		
	}
};

int main(int argc,char* argv[],char* envp[])
{
	int n,m,p,q,r;
	scanf("%d\n",&n);
	scanf("%d\n",&m);
	scanf("%d %d %d\n",&p,&q,&r);
	vector<block> blocks(3+m*2);
	blocks[0]=block(r,1,&blocks[1]);
	blocks[1]=block(n-r,0,NULL);
	int blocks_len=2;
	block* start=&blocks[0];
	for(int i=0;i<m;i++) {
		int xi,yi;
		scanf("%d %d\n",&xi,&yi);
		block* start0=start;
		block* start1;
		block* start2;
		block* current=start;
		block* end0;
		block* end1;
		block* end2;
		int cxi=xi;
		int cyi=yi;
		int cend=n;
		while(true) {
			if(cxi<current->length) {
				end0=current;
				start1=current->cut(cxi,&blocks[blocks_len++]);
				break;
			}
			cxi-=current->length;
			cyi-=current->length;
			cend-=current->length;
			current=current->next;
		}
		while(true) {
			if(cyi<current->length) {
				end1=current;
				start2=current->cut(cyi,&blocks[blocks_len++]);
				break;
			}
			cyi-=current->length;
			cend-=current->length;
			current=current->next;
		}
		while(true) {
			if(current->next==NULL) {
				end2=current;
				break;
			}
			cend-=current->length;
			current=current->next;
		}
		start=start2;
		end2->next=start1;
		end1->next=start0;
		end0->next=NULL;
	}
	block* cur=start;
	int position=0;
	int sum_p=0;
	int sum_q=0;
	p--;
	while(cur) {
		//printf("%dlen, %dcolor\n",cur->length,cur->color);
		int next_position=position+cur->length;
		if(cur->color==1) {
			if(p>next_position) {
				sum_p+=cur->length;
			} else if(p>position) {
				sum_p+=p-position;
			}
			if(q>next_position) {
				sum_q+=cur->length;
			} else if(q>position) {
				sum_q+=q-position;
			}
		}
		position=next_position;
		cur=cur->next;
	}
	//printf("%d-%d\n",sum_q,sum_p);
	printf("%d\n",sum_q-sum_p);
	return 0;
}

第六問

時間がなかったので全探索での不完全解答。これはひどい。

#include <cstdio>
#include <vector>

using namespace std;

int n,m,s;
int patterns=0;
vector<int> bng;

void search(int depth,int from,int rest) {
	if(depth==n*n) {
		if(rest==0) {
			patterns++;
		}
		return;
	}
	for(int i=from+1;i*(n*n-depth)<=rest;i++) {
		bng[depth]=i;
		search(depth+1,i,rest-i);
	}
}

int main(int argc,char* argv[],char* envp[])
{
	scanf("%d %d %d\n",&n,&m,&s);
	bng=vector<int>(n*n);
	search(0,0,s);
	printf("%d\n",patterns%100000);
	return 0;
}