Hatena::ブログ(Diary)

あなたは嘘つきですかと聞かれたら「YES」と答えるブログ このページをアンテナに追加 RSSフィード Twitter

2012-08-30

2012-08-24

supercon参加記 その2

優勝しました!


最初は頭が全く回ってなかったせいもあり、サンプルに騙されてたけど、頭回り出してからは順調に行った。

まずはCPUで正しく動くフローを書こうと思い、ポテンシャルを使ったダイクストラ解法で解いた。

最初に出来たプログラムで既に0.04sくらいで、一番遅いダイクストラ部分が自明に一回減るのでその辺の高速化とかをしたら0.02sくらいになった。

3日目の午前中くらいにはもうデバッグも終わっていたので、GPUによる高速化を考えていた。

グラフに特徴があり、ベルマンフォードでも更新回数が少なくて済むことが分かったので、これを書いてGPU化することにした。

ベルマンフォードは前回更新があった頂点だけ調べるような枝狩りみたいなのもしてCPUだと0.15sくらいだったので、うまく並列化したらいい感じになりそうとか思ってたが、最後までバグが取れずよく分からない。

これと同時くらいに仲間がテストしてくれてて、サンプルと答えがずれるケースをいくつか検出してて焦った。

結局はテストケースジェネレータのミスだったので安心した。

以下コード。

こういうグラフの持ち方すると、逆辺がxor1するだけでわかるので素晴らしい。

詳しくはここにあるスライドにあります

/*******************************************************************
  SuperCon12: Template for input output procedures
  file: sc12_template2E.cu
  by S.Kishimoto and O.Watanabe Aug. 17, 2012
  ver.2 by T.Endo and A.Nukada Aug. 22, 2012

Remark: @@@ for test/tentative statements
*********************************************************************/

/********* Template Part (1) NO CHAGNGE FROM HERE **********/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/time.h>
// @@@ two include statements for CUDA
#include<cuda.h>
#include<cuda_runtime.h>

// @@@
#define MAXlid  5
#define MAXst   40
#define MAXntr  180
#define MAXtd   7
#define MAXtid  6000
// @@@
//#define MAXlid  3
//#define MAXst   20
//#define MAXntr  90
//#define MAXtd   4
//#define MAXtid  4000

#define MAXtm4test 1200
//#define MAXtm4test 120

#define MAXtm   1200
#define MAXtvtm 7
#define MAXstPline 20

//------------
int Nst;
int Ntid;
int maxDist;
short int trainTBnst[MAXtid];
short int trainTB[MAXtid][MAXstPline][3];
int outroute[MAXtm][3][2];

//------------
void input() {
        int i,j,k;
	scanf("%d", &Nst);

	int nlid;
	scanf("%d", &nlid);
	int yobi;
	for(i=0; i<nlid; i++) {
		int m;
		scanf("%d", &m);
		for(j=0; j<m; j++) scanf("%d", &yobi);
	}
	for(i=0; i<Nst; i++) for(j=0; j<Nst; j++) scanf("%d", &yobi);

	scanf("%d", &Ntid);
	int tid;
	for(tid=0; tid<Ntid; tid++) {
		int m;
		scanf("%d", &m);
		trainTBnst[tid] = m;
		int j;
		for(j=0; j<m; j++) {
			int st , tm, dist;
			scanf("%d %d %d", &st, &tm, &dist);
			trainTB[tid][j][0] = st;
			trainTB[tid][j][1] = tm;
			trainTB[tid][j][2] = dist;
		}
	}

	for(i=0; i<MAXtm; i++) for(j=0; j<3; j++) for(k=0; k<2; k++) outroute[i][j][k] = -1;

	// pay "CUDA tax" now
	{
		void *p;
		cudaError_t err;
		err = cudaMalloc(&p, 4096);
		if (err != cudaSuccess) {
			fprintf(stderr, "cudaMalloc in input() failed!\n");
			exit(1);
		}
		err = cudaFree(p);
		if (err != cudaSuccess) {
			fprintf(stderr, "cudaFree in input() failed!\n");
			exit(1);
		}
	}
}

void output() {
	int i,j;
	printf("##########\n");
	printf("maxDist: %d\n",maxDist);
	for(i=0; i<MAXtm; i++) {
		for(j=0; j<3; j++)  printf("%2d %2d  ", outroute[i][j][0], outroute[i][j][1]);
		printf("\n");
	}
}
/********* Template Part (1) NO CHANGE UP TO HERE **********/

/********* Your Program Part (1) FROM HERE **********/

#define MAX_V 100000
#define MAX_E 500000
#define MAX_T 150000
#define INF 10000000

struct edge{ int to, cost, next; short cap;};

int V;
int head[MAX_V], graph_i = 0;
struct edge graph[MAX_E];
int trainNum[MAX_T];

int h[MAX_V];
int dist[MAX_V];
int preve[MAX_V];

void add_edge(int from, int to, int cost){
    graph[graph_i] = (struct edge){to,-cost,head[from],1}; head[from] = graph_i++; 
    graph[graph_i] = (struct edge){from,cost,head[to],0}; head[to] = graph_i++; 
}

int calc_V(int i, int j){
    return (int)trainTB[i][j][0]+(Nst*(int)trainTB[i][j][1]<<1);
}



#define MAX_NODE 1000000

struct node{ int val,v;};

struct node heap[MAX_NODE];
int heap_size = 0;

void push(struct node n) {
    int i = heap_size++;
    while(i > 0) {
        int p = (i - 1) >> 1;
        if(heap[p].val <= n.val) break;
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = n;
}

struct node pop() {
    struct node ret = heap[0];
    struct node n = heap[--heap_size];
    int i = 0;
    while((i<<1)+1 < heap_size) {
        int a = (i<<1)+1, b = a+1;
        if(b < heap_size && heap[b].val < heap[a].val) a = b;
        if(heap[a].val >= n.val) break;
        heap[i] = heap[a];
        i = a;
    }
    heap[i] = n;
    return ret;
}


/********* Your Program Part (1) UP TO HERE **********/

/********* Template Part (2) NO CHANGE FROM HERE **********/
int main() {
	struct timeval tstart, tlast;
	input();
	gettimeofday(&tstart, NULL);
/********* Template Part (2) NO CHANGE UP TO HERE **********/

/********* Your Program Part (2) FROM HERE **********/
    
    int i, j;
    int SV, TV;
    int nv, nto, ndist;
    
    V = (Nst*MAXtm<<1)+2;
    SV = V-2; TV = V-1;
    
    //init graph
    for(i = 0; i < V; i++) head[i] = -1;
    
    for(i = 0; i < Ntid; i++){
        for(j = 1; j < trainTBnst[i]; j++){
            trainNum[graph_i] = i;
            add_edge(calc_V(i,j-1)+Nst,calc_V(i,j),trainTB[i][j][2]);
        }
    }
    
    for(i = 1; i < (MAXtm<<1); i++) for(j = 0; j < Nst; j++) add_edge((i-1)*Nst+j,i*Nst+j,0);
    for(i = 0; i < Nst; i++){
        add_edge(SV,i,0);
        add_edge(Nst*((MAXtm<<1)-1)+i,TV,0);
    }   
    //
    
    //init potential
    for(i = 0; i < V; i++) h[i] = INF;
    h[SV] = 0;
    for(i = 0; i < V; i++){
        if(i){
            if(i == TV) nv = TV; else nv = i-1;
        } else nv = SV; // SV 0 1 2 3 ... V-3 TV
        for(j = head[nv]; j != -1; j = graph[j].next){
            if((j&1) == 0 && h[graph[j].to] > h[nv]+graph[j].cost){
                h[graph[j].to] = h[nv]+graph[j].cost;
                preve[graph[j].to] = j;
            }
        }
    }
    //
    
    //minimum cost flow
    int flow = 3, ans = 0;
    struct node xnode;

    while(flow){
        if(flow != 3){
            for(i = 0; i < V; i++) dist[i] = INF;
            dist[SV] = 0;
            heap_size = 0;
            push((struct node){0,SV});

            while(heap_size){
                xnode = pop();
                nv = xnode.v;
                if(dist[nv] < xnode.val) continue;

                for(i = head[nv]; i != -1; i = graph[i].next){
                    if(graph[i].cap == 0) continue;
                    nto = graph[i].to;
                    ndist = dist[nv] + graph[i].cost + h[nv]-h[nto];
                    if(dist[nto] > ndist){
                        dist[nto] = ndist;
                        preve[nto] = i;
                        push((struct node){ndist,nto});
                    }
                }
            }

            for(i = 0; i < V; i++) h[i] += dist[i];
        }
        
        ans += h[TV];
        for(nv = TV; nv != SV; nv = graph[i^1].to){
            i = preve[nv];
            graph[i].cap = 0;
            graph[i^1].cap = 1;
        }
        
        flow--;
    }
    //
    
    maxDist = -ans;
    
    //path
        int ntm;
        for(flow = 0; flow < 3; flow++){
            nv = SV; ntm = 0;
            while(nv != TV){
                for(i = head[nv]; i != -1; i = graph[i].next){
                    if((i&1) == 1 || graph[i].cap) continue;
                    graph[i].cap = 1;
                    nto = graph[i].to;
                    
                    if((nv/Nst&1) == 1){    
                        outroute[ntm][flow][0] = nv%Nst;
                        j = ntm;
                        ntm = nto/Nst>>1;
                        if(graph[i].cost){
                            for(; j < ntm; j++){
                                outroute[j][flow][1] = trainNum[i];
                            }
                        }
                    }
                    
                    nv = nto;
                    break;
                }
            }
        }
    //*/

/********* Your Program Part (2) UP TO HERE **********/

/********* Template Part (3) NO CHANGE FROM HERE TO THE END **********/
	gettimeofday(&tlast, NULL);
	printf("...end of execution... time %f\n", 
		   (double)(tlast.tv_sec - tstart.tv_sec)+
		   (double)(tlast.tv_usec - tstart.tv_usec)/ 1000000);
	output();
	return 0;
}

フィボナッチヒープをダイクストラと組み合わせると1桁ms位になることを後で聞いたけど、思いつかなかったなぁ・・・

準急がさらにヤバい解法をつぶやいてて怖かった。

こんな普通めな解法で優勝できるとは思ってなかった・・・

PANAIは全員が別々の方針を実装していたりすれば負けていたかも。


まとめ

高校最後の大会で優勝できて本当に嬉しい。

「優勝は、イマセン!」とかなると面白いなぁーとか思いながら付けたチーム名なので、当初の目的を達成できた。

一人では絶対に優勝できなかった。チームメイトにまじで感謝してる。

2012-08-23

supercon参加記 その1

結果がまだ分からないので、競技のことに関しては明日書くことにして、とりあえずその他雑多なことを書きます。


8/20

・この日は特に面白いことはなかったかな〜、移動日みたいなもんだし。

・朝のんびり出発

・御堂筋線混んでた・・・

・受付の時間は過ぎていた。

・チームメイトと会う。

・きゅうりが斜め前にいた。

・roxionさんも発見した。

・課題が封筒に入っていてちらっと見て「あグラフだー」とか思ったけど、眠くてあんまり何も考えられなかった。

・初阪大学食。

・たぬきそば、まあまあだった。

・時間がやたらあったのでjubeat対戦とかやった。

・色々説明を聞く。

・内部wikiにやっとアクセスする。

関東勢はとっくに「ツブヤキ」をしてて悲しかった。

・この日は全く脳が起動していなかった。

・さっそく「ツブヤキ」が荒れまくっていた。

・強制おやつ休憩

・りんごさん登場。

青春18切符を使うために旅行をしていたらしい。

東京会場と繋がっていたけど、なんか会場の空気がかなりちがった。

・20:00

・回数券カードの使い方を学んだ。

・サイゼリア

ピザが思ったよりうまかった。

・千里中央〜江坂間やたら安い。

・ホテルチェックイン

・同じホテルにりんごさんも泊まっていた。

・部屋でスコットランドヤードをした。

・やっぱMr.X不利すぎだよね・・・


8/21

・どうでもいいことを書くのに飽きたので、重要な事件だけ書きます。

・きゅうり不正。


8/22

東京会場のじゃんけん大会に参加したけど、不当判決のせいで勝てなかった><

・中間提出とは何だったのか。


8/23

・「9時の時点でima1000は「今千里中央でました。。」って感じだったので会場にはいませんでした。」とかツブヤく

・するめ出たかった。

・結局中間提出のとほぼ同じのを出した。

・最後の方はツブヤきまくってた。

・tozan、degwer自重しようぜw

・某氏ふぇぇハラスメントしすぎw 可愛くないし!

・終わった後asiさん、kyuri、refiute、roxionとかと梅田ラウンドワン

・ビリヤードできゅうりが、1ショット打つだけで3つもファールをしてて、不正スキル高ぇと思った。

・ねむい

・おすや

2012-08-19

プログラミン

なんか見つけた。

プログラミン | 文部科学省


んで、なんか作った。

Turing machine


変数とか条件分岐とかなくて微妙な感じだったけど、

ちょっとしたゲームとか作れるようにしてあるらしく、当たり判定とかがあったから作ってみた。

ハターンとかいうコマンドがなかなか使える子だった。

2012-08-17

SRM552

久々にミス無く解けてチャレンジまで出来て、ついていた。

2完で、最終順位は21位だった。

レートは 1585 -> 1775


せっかくだし解法も書くか。


250

少し読解しにくかったけどそれほど詰まらなかった。

いざ実装してみようとすると一筋縄ではいかないことが分かり、思考停止の二分探索にした。

N=1のケースを全く意識していなかったけど、二分探索なら割り算はしないので、にぶたんは正着だったらしい。

二分探索ってはじめバグの温床みたいになって苦手だったけど、

自分のスタイルを確立してしまうと、むしろ書くのが楽しいくらいになる。

半開区間がおすすめ。


500

IOI過去問に同じような問題がある。(簡単そうだと思って飛ばした気がするけど、満点解法は骨がありそう。)

問題 解説

面倒なので↑参照。多分今回の問題は上の50%解法でも間に合ったはず。

後は累積和で長方形内にある花の個数計算するってところ。


こういう問題をバグ無く通せたのはうれしい。

Connection: close