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

SuperCon2016予選

SuperCon予選通過したので書きます。

・問題

数独を少し拡張したような魔法陣の問題です。6×6のマスに空白が15個開くので、魔方陣になるように数字を埋めるという問題でした。魔方陣を初めて知った。詳しくはリンク先へ。

http://www.gsic.titech.ac.jp/supercon/main/attwiki/index.php?plugin=attach&refer=SupercomputingContest2016&openfile=yosen.pdf 

 

まず最初は適当に再帰で書いてみたら、解くのに2分かかった。それから、「空白少ないとこから探せばいいんじゃね?」と言われたので書いたら速くなった。とてもありがたい。そのあと「5個埋まってたら残り1個は確定でしょ」とか「斜めから探したほうが速いんじゃね?」とか、いろいろ汚く書いてたらチョー速くなった。速くするためにswitchを使いました。ゆるして

結果はノートPCで平均20μsくらい?で最悪ケースでもだいたい150μsになりました。(ちゃんと測ってない)

通過できて良かったです。

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include "sc1.h"
#define MAXSQ 111

int space(int sq[N][N],int *x,int *y)
{
	register int i,j,cou = 0;
	int max = N,kakux,kakuy;
	for(i = 0;i < N;i++)
	{
		if(sq[i][i] == 0)
		{
			*x = *y = i;
			++cou;
		}
	}
	if(cou == 1)
	{
		return 1;
	}
	else if(max > cou && cou > 0)
	{
		max = cou;
		for(i = 0;i < N;i++)
		{
			if(sq[i][i] == 0)
			{
				kakux = kakuy = i;
				break;
			}
		}
	}
	cou = 0;
	for(i = 0;i < N;i++)
	{
		if(sq[i][5 - i] == 0)
		{
			*x = i;
			*y = 5 - i;
			++cou;
		}
	}
	if(cou == 1)
	{
		return 2;
	}
	else if(max > cou && cou > 0)
	{
		max = cou;
		for(i = 0;i < N;i++)
		{
			if(sq[i][5 - i] == 0)
			{
				kakux = i;
				kakuy = 5 - i;
				break;
			}
		}
	}
	for(i = 0;i < N;i++)	//たて
	{
		cou = 0;
		for(j = 0;j < N;j++)
		{
			if(sq[j][i] == 0)
			{
				*x = j;
				*y = i;
				++cou;
			}
		}
		if(cou == 1)
		{
			return 3;
		}
		else if(max > cou && cou > 0)
		{
			max = cou;
			for(j = 0;j < N;j++)
			{
				if(sq[j][i] == 0)
				{
					kakux = j;
					kakuy = i;
					break;
				}
			}
		}
	}
	for(i = 0;i < 6;i++)	//よこ
	{
		cou = 0;
		for(j = 0;j < 6;j++)
		{
			if(sq[i][j] == 0)
			{
				*x = i;
				*y = j;
				++cou;
			}
		}
		if(cou == 1)
		{
			return 4;
		}
		else if(max > cou && cou > 0)
		{
			max = cou;
			for(j = 0;j < 6;j++)
			{
				if(sq[i][j] == 0)
				{
					kakux = i;
					kakuy = j;
					break;
				}
			}
		}
	}
	if(*x == -1 && *y == -1)
	{
		return 0;
	}
	else
	{
		*x = kakux;
		*y = kakuy;
		return 5;
	}
}

int saiki(int sq[N][N],int used[37],int nana1,int nana2,int tate[6],int yoko[6])
{
	int x = -1,y = -1;
	int nanaflag = 0;
	int i,j;
	int dai;
	register int daina1,daina2,daita,daiyo;
	switch(space(sq,&x,&y))
	{
		case 0:	//終了
		{
			output(s);
			exit(0);
		}
		case 1:	//斜め確定1
		{
			dai = MAXSQ - nana1;
			if(dai > MAXSQ || dai < 0)
				return 0;
			if(used[dai])
				return 0;
			daina1 = nana1 + dai;
			daita = tate[y] + dai;
			daiyo = yoko[x] + dai;
			if(daiyo > MAXSQ || daita > MAXSQ || daina1 > MAXSQ)
				return 0;
			nana1 = daina1;
			tate[y] = daita;
			yoko[x] = daiyo;
			sq[x][y] = dai;
			used[dai] = 1;
			saiki(sq,used,nana1,nana2,tate,yoko);
			sq[x][y] = 0;
			yoko[x] -= dai;
			tate[y] -= dai;
			nana1 -= dai;
			used[dai] = 0;
			return 0;
		}
		case 2:	//斜め確定2
		{
			dai = MAXSQ - nana2;
			if(dai > MAXSQ || dai < 0)
				return 0;
			if(used[dai])
				return 0;
			daina2 = nana2 + dai;
			daita = tate[y] + dai;
			daiyo = yoko[x] + dai;
			if(daita > MAXSQ || daiyo > MAXSQ || daina2 > MAXSQ)
				return 0;
			nana2 = daina2;
			tate[y] = daita;
			yoko[x] = daiyo;
			sq[x][y] = dai;
			used[dai] = 1;
			saiki(sq,used,nana1,nana2,tate,yoko);
			sq[x][y] = 0;
			yoko[x] -= dai;
			tate[y] -= dai;
			nana2 -= dai;
			used[dai] = 0;
			return 0;
		}
		case 3:	//縦確定
		{
			dai = MAXSQ - tate[y];
			if(dai > MAXSQ || dai < 0)
				return 0;
			if(used[dai])
				return 0;
			daita = tate[y] + dai;
			daiyo = yoko[x] + dai;
			daina1 = nana1 + dai;
			daina2 = nana2 + dai;
			if(x == y)
			{
				if(daiyo > MAXSQ || daita > MAXSQ || daina1 > MAXSQ)
					return 0;
				nana1 = daina1;
				nanaflag = 1;
			}
			else if(x + y == 5)
			{
				if(daiyo > MAXSQ || daita > MAXSQ || daina2 > MAXSQ)
					return 0;
				nana2 = daina2;
				nanaflag = 2;
			}
			else
			{
				if(daiyo > MAXSQ || daita > MAXSQ)
					return 0;
			}
			tate[y] = daita;
			yoko[x] = daiyo;
			sq[x][y] = dai;
			used[dai] = 1;
			saiki(sq,used,nana1,nana2,tate,yoko);
			sq[x][y] = 0;
			yoko[x] -= dai;
			tate[y] -= dai;
			if(nanaflag == 2)
				nana2 -= dai;
			else if(nanaflag == 1)
				nana1 -= dai;
			used[dai] = 0;
			return 0;
		}
		case 4:	//横確定
		{
			dai = MAXSQ - yoko[x];
			if(dai > MAXSQ || dai < 0)
				return 0;
			if(used[dai])
				return 0;
			daita = tate[y] + dai;
			daiyo = yoko[x] + dai;
			daina1 = nana1 + dai;
			daina2 = nana2 + dai;
			if(x == y)
			{
				if(daiyo > MAXSQ || daita > MAXSQ || daina1 > MAXSQ)
					return 0;
				nana1 = daina1;
				nanaflag = 1;
			}
			else if(x + y == 5)
			{
				if(daiyo > MAXSQ || daita > MAXSQ || daina2 > MAXSQ)
					return 0;
				nana2 = daina2;
				nanaflag = 2;
			}
			else
			{
				if(daiyo > MAXSQ || daita > MAXSQ)
					return 0;
			}
			tate[y] = daita;
			yoko[x] = daiyo;
			sq[x][y] = dai;
			used[dai] = 1;
			saiki(sq,used,nana1,nana2,tate,yoko);
			sq[x][y] = 0;
			yoko[x] -= dai;
			tate[y] -= dai;
			if(nanaflag == 2)
				nana2 -= dai;
			else if(nanaflag == 1)
				nana1 -= dai;
			used[dai] = 0;
			return 0;
		}
		case 5:	//探索
		{
			for(i = 1;i <= 36;i++)
			{
				if(used[i])
					continue;
				daita = tate[y] + i;
				daiyo = yoko[x] + i;
				daina1 = nana1 + i;
				daina2 = nana2 + i;
				if(x == y)
				{
					if(daiyo > MAXSQ || daita > MAXSQ || daina1 > MAXSQ)
						return 0;
					nana1 = daina1;
					nanaflag = 1;
				}
				else if(x + y == 5)
				{
					if(daiyo > MAXSQ || daita > MAXSQ || daina2 > MAXSQ)
						return 0;
					nana2 = daina2;
					nanaflag = 2;
				}
				else
				{
					if(daiyo > MAXSQ || daita > MAXSQ)
						return 0;
				}
				tate[y] = daita;
				yoko[x] = daiyo;
				sq[x][y] = i;
				used[i] = 1;
				saiki(sq,used,nana1,nana2,tate,yoko);
				sq[x][y] = 0;
				yoko[x] -= i;
				tate[y] -= i;
				if(nanaflag == 2)
					nana2 -= i;
				else if(nanaflag == 1)
					nana1 -= i;
				used[i] = 0;
			}
			return 0;
		}
	}
}

int main(void)
{
	input(s);
	int used[37] = {}, nana1 = 0,nana2 = 0,tate[6] = {},yoko[6] = {};
	register int i,j;
	for(i = 0;i < 6;i++)
	{
		for(j = 0;j < 6;j++)
			used[s[i][j]] = 1;
	}
	for(i = 0;i < 6;i++)
	{
		nana1 += s[i][i];
		nana2 += s[i][5 - i];
		for(j = 0;j < 6;j++)
		{
			tate[i] += s[j][i];
			yoko[i] += s[i][j];
		}
	}
	saiki(s,used,nana1,nana2,tate,yoko);
	return 0;
}

 

・反省

12日まで一切書かなかったのが痛い。5徹はさすがにきつかった。次に何かのプロコンに参加するときには計画的に進めていこうと思った。コードが絶望的に汚い。しかも提出したやつがミスってることにこれ書く前に気づいた。こういうミスもなくしていきたい。勉強します。

本戦がんばるぞい