SuperCon2013予選

こんにちは。

朗報です。

SuperCon2013本選西日本地区にチームAkaKDanCとして出場することが決まりました。
チームメンバーは@chigichan24、@Pelkira、後輩君です。
相方さんの記事
ということで、SuperConに出場する方はよろしくお願いしますなのです。

今年の予選問題について少し。
問題はhttp://www.gsic.titech.ac.jp/supercon/main/attwiki/index.php?Supercomputing%20Contest%202013#u5caeb77　です。

要約すると、スタートからゴールまで(右に行ったマス-左に行ったマス)を最大にしていくという問題です。これ愚直にすると2^30くらいかかると思うんですけど、うまく枝狩り?(厳密にはできていない)すればかなり早くなりました。僕が始めに書いたコードはこんなんです

僕のコード

#include <stdio.h>
#include <string.h>
//#include <windows.h>
#include "sc13.h"

#define N 5

int stage[8][32];
int path[128];
int ans[128];
int ma = -10000;
int num = 0;

void check(int cnt,int cost){
    int i;
	if(ma < cost){
        for(i = 0; i < cnt+1 ; i++){
            ans[i] = path[i];
        }
        num = cnt+1;
        ma = cost;
	}
    return ;
}
void dfs(int th,int now,int cnt,int cost){
    int i;

    path[cnt] = now;
    for(i = 0; i < cnt; i++)if(path[cnt] == path[i])return ;
    if(cnt > 29)return ;
    if(now == 29){
        check(cnt,cost);
        return ;
    }

    if(path[cnt] > 15 && (now+stage[th][now])%30 < 14)dfs(th,(now+stage[th][now])%30,cnt+1,cost+1);
    else dfs(th,(now+stage[th][now])%30,cnt+1,cost);

    if(now-stage[th][now] >= 0)dfs(th,now-stage[th][now],cnt+1,cost);
    else dfs(th,30+(now-stage[th][now]),cnt+1,cost-1);

    return ;
}
int main(void){
	int i,j;
	//int t = timeGetTime();

	for(i = 0; i < N; i++){
        for(j = 0; j < 30; j++){
            scanf("%d",&stage[i][j]);
        }
	}

    for(i = 0; i < N; i++){
        memset(path,0,sizeof(path));
	memset(ans,0,sizeof(ans));
        dfs(i,0,0,0);
        sc_output(num,ans);
        num = 0;
        ma = -10000;
    }
    //printf("%d ms\n",timeGetTime()-t);
	return 0;
}

こんなんでしたね(コメントアウトそのまんま)。これのダメな点は
・check()関数に毎回渡してるので遅い。
・今まで通ってきた経路をフラグではなく保存しながら潜っているので遅い。

それでも、input5つ位なら、0ms余裕だったので、どうやって差がついたのかは未だに不思議です。
そこで、部内では5000個くらい走らせて速度を見ると...
僕→192ms
Pelkira→69ms
というように圧倒的に相方さんのほうが速かったようでした。
少し改善して、僕のコードも74msまで速くなりましたが、結局、相方さんの方を提出しました。

最後に提出したコード

#include<stdio.h>
#include"sc13.h"
int pel[30];
int depth = 0;
int max = -1000000;
void dfs(int now,int ans,int dep,int *path,int *data,int *flg){
    int i,x,y;
    if(now == 29){
        if(ans > max){
            int p;
            max = ans;
            depth = dep + 1;
            path[depth-1] = 29;
            p = depth;
            while(p--)pel[p] = path[p];
            pel[0] = path[0];
        }
        return;
    }

    x = now + data[now];
	if(x >= 30)x -= 30;
    if(!flg[x]){
        path[dep] = now;
        y = ans + data[now];
        flg[x] = 1;
        dfs(x,y,dep+1,path,data,flg);
        flg[x] = 0;
    }
    x = now - data[now] ;
	if(x < 0) x += 30;
    if(!flg[x]){
        path[dep] = now;
        y = ans - data[now];
        flg[x] = 1;
        dfs(x,y,dep+1,path,data,flg);
        flg[x] = 0;
    }
    return;
}
int main(void){
    int path[30]={0};
    int flg[30]={1};
    int data[30];
    int i,q=5;
    while(q--){
    	max = -1000000;
        depth = 0;
        for(i=0;i<30;i++)scanf("%d",&data[i]);
        dfs(0,0,0,path,data,flg);
        sc_output(depth,pel);
    }
    return 0;
}

pelとか個性的な配列があるのがいいですね(あくまでも個人的な感想)

最後に
・予選の順位とか知りたいなー(おそらく一位タイとかだろうな)
・マラソンチックなのも楽しい
・剰余算って意外と遅い
・高速化も楽しい
・資料作成時に寝落ちしたので相方さんに深くお詫び申し上げます
・今年は開成とか灘とか府立とかいないので賞狙います(宣言)

日本語力の無さがモロにでている文章でしたが最後まで読んでくださってありがとうございました。